A heuristic approach to the deterministic and stochastic air crew pairing problem

[摘要] ENGLISH SUMMARY : The air crew pairing problem is a subproblem of the integrated airline management problem and one of the more complicated problems to solve in the field of transport logistics.There have been various approaches both in literature and in industry for solving the deterministic crew pairing problem. More recently there have been developments in solving stochastic instances of the problem. This study presents a heuristic approach to solve the crew pairing problem, for the one day planning horizon. An exact solution approach is also presented to generate the entire feasible region and produce the optimal solution, however this approach is computationally tasking for larger problem sets. To address the need to generate solutions in reasonable time for industry requirements, two heuristic solution approaches are presented; the first is based on a greedy tree search heuristic and the second is based on a random tree search with logical constraints to ensure feasibility in all solutions.A comparison is made with results for a benchmark study in literature in order to test the performance of the algorithms used in the deterministic crew pairing problem. The results are competitive for larger problem sets. Sensitivity analysis is also performed to generate -what-if scenarios to test for algorithm robustness. The two heuristic approaches are also adjusted to solve the stochastic crew pairing problem, where weather delays are introduced in the flight network. The results illustrate that in most network problems given a delay asapplied from a given distribution, an airline would need to employ additional crew to service a network of scheduled flights. The results also indicate that a greedy based algorithm performs better than a completely random monte carlo approach for both the deterministic and stochastic crew pairing problems.

[发布机构] Stellenbosch University