IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v49y2025i5d10.1007_s10878-025-01324-0.html
   My bibliography  Save this article

Integrated airline aircraft routing and crew pairing by alternating Lagrangian decomposition

Author

Listed:
  • Cong Li

    (University of Chinese Academy of Sciences)

  • Suixiang Gao

    (University of Chinese Academy of Sciences
    Zhongguancun Laboratory)

  • Wenguo Yang

    (University of Chinese Academy of Sciences)

  • Zhipeng Jiang

    (University of Chinese Academy of Sciences)

Abstract

For the aircraft routing and crew pairing problems, a sequential approach is usually used to solve they. When solving the crew pairing problem, the impact of aircraft routing problem is often neglected so that these two problems are independent. This approach reduces the complexity of the solution process, but it may obtain a suboptimal solution. In this paper, we consider an integrated aircraft routing and crew pairing problem. We propose an integrated model that integrates the aircraft routing and crew pairing problems. We propose a solution algorithm based on a heuristic alternating Lagrangian decomposition to address coupling constraint of the integrated model. The solution algorithm iterates between the first Lagrangian subproblem about aircraft routing and the second Lagrangian subproblem about crew pairing. These two Lagrangian subproblems are solved by a branch-and-price algorithm. In the branch-and-price algorithm, we present a heuristic branching strategy. The computational experiments are conducted on several real-world data sets.

