An Enhanced Hybrid Genetic Algorithm for the Capacitated Arc Routing Problem

Abstract

Abstract: In order to solve the NP-hard capacitated arc routing problem (CARP) in acceptable time, an enhance hybrid genetic algorithm (EHGA) was proposed. The enhanced local search (ELS) was used within a genetic algorithm (GA) framework to intensify the search. Binary tournament replacement and population management strategy were proposed when population was updated. The CARP benchmark instances were tested. The results show that EHGA outperforms memetic algorithm (MA), and is effective to solve the CARP.

Key words: capacitated arc routing problem (CARP), metaheuristic; , hybrid genetic algorithm, binary tournament replacement

CLC Number:

TP 301

LIU Tian-Tang, JIANG Zhi-Bin, HU Hong-Tao, LIU Ran. An Enhanced Hybrid Genetic Algorithm for the Capacitated Arc Routing Problem [J]. Journal of Shanghai Jiaotong University, 2013, 47(04): 619-625.

References

［1］Golden B L, Wong R T. Capacitated arc routing problems［J］. Networks, 1981，11(3): 305315.
［2］Golden J, DeArmon J S, Baker E K. Computational experiments with algorithms for a class of routing problems ［J］. Computers & Operations Research, 1983. 10(1): 4759.
［3］Chapleau L, Ferland J A, Lapalme G, et al. A parallel insert method for the capacitated arc routing problem ［J］. Operations Research Letters, 1984， 3(2): 9599.
［4］Pearn W. Approximate solutions for the capacitated arc routing problem ［J］. Computers & Operations Research, 1989，16(6): 589600.
［5］Pearn W. Augmentinsert algorithms for the capacitated arc routing problem ［J］. Computers & Operations Research, 1991，18(2): 189198.
［6］Ulusoy G. The fleet size and mix problem for capacitated arc routing ［J］. European Journal of Operational Research, 1985， 22(3): 329337.
［7］Benavent E, Campos V, Corberán A, et al. The capacitated arc routing problem. A heuristic algorithm ［J］. Qüestiió, 1990， 14(13): 107122.
［8］Hertz A, Laporte G , Mittaz M. A tabu search heuristic for the capacitated arc routing problem ［J］. Operations Research, 2000， 48(1): 129135.
［9］Branda J, Eglese R. A deterministic tabu search algorithm for the capacitated arc routing problem ［J］. Computers & Operations Research, 2008， 35(4): 11121126.
［10］Hertz A, Mittaz M. A variable neighborhood descent algorithm for the undirected capacitated arc routing problem ［J］. Transportation Science, 2001，35(4): 425434.
［11］Beullens P, Muyldermans L, Cattrysse D, et al. A guided local search heuristic for the capacitated arc routing problem ［J］. European Journal of Operational Research, 2003， 147(3): 629643.
［12］Lacomme P, Prins C, RamdaneCherif W. Competitive memetic algorithms for arc routing problems ［J］. Annals of Operations Research, 2004， 131(1): 159185.
［13］Santos L, CoutinhoRodrigues J, Current J R. An improved ant colony optimization based algorithm for the capacitated arc routing problem ［J］. Transportation Research Part B: Methodological, 2010， 44(2): 246266.
［14］Frederickson G. Approximation algorithms for some postman problems ［J］. Journal of the ACM (JACM), 1979， 26(3): 538554.
［15］Srensen K, Sevaux M. MA|PM: Memetic algorithms with population management ［J］. Computers & Operations Research， 2006， 33(5): 12141225.

[1]	FAN Houming,XU Zhenlin,LI Yang,LIU Wenqi,GENG Jing. Hybrid Genetic Algorithm for Solving Multi-Depot Joint Distribution Routing Problem [J]. Journal of Shanghai Jiaotong University, 2019, 53(8): 1000-1009.
[2]	HUANG Qiang1,2 (黄强), LOU Xin-yuan3 (楼新远), WANG Wei4* (王薇), NI Shao-quan1 (倪少权). Research of Order Allocation Model Based on Cloud and Hybrid Genetic Algorithm Under Ecommerce Environment [J]. Journal of shanghai Jiaotong University (Science), 2013, 18(3): 334-342.
[3]	HU Da-Yong, YAO Zhen-Qiang. Optimization Strategy for Bulk Ship Unloader Scheduling with Rail Routing Constraints [J]. Journal of Shanghai Jiaotong University, 2012, 46(09): 1431-1435.