关键词: 谱聚类, 车辆路径规划, 多车场车辆路径, 启发式算法, 组合优化

Abstract: Abstract: Aiming at the limitation of poor initial solution quality of existing heuristic algorithms when solving large-scale multi-depot vehicle path planning problem, an improvement method of heuristic vehicle routing algorithm based on Constrained Spectral Clustering (CSC) was proposed. Firstly, according to the geographical location and demand of the customers, the geographic information feature matrix and demand information feature matrix of the customers was generated. Secondly, the constraint matrix with constrained spectral clustering was generated according to the geographic information feature matrix and demand information feature matrix, and the clustering is completed. Finally, the spectral clustering results were used to generate the initial solution of the heuristic algorithm, and the appropriate heuristic algorithm was selected to solve the vehicle path planning problem. In the experiments on 21 instances of the standard dataset, CSC improves by 18% and 31% compared with SCSC (Self-Constrained-Spectral-Clustering) in standardized mutual information and Fowlkes-Mallows index of two indicators of clustering, respectively. In the vehicle routing task, the CSC initialization heuristic algorithm obtains the shortest path on 76% of the cases, and the running time of the heuristic algorithm is reduced by 13% compared with that of SCSC. The experimental results show that CSC can effectively improve the clustering accuracy of customer points, and then can effectively improve the solving speed and precision of vehicle path planning problems.

Key words: spectral clustering, vehicle routing, multi-depot vehicle routing, heuristic algorithm, combinatorial optimization