EFFECTIVE CLUSTER-FIRST ROUTE-SECOND APPROACHES USING METAHEURISTIC ALGORITHMS FOR THE CAPACITATED VEHICLE ROUTING PROBLEM

Authors

  • Serap Ercan Comert
  • Harun Resit Yazgan

DOI:

https://doi.org/10.23055/ijietap.2021.28.1.7223

Keywords:

cluster-first route-second approach, capacitated vehicle routing problem, ant colony optimization algorithm, genetic algorithm, artificial bee colony algorithm

Abstract

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.

Published

2021-10-12

How to Cite

Ercan Comert, S., & Yazgan, H. R. (2021). EFFECTIVE CLUSTER-FIRST ROUTE-SECOND APPROACHES USING METAHEURISTIC ALGORITHMS FOR THE CAPACITATED VEHICLE ROUTING PROBLEM. International Journal of Industrial Engineering: Theory, Applications and Practice, 28(1). https://doi.org/10.23055/ijietap.2021.28.1.7223

Issue

Section

Operation Research