An integrated optimization mode for multi-type aircraft flight scheduling and routing problem

Abstract

This paper proposes an optimization model for the integrated aircraft flight scheduling and routing problem, which allows a simultaneous determination of the departure time of each flight trip and assignment of a set of aircraft located at different airports to perform all flight trips. The proposed model envisages that each flight trip is covered by its own particular aircraft type or a larger airplane. Further, departure and arrival times of each flight trip are within a flexible time window in its aircraft's route and origin/destination airports, and the number of airplanes firstly distributed in the base airports is fully accounted for in the model. The model not only can effectively minimize weighted operation costs for the number of airplanes and the total idle time for adjacent flight trips covered by an aircraft, but also can maximize the number of transported passengers. This paper further presents a two-stage heuristic approach based on the ant colony optimization algorithm, which efficiently finds the most acceptable solutions. The above algorithm is used to generate a series of aircraft routes, and a polynomial algorithm is designed to obtain their feasible flight trip timetable. Finally, the model is applied to a case study to design the integrated aircraft flight scheduling and routing plan for a real airline in China. A comparative analysis of the conventional and proposed models proved the latter's feasibility.

Keywords

• flight scheduling
• aircraft routing
• multiple-aircraft type
• multi-objective
• heuristic algorithm