Skip to main content
Log in

Flexible aircraft fleeting and routing at TunisAir

  • Special Issue Paper
  • Published:
Journal of the Operational Research Society

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Figure 1

References

  • Abara J (1989). Applying integer programming to the fleet assignment problem. Interfaces 19 (4): 20–28.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • Bartholomew-Biggs MC, Parkhurst SC and Wilson SP (2003). Global optimization approaches to an aircraft routing problem. Eur J Opl Res 146: 417–431.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • Clarke LW, Hane C, Johnson EL and Nemhauser GL (1996). Maintenance and crew considerations in fleet assignment. Transport Sci 30: 249–260.

    Article  Google Scholar 

  • Clarke LW, Johnson EL, Nemhauser GL and Zhu Z (1997). The aircraft rotation problem. Ann Opns Res 69: 33–46.

    Article  Google Scholar 

  • Cohn AM and Barnhart C (2003). Improving crew scheduling by incorporating key maintenance routing decisions. Opns Res 51: 387–393.

    Article  Google Scholar 

  • Cook WJ, Cunningham WH, Pulleyblank WR and Schrijver A (1998). Combinatorial Optimization. John Wiley: New York.

    Google Scholar 

  • Cordeau JF, Stojkovic G, Soumis F and Desrosiers J (2001). Benders decomposition for simultaneous aircraft routing and crew scheduling. Transport Sci 35: 375–388.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • Desaulniers G, Desrosiers J, Dumas Y, Solomon M and Soumis F (1997). Daily aircraft routing and scheduling. Mngt Sci 43: 841–855.

    Article  Google Scholar 

  • 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.

    Chapter  Google Scholar 

  • Feo TA and Bard JF (1989). Flight scheduling and maintenance base planning. Mngt Sci 35: 1414–1432.

    Article  Google Scholar 

  • Ghoniem A and Sherali HD (2009). Complementary column generation and bounding approaches for set partitioning formulations. Optim Lett 3: 123–136.

    Article  Google Scholar 

  • Gopalan R and Talluri KT (1998). The aircraft maintenance routing problem. Opns Res 46: 260–271.

    Article  Google Scholar 

  • Gu Z, Johnson EL, Nemhauser GL and Wang Y (1994). Some properties of the fleet assignment problem. Opns Res Lett 15: 59–71.

    Article  Google Scholar 

  • 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.

    Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • Levin A (1971). Scheduling and fleet routing models for transportation systems. Transport Sci 5: 233–255.

    Article  Google Scholar 

  • Li Y and Wang X (2005). Integration of fleet assignment and aircraft routing. Transport Res Rec 1915: 79–84.

    Article  Google Scholar 

  • Mercier A and Soumis F (2007). An integrated aircraft routing, crew scheduling and flight retiming model. Comput Opns Res 34: 2251–2265.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • Rexing B, Barnhart C, Kniker T, Jarrah A and Krishnamurthy N (2000). Airline fleet assignment with time windows. Transport Sci 34: 1–20.

    Article  Google Scholar 

  • Rushmeier R and Kontogiorgis S (1997). Advances in the optimization of airline fleet assignment. Transport Sci 31: 159–169.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • Sherali HD, Bish EK and Zhu X (2006). Airline fleet assignment concepts, models, and algorithms. Eur J Opl Res 172: 1–30.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • Talluri K (1996). Swapping applications in a daily airline fleet assignment. Transport Sci 30: 237–248.

    Article  Google Scholar 

  • Talluri K (1998). The four-day aircraft maintenance routing problem. Transport Sci 32: 43–53.

    Article  Google Scholar 

Download references

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

Authors

Rights and permissions

Reprints 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

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1057/jors.2010.100

Keywords

Navigation