An Application of the Assignment Model to Bos Crew Rostering

The paper describes an aspect of bus-crew rostering in London Regional Transport. A requirement for good matching up of weekday, Saturday, and Sunday duties in a roster is formulated as a 3-dimensional assignment model, incorporating constraints governing minimum breaks. This is transformed to a 2-dimensional model which can be solved by a standard assignment algorithm. An alternative sequential approach, employing a simple heuristic, is used to reduce greatly the computational requirement, with a small loss in optimality. 1