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.

Heuristic Algorithms for the Multiple Depot Vehicle Scheduling Problem / Dell'Amico, Mauro; Fischetti, M.; Toth, P.. - In: MANAGEMENT SCIENCE. - ISSN 0025-1909. - STAMPA. - 39:(1993), pp. 115-125.

Heuristic Algorithms for the Multiple Depot Vehicle Scheduling Problem

DELL'AMICO, Mauro;
1993

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.
39
115
125
Heuristic Algorithms for the Multiple Depot Vehicle Scheduling Problem / Dell'Amico, Mauro; Fischetti, M.; Toth, P.. - In: MANAGEMENT SCIENCE. - ISSN 0025-1909. - STAMPA. - 39:(1993), pp. 115-125.
Dell'Amico, Mauro; Fischetti, M.; Toth, P.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11380/451188
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 61
  • ???jsp.display-item.citation.isi??? 56
social impact