A passenger demand model for airline flight scheduling and fleet routing

Shangyao Yan, Chich Hwang Tseng

Research output: Contribution to journalArticlepeer-review

70 Scopus citations


Fleet routing and flight scheduling are essential to a carrier's profitability, its level of service and its competitive capability in the market. This research develops a model and a solution algorithm to help carriers simultaneously solve for better fleet routes and appropriate timetables. The model is formulated as an integer multiple commodity network flow problem. An algorithm based on Lagrangian relaxation, a sub-gradient method, the network simplex method, the least cost flow augmenting algorithm and the flow decomposition algorithm is developed to efficiently solve the problem. The results of a case study, regarding a major Taiwan airline's operations, show the model's good performance. Fleet routing and flight scheduling issues have been widely studied to enhance airline's operation efficiency. Normally, network flow techniques are adopted for modeling and solving such complex mathematical problems. However, traditional approaches, which employ draft timetable as an essential medium, not only involve too much subjective judgement and decision making in the process but also reveal an incapability of directly and systematically managing the interrelation between supply and demand. The purpose of this paper is to develop a network model together with a solution algorithm, that can directly manage the interrelationships between passenger trip demands and flight supplies, in order to effectively assist carriers' scheduling.

Original languageEnglish
Pages (from-to)1559-1581
Number of pages23
JournalComputers and Operations Research
Issue number11
StatePublished - Sep 2002


  • Integer multiple commodity network flow problem
  • Lagrangian relaxation
  • Least cost flow augmenting algorithm
  • Time-space network


Dive into the research topics of 'A passenger demand model for airline flight scheduling and fleet routing'. Together they form a unique fingerprint.

Cite this