Bus relief opportunity selection using constraint programming

Abstract

In planning urban bus operations, scheduling the drivers is the next stage after allocating buses to the timetabled journeys to produce a set of bus workings. Driver scheduling involves constructing a set of legal shifts such that every bus is always assigned a driver and the number of shifts is minimized. One method for solving this problem is to use integer linear programming. TRACS-II is a successful and widely used system, developed at Leeds University, which uses an ILP approach. A constraint programming pre-processing stage for TRACS-II has been developed, using probabilistic heuristics and a constraint programming tool (IL0G Solver). The pre-processor reduces the complexity of the ILP by reducing the number of relief opportunities, the times on each bus when the driver can be changed. A good selection of relief opportunities drastically reduces the size of the subsequent ILP while preserving the quality of its solution.