混合模因算法求解软集群容量约束弧路径问题  

Hybrid Memetic Algorithm for Soft-Clustered Capacitated Arc Routing Problem

作　　者：寇亚文 周扬名 王喆[1] KOU Yawen;ZHOU Yangming;WANG Zhe(School of Information Science and Engineering,East China University of Science and Technology,Shanghai 200237,China;Data-Driven Management Decision Making Lab,Shanghai Jiao Tong University,Shanghai 200030,China;Sino-US Global Logistics Institute,Shanghai Jiao Tong University,Shanghai 200030,China)

机构地区：[1]华东理工大学信息科学与工程学院,上海200237 [2]上海交通大学数字化管理决策实验室,上海200030 [3]上海交通大学中美物流研究院,上海200030

出　　处：《应用科学学报》2025年第2期274-287,共14页Journal of Applied Sciences

基　　金：国家自然科学基金(No.61903144);深圳市人工智能与机器人研究院探索项目(No.AC01202005002)资助。

摘　　要：软集群容量约束弧路径问题是经典的容量约束弧路径问题的一种扩展。由于其NP-hard特性,求解它在计算上具有挑战性。针对该问题,本文提出一种有效的混合模因算法(hybrid memetic algorithm,HMA)。该算法集成了3个独特的算法组件:基于组匹配的交叉操作来产生有希望的子代解、双层变邻域搜索执行局部优化以及考虑解的质量和距离的种群更新以维持一个高质量的种群。实验结果表明,HMA在求解质量和计算时间上均优于现有精确算法。The soft-clustered capacitated arc routing problem(SoftCluCARP)is an extension of the classical capacitated arc routing problem.Due to its NP-hard nature,solving it is computationally challenging.In this work,we propose an effective hybrid memetic algorithm(HMA)to solve SoftCluCARP.HMA integrates three distinct algorithm modules:a group matching-based crossover to produce promising offspring solutions,a two-stage variable neighborhood search to perform local optimization,and a quality-and-distance population updating to maintain a high-quality population.Experimental results show that HMA is highly competitive compared to the existing exact algorithm in terms of both solution quality and computation time.

关 键 词：弧路径问题 组合优化 进化计算 模因算法 变邻域搜索 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程] U49[自动化与计算机技术—控制科学与工程]