Two-Phase Heuristic Approach for Solving Capacitated Vehicle Routing Problem

DOI: 10.14416/j.ind.tech.2024.12.013

Abstract

The transportation of goods is essential to the operation of a business. The problem of planning transportation routes that accomplish the shortest distance is receiving attention, and the vehicle routing problem (VRP) is one of these subjects. This research presents a heuristic approach to using routing techniques to solve the capacitated vehicle routing problem (CVRP). Through applying routing techniques, two phases are involved in solving the instance, namely the cluster-first route-second (CFRS). The initial phase involves clustering n sub-groups according to the number of transport vehicles required. There are three methods for conducting this: 1) clustering based on the distance farthest from the depot to the center (seed point) of each sub-group, 2) seed point from the point of distribution nearest to the depot, and 3) seed point from the maximum demand. The second phase involves applying the travelling salesman problem (TSP) approach to find the route sequence. The results of the CVRP using the CFRS with the three different methods for the initial phase and the second phase, the routing for all goods using the TSP, are presented. Clustering using the seed point with the highest demand for each sub-group yielded better results than the other clustering methods, accounting for 60% of all benchmark instances.