A hyper-heuristic algorithm for solving large-scale vehicle routing problems

Journal Information

J. Hefei Univ. Tech. (Nat. Sci.), Apr.2026, Vol.49 No.4: 464-471, 481

DOI: 10.3969/j.issn.1003-5060.2026.04.005

Authors

WANG Ziyuan $ ^{1} $, XIA Wei $ ^{1,2} $, WU Kang $ ^{1} $

(1. School of Management, Hefei University of Technology, Hefei 230009, China; 2. Key Laboratory of Process Optimization and Intelligent Decision Making, Ministry of Education, Hefei 230009, China)

Abstract and Keywords

Abstract: 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.

Keywords: vehicle routing problem (VRP); hyper-heuristic (HH) algorithm; evolution algorithm; density-based spatial clustering of applications with noise (DBSCAN); simulated annealing (SA)

作者信息

王子源 $ ^{1} $，夏维 $ ^{1,2} $，伍康 $ ^{1} $

(1. 合肥工业大学管理学院，安徽合肥 230009；2. 过程优化与智能决策教育部重点实验室，安徽合肥 230009)

摘要和关键词

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

关键词: 车辆路径问题；超启发式(HH)算法；进化算法；基于密度的空间聚类算法；模拟退火

Funding

国家自然科学基金资助项目（72271074）

合肥工业大学学报(自然科学版)

Navigation