A large neighbourhood search heuristic for the aircraft and passenger recovery problem |
| |
Authors: | Serge Bisaillon Jean-Fran?ois Cordeau Gilbert Laporte Federico Pasin |
| |
Institution: | 1. Universit?? de Montr??al and CIRRELT, case postale 6079, Succursale Centre-Ville, Montreal, QC, H3C 3J7, Canada 2. HEC Montr??al and CIRRELT, 3000, chemin de la C?te-Sainte-Catherine, Montreal, QC, H3T 2A7, Canada 3. HEC Montr??al, 3000, chemin de la C?te-Sainte-Catherine, Montreal, QC, H3T 2A7, Canada
|
| |
Abstract: | This paper introduces a large neighbourhood search heuristic for an airline recovery problem combining fleet assignment, aircraft
routing and passenger assignment. Given an initial schedule, a list of disruptions, and a recovery period, the problem consists
in constructing aircraft routes and passenger itineraries for the recovery period that allow the resumption of regular operations
and minimize operating costs and impacts on passengers. The heuristic alternates between construction, repair and improvement
phases, which iteratively destroy and repair parts of the solution. The aim of the first two phases is to produce an initial
solution that satisfies a set of operational and functional constraints. The third phase then attempts to identify an improved
solution by considering large schedule changes while retaining feasibility. The whole process is iterated by including some
randomness in the construction phase so as to diversify the search. This work was initiated in the context of the 2009 ROADEF
Challenge, a competition organized jointly by the French Operational Research and Decision Analysis Society and the Spanish
firm Amadeus S.A.S., in which our team won the first prize. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|