Solving the Multiple Vehicle Scheduling Problem in a Major Scandinavian City

A. Larsen and O.B.G. Madsen


The Vehicle Scheduling Problem (VSP) deals with the assignment of vehicles to a set of transportation jobs. This problem arises within urban mass transit companies in order to construct a set of minimum cost daily schedules for the vehicles.

This paper deals with the NP-hard Multiple Depot Vehicle Scheduling Problem (MDVSP). The MDVSP is formulated as a time-space network model which is solved by Lagrangean relaxation. The Lagrangean multipliers are determined by sub-gradient optimization. The subproblems are solved by a general purpose algorithm for pure network flow problems. The model implemented is tested on two large scale real-life instances from an urban bus transit company situated in a major Scandinavian city.

IMM Technical Report 10, 1997

Last modified June 24, 1997

For further information, please contact, Finn Kuno Christensen, IMM, Bldg. 321, DTU
Phone: (+45) 4588 1433. Fax: (+45) 4588 2673, E-mail:

Go back