Preemptive Rerouting of Airline Passengers under Uncertain Delays

Abstract

An airline's operational disruptions can lead to flight delays that in turn impact passengers, not only through the delay itself but also through possible missed connections. Much research has been done on crew recovery (rescheduling crews after a flight delay or cancellation), but little research has been done on passenger reaccommodation. Our goal is to design ways that passenger reaccommodation can be improved so that passengers can spend less time delayed and miss fewer connections.

Since the length of a delay is often not known in advance, we consider preemptive rerouting of airline passengers before the length of the delay is known. Our goal is to reaccommodate passengers proactively as soon as it is known that a flight will be delayed instead of waiting until passengers have missed connections and to use known probabilities for the length of delay. In addition, we consider all of the affected passengers together so that we can effectively handle passengers' competition for available seats. We can give certain seats to people with short connections or those connecting to international flights.

When there is one delayed flight, we model the problem as a two-stage stochastic programming problem, with first-stage decisions that assign passengers initial itineraries and second-stage decisions that re-assign any passengers who are subsequently disrupted by the delay. We present a Benders decomposition approach to solving this problem. Computational results for this model are given, showing its effectiveness for reducing the length of passenger delays.

When there is more than one delayed flight, we define a portfolio model which assigns passengers to portfolios that define their itineraries under all possible disruption outcomes. We focus on computational methods for solving this model.