Investigating Capacitated Vehicle Routing Problem Using Clustered Simulated Annealing Algorithm

The Capacitated Vehicle Routing Problem (CVRP) has a wide range of applications in logistics and transportation. Current metaheuristics typically rely on manually added constraints. A hyper-heuristic framework can reduce the dependency on domain-specific knowledge. Therefore, this research proposes a Clustered Simulated Annealing algorithm (CSA). When generating the initial solution of the distribution path, the CSA adopts the Clustered Clarke–Wright Savings algorithm (CCW), the core of which is to use the K-means algorithm to cluster according to the Euclidean distances between the distribution points. The CCW can reduce the search range of the optimization problem by clustering and generating the initial solution quickly, enabling the CSA to perform better in data processing and real-time updates. The CSA then optimizes the initial solution using the Improved Simulated Annealing Hyper-Heuristic algorithm (ISAHH), divided into upper and lower layers. The Improved Simulated Annealing High-Level Heuristic strategy (ISAHLH) is used to select the Low-Level Heuristic operators (LLHs). At the same time, LLHs are used to generate new distribution paths. This research designs an Improved Tabu Low-Level Heuristic operator (ITabuLLH), which can search for several different paths simultaneously in a single iteration, thus improving the convergence speed of the algorithm. ISAHLH and ITabuLLH both use the Unequal Probability Selection mode (UEPS) to speed up the search process. The CSA is tested on the Uchoa benchmark set, and the results verify that the optimal value improvement of the CSA solution is higher than 20% when compared to eleven other algorithms.