Improvements to a large neighborhood search heuristic for an integrated aircraft and passenger recovery problem

Improvements to a large neighborhood search heuristic for an integrated aircraft and passenger recovery problem

0.00 Avg rating0 Votes
Article ID: iaor20141189
Volume: 233
Issue: 1
Start Page Number: 234
End Page Number: 245
Publication Date: Feb 2014
Journal: European Journal of Operational Research
Authors: , ,
Keywords: heuristics: local search, vehicle routing & scheduling
Abstract:

Because most commercial passenger airlines operate on a hub‐and‐spoke network, small disturbances can cause major disruptions in their planned schedules and have a significant impact on their operational costs and performance. When a disturbance occurs, the airline often applies a recovery policy in order to quickly resume normal operations. We present in this paper a large neighborhood search heuristic to solve an integrated aircraft and passenger recovery problem. The problem consists of creating new aircraft routes and passenger itineraries to produce a feasible schedule during the recovery period. The method is based on an existing heuristic, developed in the context of the 2009 ROADEF Challenge, which alternates between three phases: construction, repair and improvement. We introduce a number of refinements in each phase so as to perform a more thorough search of the solution space. The resulting heuristic performs very well on the instances introduced for the challenge, obtaining the best known solution for 17 out of 22 instances within five minutes of computing time and 21 out of 22 instances within 10minutes of computing time.

Reviews

Required fields are marked *. Your email address will not be published.