An improved two-phased heuristic algorithm for the capacitated vehicle routing problem and a case study

Abstract

The Capacitated Vehicle Routing Problem (CVRP) is a special variant of the Vehicle Routing Problem which has been extensively addressed in the literature of Operations Research. Since CVRP is a NP-hard problem, only heuristic algorithms are capable of solving relatively large-scale problems. In this research paper, a new Improved Two-phased Heuristic algorithm is presented for solving CVRP. The Improved Two-phased Heuristic algorithm is comprised of two phases and cluster-first rout-second approach is used. In the first phase, best sets (≤ five) of clusters are obtained using an iterative procedure based on five parameters. In the second phase, the Traveling Salesman Problem (TSP) of each cluster of the obtained sets of clusters is separately solved by applying the standard Genetic algorithm (GA). Subsequently, the best set of clusters with the minimum total traveling distance is selected as the final solution. The performance of the improved algorithm was compared with three prominent algorithms find in the literature: Efficient Two-phased Heuristic algorithm, Savings algorithm and GA, using thirty well-known benchmarked instances. The computational results of the comparison revealed that the Improved Two-phased Heuristic algorithm finds the least total traveling distance within a reasonable CPU time, compared to the three stated prominent algorithms. To illustrate the proposed algorithm and its applicability, the algorithm was applied for a food manufacturing company located in Sri Lanka. The results showed that there was a significant impact in reducing the transportation cost in distributing the company products by reducing the total traveling distance.

Keywords

• cvrp, savings algorithm, two-phased heuristic, genetic algorithm, comparison of heuristics