Minimising propagated delay in an integrated aircraft routing and crew pairing framework

Abstract

For reasons of tractability, the airline scheduling problem has traditionally been sequentially decomposed into various stages (eg. schedule generation, fleet assignment, aircraft routing, and crew pairing), with the decisions from one stage imposed upon the decision making process in subsequent stages. Whilst this approach greatly simplifies the solution process, it unfortunately fails to capture the many dependencies between the various stages, most notably between those of aircraft routing and crew pairing, and how these dependencies affect the propagation of delays through the flight network. As delays are commonly transferred between late running aircraft and crew, it is important that aircraft routing and crew pairing decisions are made together. The propagated delay may then be accurately estimated to minimise the overall propagated delay for the network and produce a robust solution for both aircraft and crew.

In this thesis we introduce a new approach to accurately calculate and minimise the cost of propagated delay, in a framework that integrates aircraft routing and crew pairing. Additionally, we propose an extension on this model, in which we incorporate scheduling decisions; allowing higher quality aircraft and crew assignments to be obtained. Finally, we propose a new re-timing heuristic that may be used in conjunction with an incumbent aircraft and crew assignment, capable of simultaneously re-timing aircraft and crew whilst retaining the solution structure. We apply our approaches on a real-world airline network and provide numerical results for a number of test instances. Our results indicate that our new approaches perform very well on the test instances and outperform a number of existing models in a number of areas.