Comparing assignment algorithms for the Multi-Depot VRP

Abstract

This paper considers the Multi-Depot Vehicle Routing Problem (MDVRP). Given the intrinsic difficulty of this problem class, approximation methods of the type "cluster first, route second" (two step approaches) seem to be promising for practical size problems. The first step, clustering is usually solved by assignments algorithms. The total cost of the solution for a MDVRP problem depends strongly on the assignment algorithm used in the first step, and these algorithms depend on the geographic topology of the instance of the problem to solve. We compare the results obtained by six heuristic algorithms for the assignment of customers to depots, with assignments obtained from solving the Transport Problem (TP). To compare the assignment algorithms we run the same routing heuristic, namely a modified version of the Clark and Wright heuristic [5], and compare the routing results for each one of them using STAAR [9] developed under the Arcview 3.0 Geographical Information System platform. In earlier work [10] we confirmed that the heuristics with best results were those with the largest computational efforts. We now find that the solutions obtained solving the TP give good results for our test cases and are worth using in real-life problems.