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.
For further information, please contact, Finn Kuno
Christensen, IMM, Bldg. 321, DTU
Phone: (+45) 4588 1433. Fax: (+45) 4588
2673, E-mail: fkc@imm.dtu.dk