IDEAS home Printed from https://ideas.repec.org/a/eee/jomega/v93y2020ics0305048317306837.html
   My bibliography  Save this article

Aircraft routing and crew pairing: Updated algorithms at Air France

Author

Listed:
  • Parmentier, Axel
  • Meunier, Frédéric

Abstract

Aircraft routing and crew pairing problems aim at building the sequences of flight legs operated respectively by airplanes and by crews of an airline. Given their impact on airlines operating costs, both have been extensively studied for decades. Our goal is to provide reliable and easy to maintain frameworks for both problems at Air France. We propose simple approaches to deal with Air France current setting. For routing, we introduce an exact compact IP formulation that can be solved to optimality by current MIP solvers in at most a few minutes even on Air France largest instances. Regarding crew pairing, we provide a methodology to model the column generation pricing subproblem within a new resource constrained shortest path framework recently introduced by the first author. This new framework, which can be used as a black-box, leverages on bounds to discard partial solutions and speed-up the resolution. The resulting approach enables to solve to optimality Air France largest instances. Recent literature has focused on integrating aircraft routing and crew pairing problems. As a side result, we are able to solve to near optimality large industrial instances of the integrated problem by combining the aforementioned algorithms within a simple cut generating method.

Suggested Citation

  • Parmentier, Axel & Meunier, Frédéric, 2020. "Aircraft routing and crew pairing: Updated algorithms at Air France," Omega, Elsevier, vol. 93(C).
    • Handle: RePEc:eee:jomega:v:93:y:2020:i:c:s0305048317306837
    DOI: 10.1016/j.omega.2019.05.009
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0305048317306837
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.omega.2019.05.009?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Desaulniers, G. & Desrosiers, J. & Dumas, Y. & Marc, S. & Rioux, B. & Solomon, M. M. & Soumis, F., 1997. "Crew pairing at Air France," European Journal of Operational Research, Elsevier, vol. 97(2), pages 245-259, March.
    2. Shivaram Subramanian & Hanif D. Sherali, 2008. "An Effective Deflected Subgradient Optimization Scheme for Implementing Column Generation for Large-Scale Airline Crew Scheduling Problems," INFORMS Journal on Computing, INFORMS, vol. 20(4), pages 565-578, November.
    3. Ram Gopalan & Kalyan T. Talluri, 1998. "The Aircraft Maintenance Routing Problem," Operations Research, INFORMS, vol. 46(2), pages 260-271, April.
    4. Chu, Hai D. & Gelman, Eric & Johnson, Ellis L., 1997. "Solving large scale crew scheduling problems," European Journal of Operational Research, Elsevier, vol. 97(2), pages 260-268, March.
    5. Jean-François Cordeau & Goran Stojković & François Soumis & Jacques Desrosiers, 2001. "Benders Decomposition for Simultaneous Aircraft Routing and Crew Scheduling," Transportation Science, INFORMS, vol. 35(4), pages 375-388, November.
    6. Kalyan T. Talluri, 1998. "The Four-Day Aircraft Maintenance Routing Problem," Transportation Science, INFORMS, vol. 32(1), pages 43-53, February.
    7. Cynthia Barnhart & Rajesh G. Shenoi, 1998. "An Approximate Model and Solution Approach for the Long-Haul Crew Pairing Problem," Transportation Science, INFORMS, vol. 32(3), pages 221-231, August.
    8. Lloyd Clarke & Ellis Johnson & George Nemhauser & Zhongxi Zhu, 1997. "The aircraft rotation problem," Annals of Operations Research, Springer, vol. 69(0), pages 33-46, January.
    9. Balaji Gopalakrishnan & Ellis. Johnson, 2005. "Airline Crew Scheduling: State-of-the-Art," Annals of Operations Research, Springer, vol. 140(1), pages 305-337, November.
    10. Amy Mainville Cohn & Cynthia Barnhart, 2003. "Improving Crew Scheduling by Incorporating Key Maintenance Routing Decisions," Operations Research, INFORMS, vol. 51(3), pages 387-396, June.
    11. Pamela H. Vance & Cynthia Barnhart & Ellis L. Johnson & George L. Nemhauser, 1997. "Airline Crew Scheduling: A New Formulation and Decomposition Algorithm," Operations Research, INFORMS, vol. 45(2), pages 188-200, April.
    12. Shan Lan & John-Paul Clarke & Cynthia Barnhart, 2006. "Planning for Robust Airline Operations: Optimizing Aircraft Routings and Flight Departure Times to Minimize Passenger Disruptions," Transportation Science, INFORMS, vol. 40(1), pages 15-28, February.
    13. Villeneuve, Daniel & Desaulniers, Guy, 2005. "The shortest path problem with forbidden paths," European Journal of Operational Research, Elsevier, vol. 165(1), pages 97-107, August.
    14. Karla L. Hoffman & Manfred Padberg, 1993. "Solving Airline Crew Scheduling Problems by Branch-and-Cut," Management Science, INFORMS, vol. 39(6), pages 657-682, June.
    15. Diego Klabjan & Ellis L. Johnson & George L. Nemhauser & Eric Gelman & Srini Ramaswamy, 2002. "Airline Crew Scheduling with Time Windows and Plane-Count Constraints," Transportation Science, INFORMS, vol. 36(3), pages 337-348, August.
    16. Khaled, Oumaima & Minoux, Michel & Mousseau, Vincent & Michel, Stéphane & Ceugniet, Xavier, 2018. "A compact optimization model for the tail assignment problem," European Journal of Operational Research, Elsevier, vol. 264(2), pages 548-557.
    17. Thomas A. Feo & Jonathan F. Bard, 1989. "Flight Scheduling and Maintenance Base Planning," Management Science, INFORMS, vol. 35(12), pages 1415-1432, December.
    18. Michelle Dunbar & Gary Froyland & Cheng-Lung Wu, 2012. "Robust Airline Schedule Planning: Minimizing Propagated Delay in an Integrated Routing and Crewing Framework," Transportation Science, INFORMS, vol. 46(2), pages 204-216, May.
    19. Etschmaier, MM & Rothstein, M, 1974. "Operations research in the management of the airlines," Omega, Elsevier, vol. 2(2), pages 157-179, April.
    20. Stefan Irnich & Guy Desaulniers, 2005. "Shortest Path Problems with Resource Constraints," Springer Books, in: Guy Desaulniers & Jacques Desrosiers & Marius M. Solomon (ed.), Column Generation, chapter 0, pages 33-65, Springer.
    21. Cynthia Barnhart & Natashia L. Boland & Lloyd W. Clarke & Ellis L. Johnson & George L. Nemhauser & Rajesh G. Shenoi, 1998. "Flight String Models for Aircraft Fleeting and Routing," Transportation Science, INFORMS, vol. 32(3), pages 208-220, August.
    22. Cynthia Barnhart & Peter Belobaba & Amedeo R. Odoni, 2003. "Applications of Operations Research in the Air Transport Industry," Transportation Science, INFORMS, vol. 37(4), pages 368-391, November.
    23. Baker, Edward & Fisher, Michael, 1981. "Computational results for very large air crew scheduling problems," Omega, Elsevier, vol. 9(6), pages 613-618.
    24. Guy Desaulniers & Jacques Desrosiers & Yvan Dumas & Marius M. Solomon & François Soumis, 1997. "Daily Aircraft Routing and Scheduling," Management Science, INFORMS, vol. 43(6), pages 841-855, June.
    25. Lavoie, Sylvie & Minoux, Michel & Odier, Edouard, 1988. "A new approach for crew pairing problems by column generation with an application to air transportation," European Journal of Operational Research, Elsevier, vol. 35(1), pages 45-58, April.
    26. Safaei, Nima & Jardine, Andrew K.S., 2018. "Aircraft routing with generalized maintenance constraints," Omega, Elsevier, vol. 80(C), pages 111-122.
    27. Beasley, J. E. & Cao, B., 1996. "A tree search algorithm for the crew scheduling problem," European Journal of Operational Research, Elsevier, vol. 94(3), pages 517-526, November.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Pei, Zhi & Dai, Xu & Yuan, Yilun & Du, Rui & Liu, Changchun, 2021. "Managing price and fleet size for courier service with shared drones," Omega, Elsevier, vol. 104(C).
    2. Breugem, T. & van Rossum, B.T.C. & Dollevoet, T. & Huisman, D., 2022. "A column generation approach for the integrated crew re-planning problem," Omega, Elsevier, vol. 107(C).
    3. Glomb, Lukas & Liers, Frauke & Rösel, Florian, 2023. "Optimizing integrated aircraft assignment and turnaround handling," European Journal of Operational Research, Elsevier, vol. 310(3), pages 1051-1071.
    4. Weihao Ouyang & Xiaohong Zhu, 2023. "Meta-Heuristic Solver with Parallel Genetic Algorithm Framework in Airline Crew Scheduling," Sustainability, MDPI, vol. 15(2), pages 1-21, January.
    5. Ding, Chengjin & Chen, Xinyuan & Wu, Weiwei & Wei, Wenbin & Xin, Zelin, 2023. "Game-theoretic analysis of the impact of crew overnight hotel cost on airlines’ fleet assignment and crew pairing," Journal of Air Transport Management, Elsevier, vol. 113(C).
    6. Xu, Yifan & Adler, Nicole & Wandelt, Sebastian & Sun, Xiaoqian, 2024. "Competitive integrated airline schedule design and fleet assignment," European Journal of Operational Research, Elsevier, vol. 314(1), pages 32-50.
    7. Xu, Yifan & Wandelt, Sebastian & Sun, Xiaoqian, 2021. "Airline integrated robust scheduling with a variable neighborhood search based heuristic," Transportation Research Part B: Methodological, Elsevier, vol. 149(C), pages 181-203.
    8. Wen, Xin & Sun, Xuting & Sun, Yige & Yue, Xiaohang, 2021. "Airline crew scheduling: Models and algorithms," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 149(C).
    9. Park, Jongyoon & Han, Jinil & Lee, Kyungsik, 2022. "Integer Optimization Model and Algorithm for the Stem Cell Culturing Problem," Omega, Elsevier, vol. 108(C).
    10. Guy Desaulniers & François Lessard & Mohammed Saddoune & François Soumis, 2020. "Dynamic Constraint Aggregation for Solving Very Large-scale Airline Crew Pairing Problems," SN Operations Research Forum, Springer, vol. 1(3), pages 1-23, September.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Atoosa Kasirzadeh & Mohammed Saddoune & François Soumis, 2017. "Airline crew scheduling: models, algorithms, and data sets," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 6(2), pages 111-137, June.
    2. Hanif D. Sherali & Ki-Hwan Bae & Mohamed Haouari, 2013. "An Integrated Approach for Airline Flight Selection and Timing, Fleet Assignment, and Aircraft Routing," Transportation Science, INFORMS, vol. 47(4), pages 455-476, November.
    3. Mohamed Haouari & Farah Zeghal Mansour & Hanif D. Sherali, 2019. "A New Compact Formulation for the Daily Crew Pairing Problem," Transportation Science, INFORMS, vol. 53(3), pages 811-828, May.
    4. Chunhua Gao & Ellis Johnson & Barry Smith, 2009. "Integrated Airline Fleet and Crew Robust Planning," Transportation Science, INFORMS, vol. 43(1), pages 2-16, February.
    5. Jean-François Cordeau & Goran Stojković & François Soumis & Jacques Desrosiers, 2001. "Benders Decomposition for Simultaneous Aircraft Routing and Crew Scheduling," Transportation Science, INFORMS, vol. 35(4), pages 375-388, November.
    6. Vahid Zeighami & François Soumis, 2019. "Combining Benders’ Decomposition and Column Generation for Integrated Crew Pairing and Personalized Crew Assignment Problems," Transportation Science, INFORMS, vol. 53(5), pages 1479-1499, September.
    7. Zhe Liang & Wanpracha Art Chaovalitwongse, 2013. "A Network-Based Model for the Integrated Weekly Aircraft Maintenance Routing and Fleet Assignment Problem," Transportation Science, INFORMS, vol. 47(4), pages 493-507, November.
    8. Haouari, Mohamed & Aissaoui, Najla & Mansour, Farah Zeghal, 2009. "Network flow-based approaches for integrated aircraft fleeting and routing," European Journal of Operational Research, Elsevier, vol. 193(2), pages 591-599, March.
    9. Liang, Zhe & Feng, Yuan & Zhang, Xiaoning & Wu, Tao & Chaovalitwongse, Wanpracha Art, 2015. "Robust weekly aircraft maintenance routing problem and the extension to the tail assignment problem," Transportation Research Part B: Methodological, Elsevier, vol. 78(C), pages 238-259.
    10. Cynthia Barnhart & Peter Belobaba & Amedeo R. Odoni, 2003. "Applications of Operations Research in the Air Transport Industry," Transportation Science, INFORMS, vol. 37(4), pages 368-391, November.
    11. Başdere, Mehmet & Bilge, Ümit, 2014. "Operational aircraft maintenance routing problem with remaining time consideration," European Journal of Operational Research, Elsevier, vol. 235(1), pages 315-328.
    12. Sanchez, David Torres & Boyacı, Burak & Zografos, Konstantinos G., 2020. "An optimisation framework for airline fleet maintenance scheduling with tail assignment considerations," Transportation Research Part B: Methodological, Elsevier, vol. 133(C), pages 142-164.
    13. F M Zeghal & M Haouari & H D Sherali & N Aissaoui, 2011. "Flexible aircraft fleeting and routing at TunisAir," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(2), pages 368-380, February.
    14. Guy Desaulniers & François Lessard & Mohammed Saddoune & François Soumis, 2020. "Dynamic Constraint Aggregation for Solving Very Large-scale Airline Crew Pairing Problems," SN Operations Research Forum, Springer, vol. 1(3), pages 1-23, September.
    15. Mohammed Saddoune & Guy Desaulniers & Issmail Elhallaoui & François Soumis, 2012. "Integrated Airline Crew Pairing and Crew Assignment by Dynamic Constraint Aggregation," Transportation Science, INFORMS, vol. 46(1), pages 39-55, February.
    16. Mohamed Haouari & Shengzhi Shao & Hanif D. Sherali, 2013. "A Lifted Compact Formulation for the Daily Aircraft Maintenance Routing Problem," Transportation Science, INFORMS, vol. 47(4), pages 508-525, November.
    17. Okan Örsan Özener & Melda Örmeci Matoğlu & Güneş Erdoğan & Mohamed Haouari & Hasan Sözer, 2017. "Solving a large-scale integrated fleet assignment and crew pairing problem," Annals of Operations Research, Springer, vol. 253(1), pages 477-500, June.
    18. Zhe Liang & Wanpracha Art Chaovalitwongse & Huei Chuen Huang & Ellis L. Johnson, 2011. "On a New Rotation Tour Network Model for Aircraft Maintenance Routing Problem," Transportation Science, INFORMS, vol. 45(1), pages 109-120, February.
    19. Sarac, Abdulkadir & Batta, Rajan & Rump, Christopher M., 2006. "A branch-and-price approach for operational aircraft maintenance routing," European Journal of Operational Research, Elsevier, vol. 175(3), pages 1850-1869, December.
    20. Gopalan, Ram, 2014. "The Aircraft Maintenance Base Location Problem," European Journal of Operational Research, Elsevier, vol. 236(2), pages 634-642.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:jomega:v:93:y:2020:i:c:s0305048317306837. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/375/description#description .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.