A scheduling model and a solution algorithm for inter-city bus carriers

Shangyao Yan, Hao Lei Chen

Research output: Contribution to journalArticlepeer-review

127 Scopus citations


The setting of timetables and bus routing/scheduling are essential to an inter-city bus carrier's profitability, its level of service and its competitive capability in the market. In the past, carriers in Taiwan usually set their timetables and bus routes/schedules manually, which was inefficient. In this research we thus attempt to develop a model that will help Taiwan inter-city bus carriers in timetable setting and bus routing/scheduling. The model employs multiple time-space networks that can formulate bus movements and passenger flows and manage the interrelationships between passenger trip demands and bus trip supplies to produce the best timetables and bus routes/schedules. Mathematically, the model is formulated as a mixed integer multiple commodity network flow problem. An algorithm, based on Lagrangian relaxation, a sub-gradient method, the network simplex method, a Lagrangian heuristic and a flow decomposition algorithm, is developed to efficiently solve the problem. The results of a case study, regarding a major Taiwan inter-city bus operation, illustrate the model performance.

Original languageEnglish
Pages (from-to)805-825
Number of pages21
JournalTransportation Research Part A: Policy and Practice
Issue number9
StatePublished - Nov 2002


  • Inter-city bus
  • Lagrangian relaxation
  • Multiple commodity network flow problem
  • Routing/scheduling
  • Time-space network
  • Timetable


Dive into the research topics of 'A scheduling model and a solution algorithm for inter-city bus carriers'. Together they form a unique fingerprint.

Cite this