A branch and bound algorithm for the multiple depot vehicle scheduling problem
Authors:
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.Keywords
This publication has 7 references indexed in Scilit:
- An Additive Bounding Procedure for Combinatorial Optimization ProblemsOperations Research, 1989
- A new dominance procedure for combinatorial optimization problemsOperations Research Letters, 1988
- On some matching problems arising in vehicle scheduling modelsNetworks, 1987
- Network models for vehicle and crew schedulingEuropean Journal of Operational Research, 1984
- Routing and scheduling of vehicles and crewsComputers & Operations Research, 1983
- Classification in vehicle routing and schedulingNetworks, 1981
- Some New Branching and Bounding Criteria for the Asymmetric Travelling Salesman ProblemManagement Science, 1980