Premium
A branch and bound algorithm for the multiple depot vehicle scheduling problem
Author(s) -
Carpaneto G.,
Dell'amico M.,
Fischetti M.,
Toth P.
Publication year - 1989
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230190505
Subject(s) - bounding overwatch , scheduling (production processes) , computer science , mathematical optimization , branch and bound , algorithm , upper and lower bounds , dominance (genetics) , mathematics , mathematical analysis , artificial intelligence , biochemistry , chemistry , gene
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.