Math-heuristics for the air logistics service recovery

Abstract

Airline disruptions can cause huge cost for airlines and serious inconvenience for passengers. The air logistics service recovery aims to minimize the additional operating cost incurred by the airline disruptions and improve the overall service performance. Considering the complexity of the whole recovery problem, this thesis decomposes it into several sub recovery problems, while are solved in a sequential manner. The integrated recovery problem aims to consider two or more sub recovery problems simultaneously and achieve a better recovery solution. The main challenge of the integrated recovery problem is solution efficiency. This research addresses three different integrated recovery problems. For each of them, efficient models and algorithms are proposed.

First, the integrated aircraft and crew schedule recovery problem is studied. A two stage heuristic algorithm is proposed. In the first stage, the integrated aircraft recovery and flight-rescheduling model with partial crew consideration is built. This model is based on the traditional multi-commodity network model for the aircraft schedule recovery problem. The objective of this model also includes minimization of the original crew connection disruption. In the second stage, the integrated crew schedule recovery and flight re-scheduling model with partial aircraft consideration is built. We proposed a new multi-commodity model for the crew schedule recovery. The main advantage of such model is that it is much more efficient to integrate the flight-scheduling and aircraft consideration. New constraints are incorporated to guarantee that the aircraft connections generated in stage 1 are still feasible. Two stages are run iteratively until no improvement can be achieved. Experimental results show that our method can provide better recovery solutions compared with the benchmark algorithms.

Secondly, we study the integrated aircraft and passenger schedule recovery problem. To efficiently solve this problem, we propose a novel three stage math-heuristic algorithm. Our algorithm is tested on the data provided by the ROADEF 2009 challenge. Computational results reveal that our algorithm can achieve a good solution very efficiently. Among 32 instances, our algorithm can generate the best solution for 23 instances. In the meanwhile, characteristics of our algorithm indicate that our algorithm has very good potential in practical implementation.

Third, the integrated gate and passenger schedule recovery problem is studied. A sophisticated gate assignment plan can be easily disrupted and serious consequences might be caused. The aim is to propose an efficient gate re-assignment methodology to deal with the disruptions. Three objectives are considered, which are minimizing total flight delays, minimizing the number of gate re-assignment operations and minimizing the number of passenger miss connections. Two multi-commodity network flow models are built for the pure gate re-assignment problem and the gate re-assignment problem considering transfer passengers. Heuristic algorithms are proposed to solve the models efficiently. The methodology is tested based on real-world data in the ORD airport. Computational results reveal that the proposed methodology can provide high quality solution in short response.