Solving the multiple depot vehicle scheduling problem in a major scandinavian city |
Allan Larsen, Oli B.G. Madsen
|
| Abstract | 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. |
| Type | Conference paper [Without referee] |
| Conference | Proceedings, NOAS '97 |
| Editors | |
| Year | 1997 No. 23 pp. 289-306 |
| Publisher | Department of Computer Science, University of Copenhagen |
| Address | |
| ISBN / ISSN | ISSN 0107-8283 |
| BibTeX data | [bibtex] |
| IMM Group(s) | Operations Research |