The Vehicle Scheduling Problem concerns the assigning of a set of time-tabled trips to vehicles so as to minimize a given cost function. We consider the NP-hard Multiple Depot case in which, in addition, one has to assign vehicles to depots. Different lower bounds based on assigment relaxation and on connectivity constraints are presented and combined in an effective bounding procedure. A strong dominance procedure derived from new dominance criteria also described. A branch and bound algorithm is finally proposed. Computational results are given.

A Branch and Bound Algorithm for the Multiple Depot Vehicle Scheduling Problem / Dell'Amico, Mauro; Carpaneto, G.; Fischetti, M.; Toth, P.. - In: NETWORKS. - ISSN 0028-3045. - STAMPA. - 19:(1989), pp. 531-548.

A Branch and Bound Algorithm for the Multiple Depot Vehicle Scheduling Problem

DELL'AMICO, Mauro;
1989

Abstract

The Vehicle Scheduling Problem concerns the assigning of a set of time-tabled trips to vehicles so as to minimize a given cost function. We consider the NP-hard Multiple Depot case in which, in addition, one has to assign vehicles to depots. Different lower bounds based on assigment relaxation and on connectivity constraints are presented and combined in an effective bounding procedure. A strong dominance procedure derived from new dominance criteria also described. A branch and bound algorithm is finally proposed. Computational results are given.
19
531
548
A Branch and Bound Algorithm for the Multiple Depot Vehicle Scheduling Problem / Dell'Amico, Mauro; Carpaneto, G.; Fischetti, M.; Toth, P.. - In: NETWORKS. - ISSN 0028-3045. - STAMPA. - 19:(1989), pp. 531-548.
Dell'Amico, Mauro; Carpaneto, G.; 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/451189
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 90
  • ???jsp.display-item.citation.isi??? 82
social impact