A Column Generation Algorithm for the Bus Driver Scheduling Problem

  • 許 靖嵐

學生論文: Master's Thesis

摘要

Bus driver scheduling is aimed toward finding the minimum number of bus drivers to cover a published timetable of a bus company When scheduling bus drivers contractual work 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
獎項日期2016 七月 19
原文English
監督員Dung-Ying Lin (Supervisor)

引用此文

A Column Generation Algorithm for the Bus Driver Scheduling Problem
靖嵐, 許. (Author). 2016 七月 19

學生論文: Master's Thesis