Column generation approaches to bus driver scheduling

The bus driver scheduling problem involves assigning bus work to drivers in such a way that all the bus work is covered and the number of drivers and duty costs is minimised. This is complicated by the fact that there are restrictions on the formation of valid duties. A review of computerised scheduling systems is presented, along with a more detailed description of one such system which uses a set covering model to produce a schedule from a set of previously generated valid duties. This method first solves the Linear Programming relaxation, and then uses Branch and Bound techniques to search for a good integer solution. Improvements to this system are detailed. Most systems which use mathematical programming methods to solve the driver scheduling problem need heuristics to reduce the size of the problem since there are potentially many thousands of valid duties, even for small problems. Column generation is a technique which implicitly considers a much larger number of duties, whilst retaining a much smaller working duty subset. A specialised column generation method is implemented within the existing set covering system, and the results of tests on seven problems presented. Each problem instance is solved with two sizes of duty set, and timings compared to those tested on the set covering system. Results show an average reduction in execution time of 41% using column generation, and the larger data sets yield better schedules in terms of the number of duties and the overall cost