Keywords

1 Introduction

As the aviation industry grows more complex and dynamic, effective generation of recovery plans once disruption occurs becomes inevitable for airlines to minimize any potential loses. Resources, including aircrafts and crew members etc., should also be well allocated to optimize the utilization rate during the recovery period, and to minimize the costs associated. In this paper, a model that focuses on integrated aircraft and passenger recovery is presented.

Most work on airline disruption management attempts to schedule aircraft, crew, and passenger recovery in a tractable manner (Filer et al. 2000). Since integrating the recovery of several resources simultaneously is a complicated task, the number of work attempts to integrate a subset of these components is relatively few and new (Kohl et al. 2007; Clausen et al. 2010). Research focusing on passenger recovery is also scarce.

Bratu and Barnhart (2006) described two integrated recovery models by determining whether the disrupted flight legs should be delayed or cancelled. The models were developed on a flight schedule based network with the aim of minimizing airline operation costs and estimated passenger disruption costs. Zhang and Hansen (2008) introduced an integration with other transportation modes to accommodate disrupted passengers in a hub-and-spoke network. An integer programming model was developed to minimize passenger costs caused by flight delays, cancellations, or substitutions with a nonlinear objective function.

A more recent approach by Jafari and Zegordi (2010) introduced an assignment model that recovers disrupted aircraft schedules and passenger itineraries concurrently with a framework of rolling horizon time. The objective of their model is to minimize costs on aircraft recoveries, delays and cancelations. Bisaillon et al. (2011) employed a neighborhood search heuristic in a large-scale to integrate reassignment of fleets, aircraft routings, and passengers to support resumption of regular operations. However, passengers are given low priority in their model. Petersen et al. (2012) presented an optimization approach to solve a fully integrated airline recovery problem. The problem is broken into four sub-problems to recover flight schedule, aircrafts, crews, and passengers within some time horizon. The objective seeks to minimize the total airline operation cost and passenger delay cost.

It is identified that passenger disruptions have rarely been considered or are given low priority in existing airline disruption management literature. In the limited researches that involve passenger considerations, the impact on passengers are usually not being modeled explicitly, in which their delay costs are only approximate. All these operation-centric approaches have led to a fact that passengers often suffer a much greater impact than that of airlines under disruptions. According to a recent report, the direct cost to passengers on flight delay on the U.S. economy in 2007 was US$16.7 billion, and that for airlines were US$8.3 billions only (NEXTOR 2010). In the view of this, an integrated recovery model that is more passenger-centric is therefore proposed, which aims to seek a tradeoff between airline operation and passenger disruption costs.

The remainder of the paper is organized as follow: Sect. 2 gives a description on the airline recovery problem considered in this paper. Focus is put on an aircraft rerouting problem. The proposed model for the integrated aircraft and passenger recovery is formulated in Sect. 3. The operation of the model is also presented. In Sect. 4, some discussions are made on the proposed model and a conclusion is drawn.

2 Problem Description

A flight schedule is a set of flights that operated by the airline in a given period of time. A flight leg is a non-stop flight from an origin airport to a destination airport. A Fleet is a group of aircrafts A that operated as a unit. It may contain aircrafts of more than one model that shares similar configurations. A route is the sequence of flight legs assigned to a given aircraft a ϵ A. Turn-around time is the time between arrival and departure of aircraft in a rotation.

In this paper, the integrated recovery problem comprises of an aircraft recovery problem and a passenger recovery problem. Given a set of rescheduled flight legs F, individual routings among a single fleet of aircrafts of two models, a l and a s , will be assigned to accommodate each rescheduled flight leg f ϵ F. The assignment will base on the number of affected passengers N p and their itineraries over the recovery period. Passengers who cannot be transferred to the scheduled destination by the end of the recovery period will be transferred to other airlines. The cases of swapping or calling of spare aircraft are allowed. It is assumed the crew base is sufficient enough to cover all modified schedules.

2.1 The Aircraft Rerouting Problem

Once disruption occurs, the disrupted flights corresponded to a single fleet of aircraft bounded in the recovery period (t 0 , T) are rescheduled by the airline operation centre. For clear illustration, an example of a repaired flight schedule of a network with 5 airports (n 1 , n 2 ,…, n 5 ) is given in Fig. 1. The network is served by a fleet of 2 aircrafts (a l1 , a s1) with different seating capacities. Given the rescheduled flight legs (f 1 , f 2 ,…, f 13 ) that would be served by a l1 and a s1 , and a set of affected passengers p ϵ P with their initial itineraries, the problem is to construct the best aircrafts routing to utilize the seating capacity to serve as many passengers as possible. Some possible sets of routings are shown in Table 1.

