A column generation algorithm for the bus driver scheduling problem

Dung Ying Lin, Ching Lan Hsu

研究成果: Article同行評審

5 引文 斯高帕斯(Scopus)

摘要

Bus driver scheduling aims to find the minimum number of bus drivers to cover a published timetable of a bus company. When scheduling bus drivers, contractual working rules must be enforced, thus complicating the problem. In this research, we develop a column generation algorithm that decomposes this complicated problem into a master problem and a series of pricing subproblems. The master problem selects optimal duties from a set of known feasible duties, and the pricing subproblem augments the feasible duty set to improve the solution obtained in the master problem. The proposed algorithm is empirically applied to the realistic problems of several bus companies. The numerical results show that the proposed column generation algorithm can solve real-world problems and obtain bus driver schedules that are better than those developed and used by the bus companies.

原文English
頁(從 - 到)1598-1615
頁數18
期刊Journal of Advanced Transportation
50
發行號8
DOIs
出版狀態Published - 2016 十二月

All Science Journal Classification (ASJC) codes

  • Automotive Engineering
  • Economics and Econometrics
  • Mechanical Engineering
  • Computer Science Applications
  • Strategy and Management

指紋 深入研究「A column generation algorithm for the bus driver scheduling problem」主題。共同形成了獨特的指紋。

引用此