English

应用科学学报 >

2025 , Vol. 43 >Issue 2: 274 - 287

DOI: https://doi.org/10.3969/j.issn.0255-8297.2025.02.007

通信工程

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

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

收稿日期: 2023-02-15

  网络出版日期: 2025-04-03

基金资助

国家自然科学基金（No.61903144）；深圳市人工智能与机器人研究院探索项目（No.AC01202005002）资助

收起

Hybrid Memetic Algorithm for Soft-Clustered Capacitated Arc Routing Problem

Expand
  • 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 date: 2023-02-15

  Online published: 2025-04-03

Fold

摘要

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

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

本文引用格式

寇亚文, 周扬名, 王喆 . 混合模因算法求解软集群容量约束弧路径问题[J]. 应用科学学报, 2025 , 43(2) : 274 -287 . DOI: 10.3969/j.issn.0255-8297.2025.02.007

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

参考文献

[1] 孙锡梅, 林丹, 黄庆伟. 同时配送和回收需求的带容量约束弧路径问题[J]. 计算机应用, 2013, 33(增刊 1): 62-65. Sun X M, Lin D, Huang Q W. Capacitated arc routing problem with simultaneous pickup and delivery [J]. Journal of Computer Applications, 2013, 33(Suppl.1): 62-65. (in Chinese)
[2] 叶楠, 毕忠勤, 魏恒达, 等. 多区型仓库多复核台场景的拣货路径优化研究[J]. 应用科学学报, 2021, 39(4): 581-593. Ye N, Bi Z Q, Wei H D, et al. Research on optimizing picking route of multi-zone warehouse and multi-checking station [J]. Journal of Applied Sciences, 2021, 39(4): 581-593. (in Chinese)
[3] Golden B L, Wong R T. Capacitated arc routing problems [J]. Networks, 1981, 11(3): 305- 315．
[4] Hertz A, Laporte G, Mittaz M. A tabu search heuristic for the capacitated arc routing problem [J]. Operations Research, 2000, 48(1): 129-135.
[5] Hintsch T, Irnich S, Kiilerich L. Branch-price-and-cut for the soft-clustered capacitated arc-routing problem [J]. Transportation Science, 2021, 55(3): 687-705.
[6] 卫琛戈, 车阿大. 考虑容量限制的弧路径优化研究综述[J]. 系统工程学报, 2022, 37(3): 397-416. Wei C G, Che A D. Review of capacitated arc routing problems [J]. Journal of Systems Engineering, 2022, 37(3): 397-416. (in Chinese)
[7] 彭锦环, 马慧民. 带容量约束的弧路径问题: 文献综述[J]. 物流科技, 2015, 38(1): 63-66. Peng J H, Ma H M. Review of literature about capacitated arc routing problem [J]. Logistics Sci-Tech, 2015, 38(1): 63-66. (in Chinese)
[8] Gutin G, Karapetyan D. A memetic algorithm for the generalized traveling salesman problem [J]. Natural Computing, 2010, 9(1): 47-60.
[9] Neri F, Cotta C. Memetic algorithms and memetic computing optimization: a literature review [J]. Swarm and Evolutionary Computation, 2012, 2: 1-14.
[10] 陈昊, 许春蕾, 黎明, 等. 基于动态区域划分的多种群进化算法[J]. 应用科学学报, 2019, 37(1): 126-136. Chen H, Xu C L, Li M, et al. Multi-population evolutionary algorithm based on dynamic area division [J]. Journal of Applied Sciences, 2019, 37(1): 126-136. (in Chinese)
[11] Yang J, Kim Y H, Yoon Y. A memetic algorithm with a novel repair heuristic for the multiplechoice multidimensional knapsack problem [J]. Mathematics, 2022, 10(4): 602.
[12] Cordeau J F, Gaudioso M, Laporte G, et al. A memetic heuristic for the generalized quadratic assignment problem [J]. INFORMS Journal on Computing, 2006, 18(4): 433-443.
[13] Lyu Z, Hao J K. A memetic algorithm for graph coloring [J]. European Journal of Operational Research, 2010, 203(1): 241-250.
[14] Vidal T. Node, edge, arc routing and turn penalties: multiple problems-one neighborhood extension [J]. Operations Research, 2017, 65(4): 992-1010.
[15] 陈婳, 张国川. 经典一维装箱问题近似算法的研究进展[J]. 运筹学学报, 2022, 26(1): 69-84. Chen H, Zhang G C. A survey on approximation algorithms for one dimensional bin packing [J]. Operations Research Transactions, 2022, 26(1): 69-84. (in Chinese)
[16] Defryn C, Sorensen K. A fast two-level variable neighborhood search for the clustered vehicle routing problem [J]. Computers & Operations Research, 2017, 83: 78-94.
[17] Holmberg K. Heuristics for the rural postman problem [J]. Computers & Operations Research, 2010, 37(5): 981-990.
[18] Nagata Y, Kobayashi S. A powerful genetic algorithm using edge assembly crossover for the traveling salesman problem [J]. INFORMS Journal on Computing, 2013, 25(2): 346-363.
[19] Zhou Y, Kou Y, Zhou M. Bilevel memetic search approach to the soft-clustered vehicle routing problem [J]. Transportation Science, 2022, 57(3): 701-716.
[20] Setubal J C. Sequential and parallel experimental results with bipartite matching algorithms [R]. Brazil: University of Campinas, 1996.
[21] Hintsch T, Irnich S. Large multiple neighborhood search for the clustered vehicle-routing problem [J]. European Journal of Operational Research, 2018, 270(1): 118-131.
[22] Xu Z, Cai Y. Variable neighborhood search for consistent vehicle routing problem [J]. Expert Systems with Application, 2018, 113: 66-76.
[23] Babin G, Deneault S, Laporte G. Improvements to the Or-opt heuristic for the symmetric travelling salesman problem [J]. Journal of the Operational Research Society, 2007, 58(3): 402- 407.
[24] Lai X, Hao J K, Fu Z H, et al. Neighborhood decomposition based variable neighborhood search and tabu search for maximally diverse grouping [J]. European Journal of Operational Research, 2021, 289(3): 1067-1086.
[25] Chen Y, Hao J K, Glover F. A hybrid metaheuristic approach for the capacitated arc routing problem [J]. European Journal of Operational Research, 2016, 253(1): 25-39.
[26] Zhou Y, Hao J K, Glover F. Memetic search for identifying critical nodes in sparse graphs [J]. IEEE Transactions on Cybernetics, 2019, 49(10): 3699-3712.
Options
文章导航

/

〈 〉