Integrated airline aircraft routing and crew pairing by alternating Lagrangian decomposition

Cong Li, Suixiang Gao (), Wenguo Yang and Zhipeng Jiang
Additional contact information
Cong Li: University of Chinese Academy of Sciences
Suixiang Gao: University of Chinese Academy of Sciences
Wenguo Yang: University of Chinese Academy of Sciences
Zhipeng Jiang: University of Chinese Academy of Sciences

Journal of Combinatorial Optimization, 2025, vol. 49, issue 5, No 20, 15 pages

Abstract: 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.

Keywords: Aircraft routing; Crew pairing; Alternating Lagrangian decomposition; Branch and price (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-025-01324-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:49:y:2025:i:5:d:10.1007_s10878-025-01324-0

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-025-01324-0

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().