A constraint programming pre-processor for duty scheduling

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-II, 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.

This thesis describes a pre-processing stage for the TRACS-II scheduling system. The pre-processor selects potentially useful relief opportunities from bus schedule. The shifts generated by TRACS-II 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.