A Constraint Programming Pre-processor for Duty Scheduling
Colin J Layfield
PhD Thesis, School of Computing, University of Leeds, 2002.
Abstract
The bus driver scheduling problem involves assigning a set of drivers to cover all available bus work
such that every bus is assigned a driver, the number of duties is minimised and each duty conforms to
the rules governing them regarding maximum driving time and so on. Generally this problem is solved
using mathematical programming methods. The University of Leeds has developed a driver scheduling
system, TRACS-I I, that solves the bus driver scheduling problem by first generating a large set of
potential duties and selecting a subset of these via the associated set covering ILP to form the schedule.
The size of the set of potential duties used by TRACS-I I is directly related to the number of relief
opportunities present in the original bus schedule. Each relief opportunity potentially serves as a
handover point between two bus shifts. A bus schedule containing many relief opportunities can have a
very large set of potential shifts generated to cover the buswork. The complexity of the ILP is related to
the number of relief opportunities present in the bus schedule. This thesis describes a pre-processing
stage for the TRACS-I I scheduling system. The pre-processor selects potentially useful relief
opportunities from the bus schedule. The shifts generated by TRACS-I I are restricted to the subset of
relief opportunities made available to it by the pre-processor. The reduction of the number of relief
opportunities serves to reduce the complexity of the resulting set covering problem by reducing the
number of variables and constraints in the ILP. The pre-processor itself uses constraint programming
to find several possible ways of selecting relief opportunities from the morning and evening portions of
the bus schedule. This is done by exploiting useful properties found in good driver schedules, specifically
the chaining together of driver duties such that when one driver takes a break another driver finishing a
break continues on the same bus. The pre-processor described has been shown to be effective on a
wide variety of schedules in that the minimum number of drivers is almost always used and, in some
cases, cheaper schedules can be produced.