White Rose University Consortium logo
University of Leeds logo University of Sheffield logo York University logo

Bus crew scheduling using mathematical programming

Smith, Barbara Mary (1986) Bus crew scheduling using mathematical programming. PhD thesis, University of Leeds.

[img] Text
uk_bl_ethos_277275.pdf

Download (11Mb)

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.

Item Type: Thesis (PhD)
Academic Units: The University of Leeds > Faculty of Engineering (Leeds) > School of Computing (Leeds)
Depositing User: Ethos Import
Date Deposited: 06 Oct 2010 10:54
Last Modified: 07 Mar 2014 10:20
URI: http://etheses.whiterose.ac.uk/id/eprint/1053

Actions (repository staff only: login required)