Solving a Family of Multi-Depot Vehicle Routing and Location-Routing Problems

This paper examines a class of asymmetrical multi-depot vehicle routing problems and location-routing problems, under capacity or maximum cost restrictions. By using an appropriate graph representation, and then a graph extension, the problems are transformed into equivalent constrained assignment problems. Optimal solutions are then found by means of a branch and bound tree. Problems involving up to 80 nodes can be solved without difficulty.