Cluster-first route-second heuristic algorithms for capacitated vehicle routing problem

Abstract

The Capacitated Vehicle Routing Problem (CVRP) is a combinatorial optimisation problem that determines the optimum routes for a given homogeneous fleet of vehicles located at a single depot. The objective of CVRP is to determine the set of routes with the minimum total travel distance that start and terminate at the depot while satisfying the demands at every customer point. Since CVRP is NP-Hard, heuristic algorithms have received broad interest to solve largescale CVRPs. Generating feasible clusters of customer points with a subsequent Traveling Salesman Problem (TSP) for each generated cluster, called cluster-first route-second, is the most prominent heuristic approach to solve CVRP in the literature. In this study, a novel clustering heuristic algorithm and two improvements for the Nearest-Neighbor (NN) algorithm: Modified NN (MNN) and Improved NN (INN), using the best-fit regression lines for solving TSP are proposed. The Sweep Algorithm and the proposed Novel algorithm for clustering phase and original NN algorithm, MNN, INN, Genetic Algorithm, and Greedy Algorithm for TSP solving are considered to compare the performances of the proposed algorithms. By combining the aforementioned two clustering algorithms and five TSP solving algorithms, ten cluster-first route-second heuristic algorithms are formed and implemented in the MATLAB environment. Then the effectiveness of the proposed algorithms is compared statistically using a set of 100 benchmarked problems in which the number of customer nodes ranges from 100 to 1000. These instances are solved using the ten algorithms, and CPU time and the total travel distance are recorded. One-way ANOVA (𝛼 = 0.05) test was used to compare the performance of ten algorithms. The statistical analysis revealed that the proposed clustering algorithm is significantly better than the Sweep Algorithm, and performance is increased when the number of customer nodes is increased. Moreover, both MNN and INN algorithms generate competitive TSP solutions.