一种求解大规模CVRP的有效算法  

An Effective Algorithm for Solving Large Scale CVRP

作　　者：饶舜 张玉州 RAO Shun;ZHANG Yuzhou(School of Computer and Information,Anqing Normal University,Anqing 246133,China)

机构地区：[1]安庆师范大学计算机与信息学院,安徽安庆246133

出　　处：《安庆师范大学学报（自然科学版）》2022年第1期43-48,共6页Journal of Anqing Normal University(Natural Science Edition)

基　　金：安徽省自然科学基金面上项目(1808085MF173);安徽省高等学校自然科学研究重点项目(KJ2016A438);安庆师范大学科研发展基金。

摘　　要：大规模带容量约束车辆路由问题(LSCVRP)是基本车辆路由问题(VRP)在客户数上升至一定程度后形成的具有实际意义的热点问题,其难点在于如何在巨大的解空间中进行有效地搜索。为解决此问题,将一种层次分解策略引入到大规模CVRP的求解,使用变邻域搜索对解进行局部搜索,以进一步提高解的质量。为了验证所设计算法的有效性,在Golden和Li两个标准测试集上进行计算,并与现有优秀算法进行对比。结果表明,该研究所设计的算法在较多算例上更新了问题的最优解,尤其在大规模测试集Li上,表现得更加出色。Large Scale Capacitated Vehicle Routing Problem(LSCVRP)is formed by Vehicle Routing Problem(VRP).As the number of the customers rises to a certain degree,it becomes a hot practical issue.To LSCVRP,the difficulty lies in how to search effectively in a large solution space.This paper introduces a hierarchical decomposition strategy to solve LSCVRP,and applies variable neighborhood search to the incumbent solution to further improve the quality of it.In order to verify the effectiveness of the designed algorithm,two benchmark test sets(i.e.,Golden and Li)are calculated and the results are compares with several state-of-the-art algorithms.The results show that the algorithm designed in this paper can outperform the compared algorithms in many examples,especially in the large-scale test set Li.

关 键 词：组合优化 变邻域搜索 层次分解 大规模 带容量约束车辆路由问题 

分 类 号：F502[经济管理—产业经济]