Real-Time Integrated Flight Schedule Recovery Problem Using Sampling-Based Approach

摘要

When the weather conditions at an airport deteriorate or other unexpected events happen, airlines must adjust their flight schedules to satisfy more stringent capacity constraints. In this recovery process, flight timetable, aircraft routings, crew schedules and passenger itineraries will be repaired together. The integrated recovery is one of the most challenging operations research problems, especially when the disruption happens in the hub airport. The recovery process can be divided into two parts in order to realize the real-time optimization. In the first part, a multi-stage IP model was developed on reconstruction of flight schedule and fleet assignment. The second part established IP models on both crew schedule recovery and passenger re-accommodation to evaluate the reconstruction solutions obtained in the first part. A sampling-based algorithmic framework was proposed. All feasible reconstruction solutions in the current time period can be obtained by relaxing crew and passenger constraints. The upper bound and tower bound of each solution will be estimated by optimization on crew recovery and passenger re-accommodation heuristically based on the random samples of the reconstruction solutions for the future time stages. A small case was studied to describe the detail process of the model and method, and a large-scale instance from a Chinese airline was also studied. The computational results present that the proposed approach can obtain satisfying solutions using small size of samples in tractable time and can be implemented into the real world operations. They also reflect the tradeoff between crew cost and passenger delay in the recovery process.