English

应用科学学报 ›› 2025, Vol. 43 ›› Issue (2): 274-287.doi: 10.3969/j.issn.0255-8297.2025.02.007

• 通信工程 • 上一篇    

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

寇亚文1, 周扬名2,3, 王喆1   

  1. 1. 华东理工大学 信息科学与工程学院, 上海 200237;
    2. 上海交通大学 数字化管理决策实验室, 上海 200030;
    3. 上海交通大学 中美物流研究院, 上海 200030
  • 收稿日期:2023-02-15 发布日期:2025-04-03
  • 通信作者: 王喆，教授，研究方向为模式识别、机器学习等。E-mail:wangzhe@ecust.edu.cn
  • 基金资助:
    国家自然科学基金（No.61903144）；深圳市人工智能与机器人研究院探索项目（No.AC01202005002）资助

Hybrid Memetic Algorithm for Soft-Clustered Capacitated Arc Routing Problem

KOU Yawen1, ZHOU Yangming2,3, WANG Zhe1   

  1. 1. School of Information Science and Engineering, East China University of Science and Technology, Shanghai 200237, China;
    2. Data-Driven Management Decision Making Lab, Shanghai Jiao Tong University, Shanghai 200030, China;
    3. Sino-US Global Logistics Institute, Shanghai Jiao Tong University, Shanghai 200030, China
  • Received:2023-02-15 Published:2025-04-03

PDF

5

摘要： 软集群容量约束弧路径问题是经典的容量约束弧路径问题的一种扩展。由于其NP-hard特性，求解它在计算上具有挑战性。针对该问题，本文提出一种有效的混合模因算法（hybrid memetic algorithm,HMA）。该算法集成了3个独特的算法组件：基于组匹配的交叉操作来产生有希望的子代解、双层变邻域搜索执行局部优化以及考虑解的质量和距离的种群更新以维持一个高质量的种群。实验结果表明，HMA在求解质量和计算时间上均优于现有精确算法。

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

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

Key words: arc routing problem, combinatorial optimization, evolutionary computation, memetic algorithm, variable neighborhood search

中图分类号: