Heuristic Algorithms for the Multiple Depot Vehicle Scheduling Problem

Mauro Dell'Amico, Matteo Fischetti and Paolo Toth
Additional contact information
Mauro Dell'Amico: DEIS, University of Bologna, Bologna, Italy
Matteo Fischetti: DEIS, University of Bologna, Bologna, Italy
Paolo Toth: DEIS, University of Bologna, Bologna, Italy

Management Science, 1993, vol. 39, issue 1, 115-125

Abstract: We consider the NP-hard Multiple Depot Vehicle Scheduling Problem, in which a given set of time-tabled trips have to be assigned to vehicles stationed at different depots, so as to minimize the number of vehicles used and the overall operational cost. The problem arises in the management of transportation companies. In this paper some structural properties of the problem are studied and used to design a new polynomial-time heuristic algorithm which always guarantees the use of the minimum number of vehicles. Several effective refining procedures are also proposed. Extensive computational results on test problems involving up to 1,000 trips and 10 depots are reported, showing that the new approach always produces very tight approximate solutions in small computing times and outperforms other heuristics from the literature.

Keywords: vehicle scheduling; heuristic algorithms; computational analysis (search for similar items in EconPapers)
Date: 1993
References: Add references at CitEc
Citations: View citations in EconPapers (21)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.39.1.115 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:39:y:1993:i:1:p:115-125

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().