Airline planning and scheduling: Models and solution methodologies

doi:10.1007/s42524-020-0093-5

Front. Eng

2020, Vol. 7

Issue (1) : 1-26 https://doi.org/10.1007/s42524-020-0093-5

REVIEW ARTICLE

Airline planning and scheduling: Models and solution methodologies

Lei ZHOU¹, Zhe LIANG¹(

), Chun-An CHOU², Wanpracha Art CHAOVALITWONGSE³

¹. School of Economics & Management, Tongji University, Shanghai 200092, China
². Mechanical & Industrial Engineering Department, Northeastern University, Boston, MA 02115, USA
³. Department of Industrial Engineering and Institute for Advanced Data Analytics, University of Arkansas, Fayetteville, AR 72701, USA

Download: PDF(1115 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

Abstract

The airline industry is a representative industry with high cost and low profitability. Therefore, airlines should carefully plan their schedules to ensure that overall profit is maximized. We review the literature on airline planning and scheduling and focus on mathematical formulations and solution methodologies. Our research framework is anchored on three major problems in the airline scheduling, namely, fleet assignment, aircraft routing, and crew scheduling. General formulation, widely used solution approaches, and important extensions are presented for each problem and integrated problems. We conclude the review by identifying promising areas for further research.

Keywords airline planning fleet assignment problem aircraft routing problem crew pairing problem crew rostering problem crew scheduling problem integrated planning

Corresponding Author(s): Zhe LIANG

Just Accepted Date: 17 January 2020 Online First Date: 24 February 2020 Issue Date: 02 March 2020

Cite this article:

Lei ZHOU,Zhe LIANG,Chun-An CHOU, et al. Airline planning and scheduling: Models and solution methodologies[J]. Front. Eng, 2020, 7(1): 1-26.

URL:

https://academic.hep.com.cn/fem/EN/10.1007/s42524-020-0093-5
https://academic.hep.com.cn/fem/EN/Y2020/V7/I1/1

Fig.1 Connection network proposed by Abara (1989).

Sets
K	set of fleets, indexed by k
L	set of legs, indexed by l, i, or j
L ⁺	= L∪ {0}. The index i = 0 denotes the original arc, and index j = 0 denotes the terminal arc. Given a leg connection i→ j, i, j Î L ⁺, if i = 0, then j is the first leg of a daily aircraft route; if j = 0, then i is the last leg of a daily aircraft route.
S	set of stations, indexed by s
$L s A$	set of legs arriving at station s
$L s D$	set of legs departing from station s
Constants
M _k	number of available aircraft of fleet k
Parameters
c _k	cost of each aircraft in fleet k
p _jk	benefit of operating leg j by fleet k
Variables
x _ijk	Î {0, 1}. x _ijk = 1, if fleet k covers the connection i→ j, i, j Î L ⁺; and x _ijk = 0, otherwise.

Max	$∑ i ∈ L + ∑ j ∈ L ∑ k ∈ K p j k x i j k − ∑ j ∈ L ∑ k ∈ K c k x 0 j k$		(2.1)
s.t.	$∑ i ∈ L + ∑ k ∈ K x i j k = 1$	$∀ j ∈ L$	(2.2)
	$∑ i ∈ L + x i l k − ∑ j ∈ L + x l j k = 0$	$∀ l ∈ L, ∀ k ∈ K$	(2.3)
	$∑ l ∈ L s D x 0 l k − ∑ l ∈ L s A x l 0 k = 0$	$∀ s ∈ S, ∀ k ∈ K$	(2.4)
	$∑ l ∈ L x 0 l k ≤ M k$	$∀ k ∈ K$	(2.5)
	$x i j k ∈ {0, 1}$	$∀ i, j ∈ L +, ∀ k ∈ K$	(2.6)

Sets
L ^DM	set of dummy arcs
L ^*	= L∪ L ^DM
	$∑ i ∈ L * x i l k − ∑ j ∈ L * x l j k = 0$	$∀ l ∈ L, ∀ k ∈ K$	(2.7)

Fig.2 Connection network with dummy source/sink nodes and wrap-around arcs.

Fig.3 Example of the time–space network.

Sets (cont.)
N _k	set of nodes in the network for fleet k, indexed by n
$L n +$	set of legs inbound to node n
$L n −$	set of legs outbound from node n
L ^P	set of legs crossing the aircraft count time. The count time can be any time point of a day.
$N k P$	set of nodes in the network for fleet k, and the ground arcs into these nodes cross the aircraft count time
Variables (cont.)
x _lk	Î{0, 1}. x _lk = 1, if fleet k covers the leg l; x _lk = 0, otherwise.
$y n +$	number of aircraft on the ground arc into node n, where n Î N _k, k Î K
$y n −$	number of aircraft on the ground arc out node n, where n Î N _k, k Î K

Max	$∑ l ∈ L ∑ k ∈ K p l k x l k$		(2.8)
s.t.	$∑ k ∈ K x l k = 1$	$∀ l ∈ L$	(2.9)
	$∑ l ∈ L n + x l k + y n + − ∑ l ∈ L n − x l k − y n − = 0$	$∀ n ∈ N k, ∀ k ∈ K$	(2.10)
	$∑ l ∈ L P x l k + ∑ n ∈ N k P y n + ≤ M k$	$∀ k ∈ K$	(2.11)
	$x l k ∈ {0, 1}$	$∀ l ∈ L, ∀ k ∈ K$	(2.12)
	$y n +, y n − ≥ 0$	$∀ n ∈ N k, ∀ k ∈ K$	(2.13)

Tab.1 Comparison of the connection and time–space networks

Max	$∑ i ∈ I p i z i − ∑ l ∈ L ∑ k ∈ K c l k x l k$		(2.14)
s.t.	(2.9)–(2.13)
	$∑ k ∈ K C A P k x l k − ∑ i ∈ I l z i ≥ 0$	$∀ l ∈ L$	(2.15)
	$0 ≤ z i ≤ D M D i$	$∀ i ∈ I$	(2.16)

Min	$∑ l ∈ L ∑ k ∈ K c l k x l k + ∑ i ∈ I ∑ j ∈ I (p i − b i j p j) z i j$		(2.17)
s.t.	(2.9)–(2.13)
	$∑ i ∈ I l D M D i − ∑ i ∈ I l ∑ j ∈ I z i j + ∑ j ∈ I ∑ i ∈ I l b j i z j i ≤ ∑ k ∈ K C A P k x l k$	$∀ l ∈ L$	(2.18)
	$∑ j ∈ I z i j ≤ D M D i$	$∀ i ∈ I$	(2.19)
	$z i j ≥ 0$	$∀ i, j ∈ I$	(2.20)

Literature	Network¹	Time horizon²	Solution method³	Features⁴
Abara (1989)	CN	D	–	–
Berge and Hopperstad (1993)	TSN	W	heuristic	–
Subramanian et al. (1994)	TSN	D	cutting-edge algorithms	maintenance arcs
Hane et al. (1995)	TSN	D	interior-point algorithm; B&B	–
Clarke et al. (1996)	TSN	D	LP-based B&B	maintenance+ crew considerations
Rushmeier and Kontogiorgis (1997)	CN	D	CPLEX	flight connection possibilities
Barnhart et al. (1998)	CN	D	B&P	string-based; through revenues
Ioachim et al. (1999)	CN	W	DW; CG	time synchronization
Rexing et al. (2000)	TSN	D	iterative solution technique	departure time window
Barnhart et al. (2002)	TSN	D	heuristic approach based on C&RG	itinerary-based demand
Yan and Tseng (2002)	TSN	D	Lagrangian relaxation; sub-gradient method	decide O&D pairs by model
Lohatepanont and Barnhart (2004)	TSN	D	heuristic approach based on C&RG	itinerary-based demand
Rosenberger et al. (2004)	CN	D	ILOG	string-based; short cycles
Bélanger et al. (2006a)	TSN	D	B&P	departure time window
Bélanger et al. (2006b)	TSN	W	two-phase heuristic	fleet homogeneity
Smith and Johnson (2006)	TSN	D/W	CG	station purity
Jacobs et al. (2008)	TSN	D	iterative algorithm	O&D network effects
Pilla et al. (2008)	TSN	D	statistical experiments approach	demand driven dispatch
Barnhart et al. (2009)	TSN	D	heuristic	realistic revenue functions
Gao et al. (2009)	TSN	D	CPLEX	station purity; crewbase purity
Haouari et al. (2009)	CN	D/W	two-phase network flow-based heuristic	–
Sherali et al. (2010)	TSN	–	BD	itinerary-based demand
Pilla et al. (2012)	TSN	W	L-shaped method	stochastic demand
Liang and Chaovalitwongse (2013)	TSN	W	CPLEX	weekly rotation-tour network
Sherali et al. (2013a)	CN	D	BD	itinerary-based demand; flight retiming
Sherali et al. (2013b)	TSN	D	BD	itinerary-based demand; flight retiming
Salazar-González (2014)	TSN	D	heuristic	FAP+ ARP+ CSP
Shao et al. (2017)	CN	D	BD	FAP+ ARP+ CPP

Tab.2 Summary of the literature on FAP

Tab.3 Maintenance types

Sets (cont.)
G	set of ground arcs in the network, indexed by g, also indexed by $(e l, a −, e l, a)$ , $(e l, a, e l, a +)$ , $(e l, d −, e l, d)$ , and $(e l, d, e l, d +)$ . e _l,a indexes the arrival node of leg l, and e _l,d indexes the departure node of leg l. The “-” (“+”) represents the previous (succeeding) event. Thus, $(e l, a −, e l, a)$ indexes the ground arc into the arrival node of leg l, $(e l, a, e l, a +)$ indexes the ground arc out the arrival node of leg l, $(e l, d −, e l, d)$ indexes the ground arc into the departure node of leg l, and $(e l, d, e l, d +)$ indexes the ground arc out the departure node of leg l.
G ^P	set of ground arcs in the network cross the count time
R	set of strings, indexed by r
R _l	set of strings that include leg l
$R l +$	set of strings beginning with leg l
$R l −$	set of strings ending with leg l
Parameters (cont.)
c _r	cost of string r
g _r	number of times that string r crosses the count time
M	total number of available aircraft
Variables (cont.)
x _r	Î{0, 1}. x _r = 1, if the string r is selected; x _r = 0, otherwise.
y _g	number of aircraft on the ground arc g

Min	$∑ r ∈ R c r x r$		(3.1)
s.t.	$∑ r ∈ R l x r = 1$	$∀ l ∈ L$	(3.2)
	$∑ r ∈ R l + x r − y (e l, d −, e l, d) + y (e l, d, e l, d +) = 0$	$∀ l ∈ L$	(3.3)
	$− ∑ r ∈ R l − x r − y (e l, a −, e l, a) + y (e l, a, e l, a +) = 0$	$∀ l ∈ L$	(3.4)
	$∑ r ∈ R γ r x r + ∑ g ∈ G P y g ≤ M$		(3.5)
	$y g ≥ 0$	$∀ g ∈ G$	(3.6)
	$x r ∈ {0, 1}$	$∀ r ∈ R$	(3.7)

Sets (cont.)
$L j − M$	set of legs i of all feasible connection i→ j, i, j Î L ⁺, and a maintenance check could be planned between the arrival of leg i and the departure of leg j
$L j − NM$	set of legs i of all feasible connection i→ j, i, j Î L ⁺, and a maintenance check could not be planned between the arrival of leg i and the departure of leg j
Constants (cont.)
t _j	flying hours of leg j
u ^UB	maximum flight hours between two consecutive maintenance checks
Variables (cont.)
x _ij	Î{0, 1}. x _ij = 1, if the connection i→ j is selected, i, j Î L ⁺; x _ij = 0, otherwise.
u _j	total accumulated flight hours since last maintenance check after leg j served

Min	0		(3.8)
s.t.	$∑ i ∈ L + x i j = 1$	$∀ j ∈ L$	(3.9)
	$∑ i ∈ L * x i l − ∑ j ∈ L * x l j = 0$	$∀ l ∈ L$	(3.10)
	$∑ l ∈ L x 0 l ≤ M$		(3.11)
	$u j x i j = t j x i j$	$∀ i ∈ L j − M, ∀ j ∈ L$	(3.12)
	$u j x i j = (u i + t j) x i j$	$∀ i ∈ L j − NM, ∀ j ∈ L$	(3.13)
	$t j ≤ u j ≤ u UB$	$∀ j ∈ L$	(3.14)
	$x i j ∈ {0, 1}$	$∀ i, j ∈ L +$	(3.15)

Fig.4 The daily time–space network and the rotation tour network.

Sets (cont.)
S ^M	set of maintenance airports, indexed by s
Indicators
a _dn	Î{0, 1}. a _dn = 1, if node n belongs to day d; a _dn = 0, otherwise.
$β s d n +$	Î{0, 1}. $β s d n +$ = 1, if maintenance arc at airport s inbound to node n on day d; $β s d n +$ = 0, otherwise.
$β s d n −$	Î{0, 1}. $β s d n −$ = 1, if maintenance arc at airport s outbound from node n on day d; $β s d n −$ = 0, otherwise.
Constants (cont.)
D	maximum number of days between two consecutive maintenances for an aircraft
$Q s M$	maximum number of aircraft that can undergo maintenance at airport s per night
Variables (cont.)
x _ld	Î{0, 1}. x _ld = 1, if leg l is flown on day d; x _ld = 0, otherwise.
z _sd	number of aircraft at maintenance airport s at the end of day d

Min	0		(3.8)
s.t.	$∑ d ∈ D x l d = 1$	$∀ l ∈ L$	(3.16)
	$∑ l ∈ L n + ∑ d ∈ D α d n x l d + y n + + ∑ s ∈ S M ∑ d ∈ D β s d n + z s d$ $− ∑ l ∈ L n − ∑ d ∈ D α d n x l d − y n − − ∑ s ∈ S M ∑ d ∈ D β s d n − z s d = 0$	$∀ n ∈ N$	(3.17)
	$∑ s ∈ S M ∑ d ∈ D d ? z s d ≤ M$		(3.18)
	$∑ d ∈ D z s d ≤ Q s M$	$∀ s ∈ S$	(3.19)
	$x l d ∈ {0, 1}$	$∀ l ∈ L, ∀ d ∈ D$	(3.20)
	$y n +, y n − ≥ 0$	$∀ n ∈ N$	(3.21)
	$z s d ≥ 0$	$∀ s ∈ S, ∀ d ∈ D$	(3.22)

Tab.4 Differences among the string-based network (SN), connection network (CN), and time–space network (TSN)

Tab.5 Data size and computation running time of models in research

Abbreviation	Full name	Definition
STD	scheduled time of departure	–
ETA	estimated time of arrival	–
ATD	actual time of departure	–
ATA	actual time of arrival	–
IDD	independent delay of departure	$I D D j = max (A T D j − S T D j − P D j, 0)$
IDA	independent delay of arrival	$I D A j = max (A T A j − E T A j − P D j, 0)$
PD	propagated delay	$P D j = max (A T A i + min T m − S T D j, 0)$

Tab.6 Relevant concepts of delay

Tab.7 Example of relevant concepts of delay (minTm = 50 min)

Fig.5 Example of relevant concepts of delay.

Tab.8 Summary of solution approaches in the literature for the fleet assignment problem (FAP)

Fig.6 Relationship of duty, pairing, and roster.

Tab.9 Typical crew regulations

Min	$∑ p ∈ P c p x p$		(4.1)
s.t.	$∑ p ∈ P l x p ≥ 1$	$∀ l ∈ L$	(4.2)
	$x p ∈ {0, 1}$	$∀ p ∈ P$	(4.3)

Sets (cont.)
L _p	set of legs included in pairing p
P _s	set of pairings begging and ending at crewbase s
Constants (cont.)
$u s LB$	lower bound of crew hours assigned to base s
$u s UB$	upper bound of crew hours assigned to base s
	$u s LB ≤ ∑ p ∈ P s ∑ j ∈ L p t j x p ≤ u s UB$	$∀ s ∈ S$	(4.4)

Min	$∑ q ∈ Q ∑ e ∈ E c q e x q e$		(4.5)
s.t.	$∑ q ∈ Q p x q ≥ M p$	$∀ p ∈ P$	(4.6)
	$∑ q ∈ Q x q e = 1$	$∀ e ∈ E$	(4.7)
	$x q e ∈ {0, 1}$	$∀ q ∈ Q, ∀ e ∈ E$	(4.8)

Tab.10 CRM with different objective functions

Sets (cont.)
E ^C	set of crew with the rank of captain
E ^F	set of crew with the rank of first officer
Constants (cont.)
$M p C$	number of crew with the rank of captain required by pairing p
$M p F$	number of crew with the rank of first officer required by pairing p
	$∑ e ∈ E c ∑ q ∈ Q p x q e ≥ M p C$	$∀ p ∈ P$	(4.9)
	$∑ e ∈ E c ∑ q ∈ Q p x q e + ∑ e ∈ E F ∑ q ∈ Q p x q e ≥ M p C + M p F$	$∀ p ∈ P$	(4.10)

Fig.7 An example of the move-up crew.

Sets (cont.)
T ^PD	set of possible days of a pairing, that is, {1, 2,…, the maximum number of days in a pairing}, indexed by t
S ^CB	set of crewbases, indexed by s
P _lst	set of pairings covering l Î L, starting from s Î S ^CB, and there are t Î T ^PD days to the end of the pairing
$P ‾ l s t$	set of pairings providing a move-up crew for leg l which is covered by p Î P _lst
Parameters (cont.)
w	weight in the objective function that encourages more move-up crews
Variables (cont.)
z _lst	number of move-up crews of leg l if l is covered by a p Î P _lst
Min	$∑ p ∈ P c p x p − w ∑ l ∈ L ∑ s ∈ S CB ∑ t ∈ T PD z l s t$		(4.11)
	$z l s t ≤ ∑ p ∈ P ‾ l s t x p$	$∀ l ∈ L, ∀ s ∈ S CB, ∀ t ∈ T PD$	(4.12)

Fig.8 General solution method for the crew scheduling model.

Sets (cont.)
C	set of short connections, indexed by (i, j)
R _ij	set of strings including flight connection (i, j)
P _ij	set of pairings including flight connection (i, j)
Variables (cont.)
x _r	= 1, if route r is selected; = 0, otherwise.
	$∑ r ∈ R i j x r − ∑ p ∈ P i j x p ≥ 0$	$∀ (i, j) ∈ C$	(5.1)

Sets (cont.)
P	set of solutions to ARP, indexed by q
P _ij	set of solutions including flight connection (i, j)
Variables (cont.)
x _q	= 1, if solution q is selected; = 0, otherwise.
	$∑ θ ∈ Π i j x θ − ∑ p ∈ P i j x p ≥ 0$	$∀ (i, j) ∈ C$	(5.2)

1	J Abara (1989). Applying integer linear programming to the fleet assignment problem. Interfaces, 19(4): 20–28 https://doi.org/10.1287/inte.19.4.20
2	AEINFO (2016). Aircraft maintenance checks.
3	Y Ageeva (2000). Approaches to Incorporating Robustness into Airline Scheduling. Dissertation for the Master’s Degree. Cambridge: Massachusetts Institute of Technology
4	AGIFORS (2019). Delivering operations research and analytics innovation.
5	S AhmadBeygi, A Cohn, M Weir (2009). An integer programming approach to generating airline crew pairings. Computers & Operations Research, 36(4): 1284–1298 https://doi.org/10.1016/j.cor.2008.02.001
6	AINonline (2017). Chinese airlines need 5000 pilots per year in next 20 years.
7	Airbus (2018). Airbus 2018 price list press release.
8	D Antunes, V Vaze, A P Antunes (2019). A robust pairing model for airline crew scheduling. Transportation Science, 53(6): 1751–1771 https://doi.org/10.1287/trsc.2019.0897
9	J P Arabeyre, J Fearnley, F C Steiger, W Teather (1969). The airline crew scheduling problem: A survey. Transportation Science, 3(2): 140–163 https://doi.org/10.1287/trsc.3.2.140
10	Aviation Enthusiasts (2019a). Aircraft maintenance A check.
11	Aviation Enthusiasts (2019b). Aircraft maintenance B check.
12	C Barnhart, P Belobaba, A R Odoni (2003a). Applications of operations research in the air transport industry. Transportation Science, 37(4): 368–391 https://doi.org/10.1287/trsc.37.4.368.23276
13	C Barnhart, N L Boland, L W Clarke, E L Johnson, G L Nemhauser, R G Shenoi (1998). Flight string models for aircraft fleeting and routing. Transportation Science, 32(3): 208–220 https://doi.org/10.1287/trsc.32.3.208
14	C Barnhart, A Cohn (2004). Airline schedule planning: Accomplishments and opportunities. Manufacturing & Service Operations Management, 6(1): 3–22 https://doi.org/10.1287/msom.1030.0018
15	C Barnhart, A M Cohn, E L Johnson, D Klabjan, G L Nemhauser, P H Vance (2003b). Airline crew scheduling. In: Handbook of Transportation Science. Boston, MA: Springer, 517–560
16	C Barnhart, A Farahat, M Lohatepanont (2009). Airline fleet assignment with enhanced revenue modeling. Operations Research, 57(1): 231–244 https://doi.org/10.1287/opre.1070.0503
17	C Barnhart, L Hatay, E L Johnson (1995). Deadhead selection for the long-haul crew pairing problem. Operations Research, 43(3): 491–499 https://doi.org/10.1287/opre.43.3.491
18	C Barnhart, T S Kniker, M Lohatepanont (2002). Itinerary-based airline fleet assignment. Transportation Science, 36(2): 199–217 https://doi.org/10.1287/trsc.36.2.199.566
19	C Barnhart, R G Shenoi (1998). An approximate model and solution approach for the long-haul crew pairing problem. Transportation Science, 32(3): 221–231 https://doi.org/10.1287/trsc.32.3.221
20	C Barnhart, B Smith (2012). Quantitative Problem Solving Methods in the Airline Industry: A Modeling Methodology Handbook. Boston, MA: Springer
21	M Başdere, Ü Bilge (2014). Operational aircraft maintenance routing problem with remaining time consideration. European Journal of Operational Research, 235(1): 315–328 https://doi.org/10.1016/j.ejor.2013.10.066
22	N Bélanger, G Desaulniers, F Soumis, J Desrosiers (2006a). Periodic airline fleet assignment with time windows, spacing constraints, and time dependent revenues. European Journal of Operational Research, 175(3): 1754–1766 https://doi.org/10.1016/j.ejor.2004.04.051
23	N Bélanger, G Desaulniers, F Soumis, J Desrosiers, J Lavigne (2006b). Weekly airline fleet assignment with homogeneity. Transportation Research Part B: Methodological, 40(4): 306–318 https://doi.org/10.1016/j.trb.2005.03.004
24	P Belobaba, A Odoni, C Barnhart (2009). The Global Airline Industry. West Sussex: John Wiley & Sons
25	M E Berge, C A Hopperstad (1993). Demand driven dispatch: A method for dynamic aircraft capacity assignment, models and algorithms. Operations Research, 41(1): 153–168 https://doi.org/10.1287/opre.41.1.153
26	Boeing (2019a). Commercial market outlook 2019–2038.
27	Boeing (2019b). Pilot & technician outlook 2019–2038.
28	E K Burke, P de Causmaecker, G de Maere, J Mulder, M Paelinck, G Vanden Berghe (2010). A multi-objective approach for robust airline scheduling. Computers & Operations Research, 37(5): 822–832 https://doi.org/10.1016/j.cor.2009.03.026
29	V Cacchiani, J J Salazar-González (2017). Optimal solutions to a real-world integrated airline scheduling problem. Transportation Science, 51(1): 250–268 https://doi.org/10.1287/trsc.2015.0655
30	V Cacchiani, J J Salazar-González (2020). Heuristic approaches for flight retiming in an integrated airline scheduling problem of a regional carrier. Omega, 91: 102028 https://doi.org/10.1016/j.omega.2019.01.006
31	L Cadarso, R de Celis (2017). Integrated airline planning: Robust update of scheduling and fleet balancing under demand uncertainty. Transportation Research Part C: Emerging Technologies, 81: 227–245 https://doi.org/10.1016/j.trc.2017.06.003
32	P Cappanera, G Gallo (2004). A multicommodity flow approach to the crew rostering problem. Operations Research, 52(4): 583–596 https://doi.org/10.1287/opre.1040.0110
33	L Clarke, C Hane, E Johnson, G Nemhauser (1996). Maintenance and crew considerations in fleet assignment. Transportation Science, 30(3): 249–260 https://doi.org/10.1287/trsc.30.3.249
34	L Clarke, E Johnson, G Nemhauser, Z Zhu (1997). The aircraft rotation problem. Annals of Operations Research, 69: 33–46 https://doi.org/10.1023/A:1018945415148
35	A M Cohn, C Barnhart (2003). Improving crew scheduling by incorporating key maintenance routing decisions. Operations Research, 51(3): 387–396 https://doi.org/10.1287/opre.51.3.387.14759
36	J F Cordeau, G Stojković, F Soumis, J Desrosiers (2001). Benders’ decomposition for simultaneous aircraft routing and crew scheduling. Transportation Science, 35(4): 375–388 https://doi.org/10.1287/trsc.35.4.375.10432
37	M S Daskin, N D Panayotopoulos (1989). An Llagrangian relaxation approach to assigning aircraft to routes in hub and spoke networks. Transportation Science, 23(2): 91–99 https://doi.org/10.1287/trsc.23.2.91
38	H Dawid, J König, C Strauss (2001). An enhanced rostering model for airline crews. Computers & Operations Research, 28(7): 671–688 https://doi.org/10.1016/S0305-0548(00)00002-2
39	M Deveci, N C Demirel (2015). Airline crew pairing problem: A literature review. In: 11th International Scientific Conference on Economic and Social Development—Building Resilient Society. Zagreb, Croatia: Varazdin Development and Entrepreneurship Agency (VADEA), 103–111
40	T Doi, T Nishi, S Voß (2018). Two-level decomposition-based matheuristic for airline crew rostering problems with fair working time. European Journal of Operational Research, 267(2): 428–438 https://doi.org/10.1016/j.ejor.2017.11.046
41	M Dunbar, G Froyland, C L Wu (2012). Robust airline schedule planning: Minimizing propagated delay in an integrated routing and crewing framework. Transportation Science, 46(2): 204–216 https://doi.org/10.1287/trsc.1110.0395
42	M Dunbar, G Froyland, C L Wu (2014). An integrated scenario-based approach for robust aircraft routing, crew pairing and re-timing. Computers & Operations Research, 45: 68–86 https://doi.org/10.1016/j.cor.2013.12.003
43	A E E Eltoukhy, F T S Chan, S H Chung (2017). Airline schedule planning: A review and future directions. Industrial Management & Data Systems, 117(6): 1201–1243
44	A Farkas (1996). The Influence of Network Effects and Yield Management on Airline Fleet Assignment Decisions. Dissertation for the Doctoral Degree. Cambridge: Massachusetts Institute of Technology
45	Federal Aviation Administration (2019). Emergency equipment: Extended overwater operations.
46	T A Feo, J F Bard (1989). Flight scheduling and maintenance base planning. Management Science, 35(12): 1415–1432 https://doi.org/10.1287/mnsc.35.12.1415
47	G Froyland, S J Maher, C L Wu (2014). The recoverable robust tail assignment problem. Transportation Science, 48(3): 351–372 https://doi.org/10.1287/trsc.2013.0463
48	P Gall (2018). The US is facing a serious shortage of airline pilots. The Conversation. CNN Travel
49	M Gamache, F Soumis, G Marquis, J Desrosiers (1999). A column generation approach for large-scale aircrew rostering problems. Operations Research, 47(2): 247–263 https://doi.org/10.1287/opre.47.2.247
50	C Gao, E Johnson, B Smith (2009). Integrated airline fleet and crew robust planning. Transportation Science, 43(1): 2–16 https://doi.org/10.1287/trsc.1080.0257
51	D Goldman (2019). Airlines are on pace for their worst year since 2014. CNN Business
52	B Gopalakrishnan, E L Johnson (2005). Airline crew scheduling: State-of-the-art . Annals of Operations Research, 140(1): 305–337 https://doi.org/10.1007/s10479-005-3975-3
53	R Gopalan, K T Talluri (1998). The aircraft maintenance routing problem. Operations Research, 46(2): 260–271 https://doi.org/10.1287/opre.46.2.260
54	Y Guo, T Mellouli, L Suhl, M P Thiel (2006). A partially integrated airline crew scheduling approach with time-dependent crew capacities and multiple home bases. European Journal of Operational Research, 171(3): 1169–1181 https://doi.org/10.1016/j.ejor.2005.01.024
55	C A Hane, C Barnhart, E L Johnson, R E Marsten, G L Nemhauser, G Sigismondi (1995). The fleet assignment problem: Solving a large-scale integer program. Mathematical Programming, 70(1–3): 211–232 https://doi.org/10.1007/BF01585938
56	M Haouari, N Aissaoui, F Zeghal Mansour (2009). Network flow-based approaches for integrated aircraft fleeting and routing. European Journal of Operational Research, 193(2): 591–599 https://doi.org/10.1016/j.ejor.2007.11.042
57	M Haouari, S Shao, H D Sherali (2013). A lifted compact formulation for the daily aircraft maintenance routing problem. Transportation Science, 47(4): 508–525 https://doi.org/10.1287/trsc.1120.0433
58	M Haouari, H D Sherali, F Zeghal Mansour, N Aissaoui (2011). Exact approaches for integrated aircraft fleeting and routing at TunisAir. Computational Optimization and Applications, 49(2): 213–239 https://doi.org/10.1007/s10589-009-9292-z
59	M Haouari, F Zeghal Mansour, H D Sherali (2019). A new compact formulation for the daily crew pairing problem. Transportation Science, 53(3): 811–828 https://doi.org/10.1287/trsc.2018.0860
60	J Hessburg (2000). What’s this ‘A’ check, ‘C’ check stuff?
61	K L Hoffman, M Padberg (1993). Solving airline crew scheduling problems by branch-and-cut. Management Science, 39(6): 657–682 https://doi.org/10.1287/mnsc.39.6.657
62	IATA (2018). Economic performance of the airline industry. IATA Economics Report
63	IATA (2019). Air passenger demand 2018—infographic.
64	ICAO (2019). Fatigue management.
65	ICAO (2018). Long-term traffic forecasts—passenger and cargo.
66	INFORMS (2019). About the aviation applications section.
67	I Ioachim, J Desrosiers, F Soumis, N Bélanger (1999). Fleet assignment and routing with schedule synchronization constraints. European Journal of Operational Research, 119(1): 75–90 https://doi.org/10.1016/S0377-2217(98)00343-9
68	S Irnich, G Desaulniers (2005). Shortest path problems with resource constraints. In: Desaulniers G, Desrosiers J, Solomon M M, eds. Column Generation. Boston, MA: Springer, 33–65
69	T L Jacobs, B C Smith, E L Johnson (2008). Incorporating network flow effects into the airline fleet assignment process. Transportation Science, 42(4): 514–529 https://doi.org/10.1287/trsc.1080.0242
70	A Kasirzadeh, M Saddoune, F Soumis (2017). Airline crew scheduling: Models, algorithms, and data sets. EURO Journal on Transportation and Logistics, 6(2): 111–137
71	N Kenan, A Jebali, A Diabat (2018). The integrated aircraft routing problem with optional flights and delay considerations. Transportation Research Part E: Logistics and Transportation Review, 118: 355–375 https://doi.org/10.1016/j.tre.2018.08.002
72	G Keysan, G L Nemhauser, M W P Savelsbergh (2010). Tactical and operational planning of scheduled maintenance for per-seat, on-demand air transportation. Transportation Science, 44(3): 291–306 https://doi.org/10.1287/trsc.1090.0311
73	O Khaled, M Minoux, V Mousseau, S Michel, X Ceugniet (2018). A compact optimization model for the tail assignment problem. European Journal of Operational Research, 264(2): 548–557 https://doi.org/10.1016/j.ejor.2017.06.045
74	D Klabjan, E L Johnson, G L Nemhauser, E Gelman, S Ramaswamy (2001). Airline crew scheduling with regularity. Transportation Science, 35(4): 359–374 https://doi.org/10.1287/trsc.35.4.359.10437
75	D Klabjan, E L Johnson, G L Nemhauser, E Gelman, S Ramaswamy (2002). Airline crew scheduling with time windows and plane-count constraints. Transportation Science, 36(3): 337–348 https://doi.org/10.1287/trsc.36.3.337.7831
76	N Kohl, S E Karisch (2004). Airline crew rostering: Problem types, modeling, and optimization. Annals of Operations Research, 127(1–4): 223–257 https://doi.org/10.1023/B:ANOR.0000019091.54417.ca
77	S Lan, J P Clarke, C Barnhart (2006). Planning for robust airline operations: Optimizing aircraft routings and flight departure times to minimize passenger disruptions. Transportation Science, 40(1): 15–28 https://doi.org/10.1287/trsc.1050.0134
78	Z Liang, W A Chaovalitwongse (2013). A network-based model for the integrated weekly aircraft maintenance routing and fleet assignment problem. Transportation Science, 47(4): 493–507 https://doi.org/10.1287/trsc.1120.0434
79	Z Liang, W A Chaovalitwongse, H C Huang, E L Johnson (2011). On a new rotation tour network model for aircraft maintenance routing problem. Transportation Science, 45(1): 109–120 https://doi.org/10.1287/trsc.1100.0338
80	Z Liang, Y Feng, X Zhang, T Wu, W A Chaovalitwongse (2015). Robust weekly aircraft maintenance routing problem and the extension to the tail assignment problem. Transportation Research Part B: Methodological, 78: 238–259 https://doi.org/10.1016/j.trb.2015.03.013
81	Z Liang, F Xiao, X Qian, L Zhou, X Jin, X Lu, S Karichery (2018). A column generation-based heuristic for aircraft recovery problem with airport capacity constraints and maintenance flexibility. Transportation Research Part B: Methodological, 113: 70–90 https://doi.org/10.1016/j.trb.2018.05.007
82	M Lohatepanont, C Barnhart (2004). Airline schedule planning: Integrated models and algorithms for schedule design and fleet assignment. Transportation Science, 38(1): 19–32 https://doi.org/10.1287/trsc.1030.0026
83	B Maenhout, M Vanhoucke (2010). A hybrid scatter search heuristic for personalized crew rostering in the airline industry. European Journal of Operational Research, 206(1): 155–167 https://doi.org/10.1016/j.ejor.2010.01.040
84	S J Maher, G Desaulniers, F Soumis (2018). The daily tail assignment problem under operational uncertainty using look-ahead maintenance constraints. European Journal of Operational Research, 264(2): 534–547 https://doi.org/10.1016/j.ejor.2017.06.041
85	E Mazareanu (2019). Air transportation—statistics & facts.
86	A Mercier, J F Cordeau, F Soumis (2005). A computational study of Benders’ decomposition for the integrated aircraft routing and crew scheduling problem. Computers & Operations Research, 32(6): 1451–1476 https://doi.org/10.1016/j.cor.2003.11.013
87	N Papadakos (2009). Integrated airline scheduling. Computers & Operations Research, 36(1): 176–195 https://doi.org/10.1016/j.cor.2007.08.002
88	PEA (2019). What do airline pilots earn?
89	V L Pilla, J M Rosenberger, V Chen, N Engsuwan, S Siddappa (2012). A multivariate adaptive regression splines cutting plane approach for solving a two-stage stochastic programming fleet assignment model. European Journal of Operational Research, 216(1): 162–171 https://doi.org/10.1016/j.ejor.2011.07.008
90	V L Pilla, J M Rosenberger, V C P Chen, B Smith (2008). A statistical computer experiments approach to airline fleet assignment. IIE Transactions, 40(5): 524–537 https://doi.org/10.1080/07408170701759734
91	J P Pita, N Adler, A P Antunes (2014). Socially-oriented flight scheduling and fleet assignment model with an application to Norway. Transportation Research Part B: Methodological, 61: 17–32 https://doi.org/10.1016/j.trb.2013.12.006
92	J P Pita, C Barnhart, A P Antunes (2013). Integrated flight scheduling and fleet assignment under airport congestion. Transportation Science, 47(4): 477–492 https://doi.org/10.1287/trsc.1120.0442
93	Qantas (2016). The A, C and D of aircraft maintenance.
94	B Rexing, C Barnhart, T Kniker, A Jarrah, N Krishnamurthy (2000). Airline fleet assignment with time windows. Transportation Science, 34(1): 1–20 https://doi.org/10.1287/trsc.34.1.1.12277
95	J M Rosenberger, E L Johnson, G L Nemhauser (2004). A robust fleet-assignment model with hub isolation and short cycles. Transportation Science, 38(3): 357–368 https://doi.org/10.1287/trsc.1030.0038
96	R A Rushmeier, S A Kontogiorgis (1997). Advances in the optimization of airline fleet assignment. Transportation Science, 31(2): 159–169 https://doi.org/10.1287/trsc.31.2.159
97	S Ruther, N Boland, F G Engineer, I Evans (2017). Integrated aircraft routing, crew pairing, and tail assignment: Branch-and-price with many pricing problems. Transportation Science, 51(1): 177–195 https://doi.org/10.1287/trsc.2015.0664
98	M Saddoune, G Desaulniers, I Elhallaoui, F Soumis (2012). Integrated airline crew pairing and crew assignment by dynamic constraint aggregation. Transportation Science, 46(1): 39–55 https://doi.org/10.1287/trsc.1110.0379
99	M Saddoune, G Desaulniers, F Soumis (2013). Aircrew pairings with possible repetitions of the same flight number. Computers & Operations Research, 40(3): 805–814 https://doi.org/10.1016/j.cor.2010.11.003
100	N Safaei, A K S Jardine (2018). Aircraft routing with generalized maintenance constraints. Omega, 80: 111–122 https://doi.org/10.1016/j.omega.2017.08.013
101	J J Salazar-González (2014). Approaches to solve the fleet-assignment, aircraft-routing, crew-pairing and crew-rostering problems of a regional carrier. Omega, 43: 71–82 https://doi.org/10.1016/j.omega.2013.06.006
102	R Sandhu, D Klabjan (2007). Integrated airline fleeting and crew-pairing decisions. Operations Research, 55(3): 439–456 https://doi.org/10.1287/opre.1070.0395
103	A Sarac, R Batta, C M Rump (2006). A branch-and-price approach for operational aircraft maintenance routing. European Journal of Operational Research, 175(3): 1850–1869 https://doi.org/10.1016/j.ejor.2004.10.033
104	P Seidenman, D J Spanovich (2018). Airlines reevaluate phased A checks: The changing dynamics of the $13 billion a year line maintenance segment.
105	S Shao, H D Sherali, M Haouari (2017). A novel model and decomposition approach for the integrated airline fleet assignment, aircraft routing, and crew pairing problem. Transportation Science, 51(1): 233–249 https://doi.org/10.1287/trsc.2015.0623
106	S Shebalov, D Klabjan (2006). Robust airline crew pairing: Move-up crews. Transportation Science, 40(3): 300–312
107	H D Sherali, K H Bae, M Haouari (2010). Integrated airline schedule design and fleet assignment: Polyhedral analysis and Benders’ decomposition approach. INFORMS Journal on Computing, 22(4): 500–513 https://doi.org/10.1287/ijoc.1090.0368
108	H D Sherali, K H Bae, M Haouari (2013a). An integrated approach for airline flight selection and timing, fleet assignment, and aircraft routing. Transportation Science, 47(4): 455–476 https://doi.org/10.1287/trsc.2013.0460
109	H D Sherali, K H Bae, M Haouari (2013b). A Benders’ decomposition approach for an integrated airline schedule design and fleet assignment problem with flight retiming, schedule balance, and demand recapture. Annals of Operations Research, 210(1): 213–244 https://doi.org/10.1007/s10479-011-0906-3
110	H D Sherali, E K Bish, X Zhu (2006). Airline fleet assignment concepts, models, and algorithms. European Journal of Operational Research, 172(1): 1–30 https://doi.org/10.1016/j.ejor.2005.01.056
111	B C Smith, E L Johnson (2006). Robust airline fleet assignment: Imposing station purity using station decomposition. Transportation Science, 40(4): 497–516 https://doi.org/10.1287/trsc.1060.0153
112	N Souai, J Teghem (2009). Genetic algorithm based approach for the integrated airline crew-pairing and rostering problem. European Journal of Operational Research, 199(3): 674–683 https://doi.org/10.1016/j.ejor.2007.10.065
113	C Sriram, A Haghani (2003). An optimization model for aircraft maintenance scheduling and re-assignment. Transportation Research Part A: Policy and Practice, 37(1): 29–48 https://doi.org/10.1016/S0965-8564(02)00004-6
114	M Stojković, F Soumis (2001). An optimization model for the simultaneous operational flight and pilot scheduling problem. Management Science, 47(9): 1290–1305 https://doi.org/10.1287/mnsc.47.9.1290.9780
115	R Subramanian, R P Scheff, J D Quillinan, D S Wiper, R E Marsten (1994). Coldstart: Fleet assignment at Delta air lines. Interfaces, 24(1): 104–120 https://doi.org/10.1287/inte.24.1.104
116	K T Talluri (1998). The four-day aircraft maintenance routing problem. Transportation Science, 32(1): 43–53 https://doi.org/10.1287/trsc.32.1.43
117	P H Vance, C Barnhart, E L Johnson, G L Nemhauser (1997). Airline crew scheduling: A new formulation and decomposition algorithm. Operations Research, 45(2): 188–200 https://doi.org/10.1287/opre.45.2.188
118	K Wei, V Vaze (2018). Modeling crew itineraries and delays in the national air transportation system. Transportation Science, 52(5): 1276–1296 https://doi.org/10.1287/trsc.2018.0834
119	O Weide, D Ryan, M Ehrgott (2010). An iterative approach to robust and integrated aircraft routing and crew scheduling. Computers & Operations Research, 37(5): 833–844 https://doi.org/10.1016/j.cor.2009.03.024
120	C Yan, J Kung (2018). Robust aircraft routing. Transportation Science, 52(1): 118–133 https://doi.org/10.1287/trsc.2015.0657
121	S Yan, C H Tseng (2002). A passenger demand model for airline flight scheduling and fleet routing. Computers & Operations Research, 29(11): 1559–1581 https://doi.org/10.1016/S0305-0548(01)00046-6
122	J W Yen, J R Birge (2006). A stochastic programming approach to the airline crew scheduling problem. Transportation Science, 40(1): 3–14 https://doi.org/10.1287/trsc.1050.0138
123	F Zeghal Mansour, M Haouari, H D Sherali, N Aissaoui (2011). Flexible aircraft fleeting and routing at TunisAir. Journal of the Operational Research Society, 62(2): 368–380 https://doi.org/10.1057/jors.2010.100
124	V Zeighami, F Soumis (2019). Combining Benders’ decomposition and column generation for integrated crew pairing and personalized crew assignment problems. Transportation Science, 53(5): 1479–1499 https://doi.org/10.1287/trsc.2019.0892

Viewed

Full text

Abstract

Cited

Shared

Discussed