Abstract
This paper addresses a Flexible Aircraft Fleeting and Routing Problem, which is motivated by the Tunisian national carrier TunisAir. A solution to this problem specifies the departure time of each flight, the subset of aircraft to be chartered or rented out, the individual aircraft assigned to each flight, as well as the sequence of flights to be flown by each aircraft. The objective is to maximize the expected total net profit, while satisfying activity constraints and long-term maintenance requirements. Tailored optimization-based heuristics are developed for solving this complex integrated problem. Computational experiments conducted on real data demonstrate that the proposed procedures are effective and robust, and significantly improve upon TunisAir's solutions.
References
Abara J (1989). Applying integer programming to the fleet assignment problem. Interfaces 19 (4): 20–28.
Barnhart C, Boland NL, Clarke LW, Johnson EL, Nemhauser GL and Shenoi RG (1998). Flight string models for aircraft fleeting and routing. Transport Sci 32: 208–220.
Bartholomew-Biggs MC, Parkhurst SC and Wilson SP (2003). Global optimization approaches to an aircraft routing problem. Eur J Opl Res 146: 417–431.
Bélanger N, Desaulniers G, Soumis F and Desrosiers J (2006). Periodic airline fleet assignment with time windows, spacing constraints, and time dependent revenues. Eur J Opl Res 175: 1757–1766.
Clarke LW, Hane C, Johnson EL and Nemhauser GL (1996). Maintenance and crew considerations in fleet assignment. Transport Sci 30: 249–260.
Clarke LW, Johnson EL, Nemhauser GL and Zhu Z (1997). The aircraft rotation problem. Ann Opns Res 69: 33–46.
Cohn AM and Barnhart C (2003). Improving crew scheduling by incorporating key maintenance routing decisions. Opns Res 51: 387–393.
Cook WJ, Cunningham WH, Pulleyblank WR and Schrijver A (1998). Combinatorial Optimization. John Wiley: New York.
Cordeau JF, Stojkovic G, Soumis F and Desrosiers J (2001). Benders decomposition for simultaneous aircraft routing and crew scheduling. Transport Sci 35: 375–388.
Daskin MS and Panayotopoulos ND (1989). A Lagrangian relaxation approach to assigning aricraft to routes in hub and spoke networks. Transport Sci 23: 91–99.
Desaulniers G, Desrosiers J, Dumas Y, Solomon M and Soumis F (1997). Daily aircraft routing and scheduling. Mngt Sci 43: 841–855.
Desrosiers J and Lübbecke ME (2005). A primer in column generation. In: Desaulniers G, Desrosiers J and Solomon M (eds). Column Generation 2005. Springer: New York, pp 1–32.
Feo TA and Bard JF (1989). Flight scheduling and maintenance base planning. Mngt Sci 35: 1414–1432.
Ghoniem A and Sherali HD (2009). Complementary column generation and bounding approaches for set partitioning formulations. Optim Lett 3: 123–136.
Gopalan R and Talluri KT (1998). The aircraft maintenance routing problem. Opns Res 46: 260–271.
Gu Z, Johnson EL, Nemhauser GL and Wang Y (1994). Some properties of the fleet assignment problem. Opns Res Lett 15: 59–71.
Hane CA, Barnhart C, Johnson EL, Marsten RE, Nemhauser GL and Sigismondi G (1995). The fleet assignment problem: Solving a large-scale integer program. Math Program 70: 211–232.
Haouari M, Aissaoui N and Zeghal FM (2009). Network flow-based approaches for integrated aircraft fleeting and routing. Eur J Opl Res 193: 591–599.
Ioachim I, Desrosiers J, Soumis F and Bélanger N (1999). Fleet assignment and routing with schedule synchronization constraints. Eur J Opl Res 119: 75–90.
Kabbani NM and Patty BW (1992). Aircraft routing at American airlines. Proceedings of the Thirty-Second Annual Symposium of AGIFORS. AGIFORS: Budapest.
Klabjan D, Johnson EL and Nemhauser GL (2002). Airline crew scheduling with time windows and plane-count constraints. Transport Sci 36: 337–348.
Levin A (1971). Scheduling and fleet routing models for transportation systems. Transport Sci 5: 233–255.
Li Y and Wang X (2005). Integration of fleet assignment and aircraft routing. Transport Res Rec 1915: 79–84.
Mercier A and Soumis F (2007). An integrated aircraft routing, crew scheduling and flight retiming model. Comput Opns Res 34: 2251–2265.
Mercier A, Cordeau JF and Soumis F (2005). A computational study of Benders decomposition for the integrated aircraft routing and crew scheduling problem. Comput Opns Res 32: 1451–1476.
Rexing B, Barnhart C, Kniker T, Jarrah A and Krishnamurthy N (2000). Airline fleet assignment with time windows. Transport Sci 34: 1–20.
Rushmeier R and Kontogiorgis S (1997). Advances in the optimization of airline fleet assignment. Transport Sci 31: 159–169.
Secomandi N (2008). An analysis of the control-algorithm re-solving issue in inventory and revenue management. M&SOM-Manuf Serv Op 10: 468–483.
Sherali HD, Bish EK and Zhu X (2006). Airline fleet assignment concepts, models, and algorithms. Eur J Opl Res 172: 1–30.
Sherali HD, Bae KH and Haouari M (2010). Integrated airline schedule design and fleet assignment: Polyhedral analysis and benders decomposition approach. INFORMS J Comput, Doi: 10.1287/ijoc.1090.0368.
Subramanian R, Scheff RP, Quillinan JD, Wiper DS and Marsten RE (1994). Cold-start: Fleet assignment at Delta Air Lines. Interfaces 24 (1): 104–120.
Talluri K (1996). Swapping applications in a daily airline fleet assignment. Transport Sci 30: 237–248.
Talluri K (1998). The four-day aircraft maintenance routing problem. Transport Sci 32: 43–53.
Acknowledgements
This research has been supported in part by the National Science Foundation under Grant No. CMMI-0754236. The authors would like to thank Mr. Kamel Berrima, Director of Operations Control Center at TunisAir, for his input on the problem and for providing the data. The authors also thank two anonymous referees for their insightful comments that have helped improve the presentation in this paper.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Zeghal, F., Haouari, M., Sherali, H. et al. Flexible aircraft fleeting and routing at TunisAir . J Oper Res Soc 62, 368–380 (2011). https://doi.org/10.1057/jors.2010.100
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/jors.2010.100