Applying Lagrangian relaxation-based algorithms for airline coordinated flight scheduling problems

Chia Hung Chen, Shangyao Yan, Miawjane Chen

Research output: Contribution to journalArticlepeer-review

10 Scopus citations

Abstract

Yan and Chen (2007, 2008) employed network flow techniques to construct coordinated scheduling models for passenger- and cargo-transportation, respectively. These models are formulated as mixed integer multiple commodity network flow problems with side constraints (NFPWS) that are characterized as NP-hard. Problem sizes are expected to be huge making the model more difficult to solve than traditional passenger/cargo flight scheduling problems. Therefore, a family of Lagrangian based algorithm is developed to solve the coordinated fleet routing and flight scheduling problems. Numerical tests are performed to evaluate the proposed algorithm using real operating data from two Taiwan airlines. The test results indicate that these solution algorithms are a significant improvement over those obtained with CPLEX. Moreover, the Lagrangian based algorithms are better than the mixed-stop heuristic, consequently they could be useful for allied airlines to solve coordinated fleet routing and flight scheduling problems.

Original languageEnglish
Pages (from-to)398-410
Number of pages13
JournalComputers and Industrial Engineering
Volume59
Issue number3
DOIs
StatePublished - Oct 2010

Keywords

  • Coordinated flight scheduling
  • Heuristic
  • Lagrangian relaxation
  • Multiple commodity network flow problem
  • Threshold accepting

Fingerprint

Dive into the research topics of 'Applying Lagrangian relaxation-based algorithms for airline coordinated flight scheduling problems'. Together they form a unique fingerprint.

Cite this