Constraint satisfaction approaches to bus driver scheduling

The bus driver scheduling problem consists of assigning bus work to drivers so that all the bus work is covered and a combination of the number of drivers and associated costs is minimised. Restrictions imposed by logistic, legal and union agreements complicate the problem.

Successful present day systems for computerised driver scheduling often use mathematical programming combined with heuristics. Purely heuristic approaches have found it very difficult to produce efficient driver schedules for large scheduling problems. Furthermore, some of these approaches may not be easily adaptable to different conditions. This thesis presents two new ways of using constraint satisfaction to form driver schedules. The two methods differ in their approach, one being a systematic constraint programming approach and the other being an adaptation of a local search method called GENET. The constraint programming approach uses a similar approach to mathematical programming systems in selecting the schedule from a large number of possible shifts, to allow adaptation to different regulations. In particular, a set partitioning formulation is used.

It then makes use of the structure of the problem and the relaxed linear programming solution to the problem in producing a schedule. The GENET system has been adapted to cope with minimising the numbers of drivers in a schedule and with the memory problems caused by the huge number of constraints involved in the set partitioning model.

The constraint programming approach has been shown to solve successfully several small scheduling problems from different companies using varying regulations. Local search procedures have hitherto not had great success on driver scheduling problems. GENET has been adapted to solve some of the small schedules from its initial state where it could not solve any. Features of the adaptation may be of interest to researchers using GENET on similar problems.