基于路径切割和自适应检测的大规模限量弧路由问题求解  

Solving large scale capacitated arc routing problem based on route cutting off decomposition and adaptive detection

作　　者：方伟 朱建阳 FANG Wei;ZHU Jian-yang(Jiangsu Artificial Intelligence International Cooperation Joint Laboratory,Jiangnan University,Wuxi 214122,China;Jiangsu Provincial Engineering Laboratory of Pattern Recognition and Computational Intelligence,Jiangnan University,Wuxi 214122,China)

机构地区：[1]江南大学江苏人工智能国际合作联合实验室,江苏无锡214122 [2]江南大学江苏省模式识别与计算智能工程实验室,江苏无锡214122

出　　处：《控制与决策》2023年第12期3571-3577,共7页Control and Decision

基　　金：国家自然科学基金项目(62073155,62002137,62106088,62206113)。

摘　　要：大规模限量弧路由问题(large scale capacitated arc routing problem,LSCARP)是一个组合优化问题,应用广泛,采用分治策略是解决LSCARP的有效方法之一.首先,为了利用分治策略取得更优的分解结果,提出改进路径切割算子来求解LSCARP,其能够自动识别路径集合中形态较差的路径并对其有针对性地进行切割,从而在迭代中通过将切割后的路径进行重组以获得更优的分解,有利于算法跳出局部最优取得更小的最终费用;然后,针对LSCARP的结构会影响算法最终效果的问题,设计一种自适应数据集检测算子,其能够根据LSCARP中任务边与非任务边的关系来进行参数分配从而提高分解质量;最后,将以上2个算子应用于SHAiD算法,并与当前主流相关算法进行对比.实验结果表明了所提出算法的有效性.The large scale capacitated arc routing problem(LSCARP) is a combinatorial optimization problem and has a wide range of applications.The divide and conquer strategy is one of the effective methods to solve the LSCARP.In order to use the divide and conquer strategy to obtain better decomposition results,an improved route cutting operator is proposed to solve the LSCARP.The proposed operator can automatically identify the path with poor shape in the path set and carry out targeted processing on it.In order to achieve better decomposition by reorganizing the divided paths in the iteration,it is beneficial for the algorithm to jump out of the local optimum and obtain a smaller final cost.In addition,since the structure of the LSCARP may affect the final effect of the algorithm,an adaptive dataset detection operator is designed,which can allocate parameters according to the relationship between the task edge and non-task edge in order to improve the decomposition quality.Finally,the above two operators are used in the SHAiD algorithm.The effectiveness of the proposed algorithm is evaluated by compared with the stat-of-the-art-algorithms.

关 键 词：限量弧路由问题 组合优化 分治策略 大规模优化 路径切割 自适应 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]