Dynamic aircraft recovery problem - An operational decision support framework. (May 2020) - Vink, J.; Santos, B.F.; Verhagen, W.J.C.; Medeiros, I.; Filho, R.
Highlights: An operational tool that solves the aircraft recovery problem is presented. Recovery solutions are dynamically computed, whenever a disruption occurs. A Selection Algorithm is proposed, computing solutions in less than 1 min. Passengers itineraries are considered without compromising computational times. For 90% of the disruptions the Selection Algorithm found the optimal solution. Abstract: This paper presents a new approach for solving the recovery of the airline schedule when disruptions have occurred. The goal is to develop an operational tool that provides the airline with a solution in less than one minute. The proposed recovery model uses a heuristic that iteratively solves selections of the airline's fleet in order to quickly converge to a good solution. An initial solution is always presented in seconds, after which potential reductions of disruption cost are investigated. The schedule is modeled as a set of parallel time-space networks, using an integer linear programming. The model is solved dynamically; a recovery solution is found whenever a disruption occurs and subsequent disruptions are solved based on the previously found solution. Aircraft maintenance schedules and passenger itineraries are modeled, while crew concerns are indirectly taken into consideration to avoid major disruptions caused by the recovery solution. The approach presented in this paper can be applied on heterogeneous fleets and to both point-to-point and (multi) hub-and-spoke airlines. The performance of the selection heuristic is discussed using a case study on the network of an airline operating in the United States. This case study shows that the selection heuristic can find a globally optimal solution in 90% of the disruption instances tested, within 22 s on average. This corresponds to 4% of the time needed to compute the optimal solution using the entire fleet.