Fig. 1
figure 1

A time-line network of rescheduled flight legs in a recovery period

Full size image
Table 1 Some examples of possible routings of aircrafts a l1 and a s1
Full size table

In typical cases, the amount of possible routes can be huge when the recovery period is long enough to cover significantly large number of flight legs. For the illustration above, there can be as many as 14 possible sets of routes for a simple case that consists only of 2 aircrafts with 13 flight legs. In reality, most recovery instances have between 30 and 150 aircrafts and the time horizons can be much longer (Rosenberger et al. 2003). With the cases of operating spare aircrafts also being considered, the number of possible aircraft routes can thus be extremely huge. It would be difficult and time consuming to evaluate all possible routings and select the best among them.

In this paper, a comprehensive mathematical formulation that integrates aircraft and passenger rescheduling is presented. The cases of aircraft swapping, ferrying, and spare aircrafts operations, which are seldom being considered in most aircraft rerouting literature are also included.

3 Model Formulation

The objective of the model is to minimize the sum of passenger delay cost and airline operation cost. Passenger delay cost involves a delay cost of arrival time at destination to each passenger (in minute), and an inconvenient cost due to direction to other airlines, which causes a loss of goodwill to the airline. Airline operation cost includes an aircraft operation cost depends on the aircraft model (in minute flight time), a cost on swapping, ferrying, or flying spare aircraft, and a compensation cost on meal and drinks to passengers for departure delays over a given limit of time. The parameters common to the proposed model are:

C dp

Cost of delay to passenger (per minute)

C cp

Inconvenient cost to passengers who are directed to other airlines

C pf

Cost of assigning a passenger to flight f

C sa

Cost of swapping aircraft a

C aa

Cost of operating spare aircraft a

C al

Cost of operating aircraft model a l (per minute)

C as

Cost of operating aircraft model a s (per minute)

C mp

Compensation cost to airlines on meals and drinks to passengers with departure delay over a given time limit h mp

H ta

Minimum turn-around time for aircraft a

S al

Seating capacity of aircraft model a l

S as

Searing capacity of aircraft model a s

T ap

Scheduled arrival time of passenger p

T dp

Scheduled departure time of passenger p

N f

Total number of rescheduled flight legs

The decision variables common to the model are:

k saf

= 1 if aircraft a of flight f is swapped, and 0 otherwise

k fa

= 1 if aircraft a is ferried, and 0 otherwise

k aaf

= 1 if flight f is operated by a spare aircraft a, and 0 otherwise

k asf

= 1 if flight f is operated by aircraft type a s , and 0 otherwise

k alf

= 1 if flight f is operated by aircraft type a l , and 0 otherwise

t aaf

= Actual arrival time of aircraft a for recovered flight f

t daf

= Actual departure time of aircraft a for recovered flight f

b pf

= 1 if passenger p is being served in flight f, and 0 otherwise

b cp

= 1 if passenger p is being directed to other airlines, and 0 otherwise

b mp

= 1 if (b pf t daf  − T dpi ) ≥ h mp , and 0 otherwise

m alf

= 1 if flight f is operated by aircraft model a l, and 0 otherwise

m asf

= 1 if flight f is operated by aircraft model a s, and 0 otherwise

n pf

= Number of passengers being assigned to flight f

The objective function is formulated as follows:

$$ \begin{aligned} \hbox{min} & \sum\limits_{f \in F} {\sum\limits_{p \in P} {[(t_{aaf} - T_{ap} )(b_{pf} )C_{dp} ]} } \\ & + \sum\limits_{a \in A} {\sum\limits_{f \in F} {[(t_{daf} - t_{aaf} )m_{alf} k_{alf} C_{al} } } \\ & + (t_{daf} - t_{aaf} )m_{asf} k_{asf} C_{as} + k_{saf} C_{sa} + k_{aaf} C_{aa} \\ & + n_{pf} C_{pf} ] + \sum\limits_{p \in P} {(b_{mp} C_{mp} + b_{cp} C_{dp} )} \\ \end{aligned} $$

Subject to:

