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. Optinal solutions are then found by means of a branch and bound tree. Problems involving up to 80 points can be solved without difficulty.