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

Karine Sinclair, Jean François Cordeau, Gilbert Laporte

Research output: Contribution to journalArticlepeer-review

36 Citations (Scopus)

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 10 minutes of computing time.

Original languageEnglish
Pages (from-to)234-245
Number of pages12
JournalEuropean Journal of Operational Research
Volume233
Issue number1
DOIs
Publication statusPublished - 16 Feb 2014

Keywords

  • Aircraft routing
  • Airline recovery
  • Fleet assignment
  • Large neighborhood search
  • Passenger itineraries

ASJC Scopus subject areas

  • Computer Science(all)
  • Modelling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Fingerprint Dive into the research topics of 'Improvements to a large neighborhood search heuristic for an integrated aircraft and passenger recovery problem'. Together they form a unique fingerprint.

Cite this