Robust and Recoverable Maintenance Routing Schedules

We present a methodology to compute more efficient airline schedules that are less sensitive to delay and can be recovered at lower cost in case of severe disruptions. We modify an original schedule by flight re-timing with the intent of improving some structural properties of the schedule. We then apply the new schedules on different disruption scenarios and then recover the disrupted schedule with the same recovery algorithm. We show that solutions with improved structural properties better absorb delays and are more efficiently recoverable than the original schedule. We provide computational evidence using the public data provided by the ROADEF Challenge 2009 http://challenge.roadef.org/2009/index.en.htm)