Integrated aircraft scheduling problem: An auto-adapting algorithm to find robust aircraft assignments for large flight plans

Abstract

The overall airline scheduling process involves hierarchical steps starting with the network design and ending with crew assignment. Aircraft routing is especially important with respect to timing and costs for an airline. In this contribution, we focus on aircraft routing where aircraft are assigned to flight legs further considering maintenance requirements. We developed and implemented algorithms that extend the aircraft routing problem (ARP) by including profit and robustness. The latter objective is important as the dependencies of flights and airlines increases and deviations to the original time plan as unexpected events like volcano eruptions or heavy weather-related issues are difficult to handle. A robust aircraft routing ensures that unforeseen events have less impact. The results are compared to current state-of-the-art solutions. We developed a test instance-generator to create specific problems and build a library for future benchmarking tests.