A Constraint Programming Pre-processor for Duty Scheduling

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.