Bus crew scheduling using mathematical programming

Abstract

This thesis describes a bus crew scheduling system, IMPACS, which has been demonstrated to be successful for a wide variety of scheduling conditions, and is at present in regular use by three British bus companies including the largest, London Buses Ltd. The background to the bus crew scheduling problem 1S described and the existing literature on methods for solution is reviewed. In IMPACS, the crew scheduling problem is formulated as an integer linear programme using a formulation which is an extension of set covering; a very large set of possible duties is generated, from which the duties forming the schedule are selected in such a way as to minimise the total cost. The variables of the set covering problem correspond to the duties generated and the constraints to the pieces of work in the bus schedule. For realistic schedules, it is impossible to generate all legal duties, and there are often too many pieces of work to allow each one to give rise to a constraint. IMPACS contains several heuristic methods which reduce the set covering problem to a manageable size, while still allowing good quality schedules to be compiled. Techniques for speeding up the solution of the set covering problem have been investigated, and in particular a branching strategy which exploits features of the crew scheduling problem has been developed.