Multifleet routing and multistop flight scheduling for schedule perturbation

Shangyao Yan, Yu Ping Tu

Research output: Contribution to journalArticlepeer-review

61 Scopus citations


Efficient and effective incidental scheduling techniques for schedule perturbation are essential to an airline carrier's operations. This research aims at developing a framework to assist carriers in fleet routing and flight scheduling for schedule perturbations in the operations of multifleet and multistop flights. The framework is based on a basic multifleet schedule perturbation model constructed as a timespace network from which strategic models are developed to research incidental scheduling. These network models are formulated as multiple commodity network flow problems. Lagrangian relaxation with subgradient methods accompanied by the network simplex method, a Lagrangian heuristic and a modified subgradient method are developed to solve the problems. A case study regarding the international operations of a major Taiwan airline carrier is presented.

Original languageEnglish
Pages (from-to)155-169
Number of pages15
JournalEuropean Journal of Operational Research
Issue number1
StatePublished - 16 Nov 1997


  • Lagrangian relaxation
  • Multiple commodity network flow problem
  • Schedule perturbation
  • Subgradient method
  • Time-space network


Dive into the research topics of 'Multifleet routing and multistop flight scheduling for schedule perturbation'. Together they form a unique fingerprint.

Cite this