EFFECTIVE CLUSTER-FIRST ROUTE-SECOND APPROACHES USING METAHEURISTIC ALGORITHMS FOR THE CAPACITATED VEHICLE ROUTING PROBLEM - Ercan Comert, Serap; Yazgan, Harun Resit (International Journal of Industrial Engineering: Theory, Applications and Practice, 2021)
In this paper, three cluster-first route-second approaches are proposed to solve the capacitated vehicle routing problem (CVRP) that extends a traveling salesman problem (TSP). In the first phase, a giant tour covering all customers is built using three different metaheuristic algorithms as an ACO, a GA, and an ABCA. Then, the giant tour is split with respecting the vehicle capacity, and vehicles are loaded. In the second phase, we transform our problem into a small TSP after completing the clustering process, and a routing problem is solved based on a Branch-and-Bound algorithm. We evaluate the performance of these approaches on the benchmark problems. The computational results show that these approaches achieve high-quality results and gain an advantage in terms of CPU time. Besides, these approaches are also applied to a real-life case study related to a distribution CVRP meeting the weekly demands of a supermarket chain and provide a better routing solution.