Memetic algorithm with non-smooth penalty for capacitated arc routing problem[Formula presented]

Li，Rui1; Zhao，Xinchao1,2; Zuo，Xingquan3; Yuan，Jianmei2,4; Yao，Xin5

2021-05-23

10.1016/j.knosys.2021.106957

KNOWLEDGE-BASED SYSTEMS   影响因子和分区

0950-7051

The capacitated arc routing problem (CARP) has attracted much attention during last decades due to its wide applications. However, the existing research methods still have a little potential to make full use of the characteristics of CARP. This paper aims to mine the essential characteristics of arc routing problem that node routing problem does not have. Based on the observation on characteristics of arc routing instances, smooth condition is proposed and constructed as a rule to divide the link between two tasks into smooth link and non-smooth link. Then smooth degree is defined to measure the influence of non-smooth links on solution and a small smooth degree means the better quality for a solution. The effect of smooth degree is verified through simulation comparison on several instance sets, which indicates that there is a positive correlation between smooth degree and the total cost of a solution. Non-smooth penalty is used to drive the non-smooth solution to smooth and to improve its total cost. Then non-smooth penalty is inserted into path-scanning variants and new construction algorithms are obtained. A partial reconstruction method (PRM) is designed using these construction algorithms as an alternative kernel method. In order to further reduce the routes number, a reinsert method (RiM) is proposed. Combining these two methods with traditional local search algorithms, a memetic algorithm with non-smooth penalty (MANSP) is proposed which is originated from the initial observation on the essential characteristics of arc routing problem. Extensive experiments on smooth degree, penalty factor, and comparison with state-of-the-art algorithms show that the proposed strategies are effective and the proposed algorithm MANSP performs very competitive.

Capacitated arc routing problem (CARP) Memetic algorithm (MA) Non-smooth penalty Reinsertion method Smooth condition Smooth degree

SCI ; EI

英语

其他

WOS:000637681300004

20211210106264

Computer Software, Data Handling and Applications:723

COMPUTER SCIENCE

2-s2.0-85102621560

Scopus

1.School of Science,Beijing University of Posts and Telecommunications,Beijing,100876,China
2.Hunan Key Laboratory for Computation and Simulation in Science and Engineering,Xiangtan University,Xiangtan,411105,China
3.School of Computer Science,Beijing University of Posts and Telecommunications,Beijing,100876,China
4.School of Mathematics and Computational Science,Xiangtan University,Xiangtan,411105,China
5.Department of Computer Science and Engineering,Southern University of Science and Technology,Shenzhen,518055,China

Li，Rui,Zhao，Xinchao,Zuo，Xingquan,et al. Memetic algorithm with non-smooth penalty for capacitated arc routing problem[Formula presented][J]. KNOWLEDGE-BASED SYSTEMS,2021,220.

Li，Rui,Zhao，Xinchao,Zuo，Xingquan,Yuan，Jianmei,&Yao，Xin.(2021).Memetic algorithm with non-smooth penalty for capacitated arc routing problem[Formula presented].KNOWLEDGE-BASED SYSTEMS,220.

Li，Rui,et al."Memetic algorithm with non-smooth penalty for capacitated arc routing problem[Formula presented]".KNOWLEDGE-BASED SYSTEMS 220(2021).