文献类型：期刊文献

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

英文题名：Hybrid Memetic Algorithm for Soft-Clustered Capacitated Arc Routing Problem

作者：寇亚文[1];周扬名[2,3];王喆[1]

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

年份：2025

卷号：43

期号：2

起止页码：274

中文期刊名：应用科学学报

外文期刊名：Journal of Applied Sciences

收录：;北大核心:【北大核心2023】；

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

语种：中文

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

外文关键词：arc routing problem;combinatorial optimization;evolutionary computation;memetic algorithm;variable neighborhood search

摘要：软集群容量约束弧路径问题是经典的容量约束弧路径问题的一种扩展。由于其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.