$$ m_{alf} + m_{asf} = 1 \, \forall f \in F $$
(1)
$$ k_{asf} C_{as} + k_{alf} C_{al} \ge n_{f} \, \forall f \in F $$
(2)
$$ t_{{aaf_{i + 1} }} + t_{{daf_{i} }} \ge H_{ta} \, \forall a \in A,\ f \in F $$
(3)
$$ b_{fp} + b_{cp} = N_{p} \, \forall p \in P $$
(4)
$$ b_{pf} \cdot t_{daf} \ge T_{dp} \, \forall p \in P,\ f \in F $$
(5)
$$ \begin{aligned} & k_{saf} ,\;k_{fa} ,\;k_{aaf} ,\;k_{asf} ,\;k_{alf} ,\;b_{cp} ,b_{mp} ,\;m_{alf} ,\;m_{asf} = \left\{ {0,{ 1}} \right\},\;{\text{and}} \\ & t_{aaf} ,\;t_{daf}\;{\text{are}}\;{\text{REAL}},\;{\text{and}}\;n_{pf}\;{\text{is}}\;{\text{integer}} \\ \end{aligned} $$
(6)

Constraint (1) ensures all flight legs bounded in the recovery period are assigned to an aircraft of either model a l or a s . Constraint (2) is a seat capacity constraint for aircrafts. Constraint (3) guarantees a minimum turnaround time is assigned between flight legs operated by the same aircraft. Constraint (4) ensures all passengers are either being served or redirected to other airlines. Constraint (5) states that no passenger is allowed to depart before the initial scheduled departure time. Finally, constraints in (6) ensures that the decision variables k saf , k fa , k aaf , k asf , k alf , b cp ,b mp , m alf , m asf are binary variables, the aircraft departure times (t aaf , t daf ) are real, and the number of assigned passengers to a specific flight (n pf ) is integer.

3.1 Model Operations

To support effective operation of the model, various forms of information is required. They include the initial fleet schedule before disruption; the initial passengers schedule, including the scheduled departure time, the origin airport, the destination airport, and the scheduled arrival time; the repaired flight schedule correspond to the fleet; the aircrafts combination in the fleet; and the location of each aircraft at the beginning of the recovery period.

Given these, the number of passengers that needed to arrive at a specific airport at a specific timeslot, the number of passengers that scheduled to depart from a specific airport at a specific timeslot, and the number of passengers in each initial scheduled flight can be determined The model would generate possible sets of aircraft routings to cover all rescheduled flight legs based on these and select the optimal set of routings. The proposed framework is modeled in Fig. 2.

Fig. 2
figure 2

Proposed model framework on integrated aircraft and passenger recovery

Full size image

The detailed operation process is as follows:

  1. 1.

    Identify the number of passengers whom requirements can be satisfied by traveling on flight f 1

  2. 2.

    Identify the available aircrafts that are able to operate flight f 1

  3. 3.

    Assign an aircraft to flight f 1

  4. 4.

    Check if the aircraft is a swapping or spare aircraft

  5. 5.

    Assign passengers to the flight

  6. 6.

    If the number of passengers exceeds the seating capacity of the assigned aircraft, move the remaining passengers to the next suitable flight

  7. 7.

    If there is no more suitable flight, direct them to other airlines

  8. 8.

    Repeat steps i to vii until all repaired flight legs are covered

  9. 9.

    Direct remaining passengers to another airline

  10. 10.

    Evaluate the generated routing set

  11. 11.

    Repeat steps i to x to get another possible routing set, until a stopping criteria is reached

  12. 12.

    Compare all generated routings and select the best one to implement.

4 Discussions and Conclusions

In a given repaired flight schedule, the possible combination of aircraft routings can be huge. Also, given a high number of decision variables in the proposed model, identifying and evaluating all of them to find an optimized solution would be time consuming. It is recommended to use intelligent search heuristic, such as Genetic Algorithm (GA) or neighborhood search etc., to solve the identified problem to reduce the computation time. In this paper, a framework with the problem model is only provided to give a new research direction on passenger-oriented disruption management. Further investigations can be made to identify the most suitable algorithm in solving the model presented.

With the proposed model being solved, it is believed airlines can be equipped with higher reliability and customer service levels. This in turns increases customer retention rate and confidence of new customers in selecting the airline for air travels. The developed algorithm can further assist airlines in attracting high-value passengers who are sensitive to airline on-time reliability, increasing customer loyalty and satisfactory level, and reducing direct and indirect costs caused by passenger disruptions. These are especially important for airlines as the air travel market grows larger and more competitive.

In conclusion, a new optimization formulation that integrates the recovery of aircrafts and passengers simultaneously is proposed in this paper. The model routes the suitable aircrafts to operate the suitable rescheduled flight legs, and at the same time, generates the corresponding itineraries for affected passengers. The objective is to minimize the costs of passenger delay and airline operation, and to utilize the seating capacity of available aircrafts. After solving the model, airlines will be able to assign suitable aircrafts to support flight recovery under disruptions within a short time-period, reduce passenger delays, and at the same time achieve high customer satisfaction and remain competitive in the market.