Suggested Citation

  • Cong Li & Suixiang Gao & Wenguo Yang & Zhipeng Jiang, 2025. "Integrated airline aircraft routing and crew pairing by alternating Lagrangian decomposition," Journal of Combinatorial Optimization, Springer, vol. 49(5), pages 1-15, July.
    • Handle: RePEc:spr:jcomop:v:49:y:2025:i:5:d:10.1007_s10878-025-01324-0
    DOI: 10.1007/s10878-025-01324-0
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-025-01324-0
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10878-025-01324-0?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. 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.
    2. Cynthia Barnhart & Ellis L. Johnson & George L. Nemhauser & Martin W. P. Savelsbergh & Pamela H. Vance, 1998. "Branch-and-Price: Column Generation for Solving Huge Integer Programs," Operations Research, INFORMS, vol. 46(3), pages 316-329, June.
    3. 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.
    4. Zeighami, Vahid & Saddoune, Mohammed & Soumis, François, 2020. "Alternating Lagrangian decomposition for integrated airline crew scheduling problem," European Journal of Operational Research, Elsevier, vol. 287(1), pages 211-224.
    5. 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.
    6. Ben Ahmed, Mohamed & Zeghal Mansour, Farah & Haouari, Mohamed, 2018. "Robust integrated maintenance aircraft routing and crew pairing," Journal of Air Transport Management, Elsevier, vol. 73(C), pages 15-31.
    7. 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.
    Full references (including those not matched with items on IDEAS)

    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. Wen, Xin & Chung, Sai-Ho & Choi, Tsan-Ming & Fu, Xiaowen, 2024. "Airline cabin crew pairing with accurate characterization of cross-class substitution: A branch-and-price approach," Transportation Research Part B: Methodological, Elsevier, vol. 190(C).
    2. 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).
    3. Wen, Xin & Sun, Xuting & Ma, Hoi-Lam & Sun, Yige, 2022. "A column generation approach for operational flight scheduling and aircraft maintenance routing," Journal of Air Transport Management, Elsevier, vol. 105(C).
    4. Stern, Helman I. & Gertsbakh, Ilya B., 2019. "Using deficit functions for aircraft fleet routing," Operations Research Perspectives, Elsevier, vol. 6(C).
    5. Zeighami, Vahid & Saddoune, Mohammed & Soumis, François, 2020. "Alternating Lagrangian decomposition for integrated airline crew scheduling problem," European Journal of Operational Research, Elsevier, vol. 287(1), pages 211-224.
    6. Lacasse-Guay, Eve & Desaulniers, Guy & Soumis, François, 2010. "Aircraft routing under different business processes," Journal of Air Transport Management, Elsevier, vol. 16(5), pages 258-263.
    7. Arpan Rijal & Marco Bijvank & Asvin Goel & René de Koster, 2021. "Workforce Scheduling with Order-Picking Assignments in Distribution Facilities," Transportation Science, INFORMS, vol. 55(3), pages 725-746, May.
    8. Wu, Weitiao & Lin, Yue & Liu, Ronghui & Jin, Wenzhou, 2022. "The multi-depot electric vehicle scheduling problem with power grid characteristics," Transportation Research Part B: Methodological, Elsevier, vol. 155(C), pages 322-347.
    9. Korte, Johanna P. & Yorke-Smith, Neil, 2025. "An aircraft and schedule integrated approach to crew scheduling for a point-to-point airline," Journal of Air Transport Management, Elsevier, vol. 124(C).
    10. Gutiérrez-Jarpa, Gabriel & Desaulniers, Guy & Laporte, Gilbert & Marianov, Vladimir, 2010. "A branch-and-price algorithm for the Vehicle Routing Problem with Deliveries, Selective Pickups and Time Windows," European Journal of Operational Research, Elsevier, vol. 206(2), pages 341-349, October.
    11. Qin, Hu & Moriakin, Anton & Xu, Gangyan & Li, Jiliu, 2024. "The generator distribution problem for base stations during emergency power outage: A branch-and-price-and-cut approach," European Journal of Operational Research, Elsevier, vol. 318(3), pages 752-767.
    12. Albert H. Schrotenboer & Evrim Ursavas & Iris F. A. Vis, 2019. "A Branch-and-Price-and-Cut Algorithm for Resource-Constrained Pickup and Delivery Problems," Transportation Science, INFORMS, vol. 53(4), pages 1001-1022, July.
    13. Maher, Stephen J. & Desaulniers, Guy & Soumis, François, 2018. "The daily tail assignment problem under operational uncertainty using look-ahead maintenance constraints," European Journal of Operational Research, Elsevier, vol. 264(2), pages 534-547.
    14. Bani, Abderrahman & El Hallaoui, Issmail & Corréa, Ayoub Insa & Tahir, Adil, 2023. "Solving a real-world multi-depot multi-period petrol replenishment problem with complex loading constraints," European Journal of Operational Research, Elsevier, vol. 311(1), pages 154-172.
    15. 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.
    16. Guy Desaulniers & Diego Pecin & Claudio Contardo, 2019. "Selective pricing in branch-price-and-cut algorithms for vehicle routing," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 8(2), pages 147-168, June.
    17. Walteros, Jose L. & Vogiatzis, Chrysafis & Pasiliao, Eduardo L. & Pardalos, Panos M., 2014. "Integer programming models for the multidimensional assignment problem with star costs," European Journal of Operational Research, Elsevier, vol. 235(3), pages 553-568.
    18. Luciano Costa & Claudio Contardo & Guy Desaulniers, 2019. "Exact Branch-Price-and-Cut Algorithms for Vehicle Routing," Transportation Science, INFORMS, vol. 53(4), pages 946-985, July.
    19. Adil Tahir & Guy Desaulniers & Issmail El Hallaoui, 2022. "Integral Column Generation for Set Partitioning Problems with Side Constraints," INFORMS Journal on Computing, INFORMS, vol. 34(4), pages 2313-2331, July.
    20. Jiliu Li & Zhixing Luo & Roberto Baldacci & Hu Qin & Zhou Xu, 2023. "A New Exact Algorithm for Single-Commodity Vehicle Routing with Split Pickups and Deliveries," INFORMS Journal on Computing, INFORMS, vol. 35(1), pages 31-49, January.

    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:spr:jcomop:v:49:y:2025:i:5:d:10.1007_s10878-025-01324-0. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.