求解大规模车辆路径问题的超启发式算法

针对大规模车辆路径规划问题，文章提出一种基于密度空间聚类和超启发式（hyper-heuristic，HH）算法的两阶段路径规划框架。第1阶段根据客户点的空间位置特征，将大规模车辆路径客户点集合分解为若干个车辆路径优化子簇；第2阶段设计一种基于进化机制的HH算法进行求解。该算法采用底层的4种构造型算子和6种扰动型算子生成各簇的初始种群，再运用进化策略和模拟退火方案接收准则进行各子簇方案的全局融合优化，最后通过仿真实验在Uchoa标准数据集上验证了算法的有效性。

A two-stage route planning framework based on density-based spatial clustering of applications with noise(DBSCAN) and hyper-heuristic(HH) algorithm is suggested for the large-scale vehicle routing planning. The set of large-scale vehicle routing customer points is decomposed into several vehicle routing optimization sub-clusters based on the spatial location characteristics of the customer points in the first stage, and the problem is solved in the second stage using an HH algorithm based on evolutionary mechanism. The algorithm first generates the initial populations of each cluster using the underlying four conformal operators and six perturbation-type operators, and then uses the evolutionary strategy and the simulated annealing(SA) reception criterion to perform global fusion optimization of each sub-cluster solution. Finally, simulation tests on the Uchoa standard dataset verify the efficacy of the algorithm.