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

doi:10.3969/j.issn.0255-8297.2025.02.007

Abstract

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

CLC Number:

TP18
U49

KOU Yawen, ZHOU Yangming, WANG Zhe. Hybrid Memetic Algorithm for Soft-Clustered Capacitated Arc Routing Problem[J]. Journal of Applied Sciences, 2025, 43(2): 274-287.

References

[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.

Hybrid Memetic Algorithm for Soft-Clustered Capacitated Arc Routing Problem

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 1

Recommended Articles

Metrics

Comments