MAENS+: A Divide-and-Conquer Based Memetic Algorithm for Capacitated Arc Routing Problem
The Capacitated Arc Routing Problem (CARP) has attracted much attention during the last few years due to its wide applications in real life. A Memetic Algorithm with Extended Neighborhood Search (MAENS) was developed for solving this kind of problem. A powerful local search operator, the so-called MS operator, was introduced and plays an important role in MAENS. But the main disadvantage is the high computational cost due to the large enumerative number of selecting route groups. In this paper, we propose an improved approach for MAENS with a divideand-conquer strategy, named MAENS+, which divides a large graph into small sub graphs in order to decrease enumerative number so as to reduce the computational cost. An adaptive method is used for choosing parameters during dividing. Experimental results show that MAENS+ manages to obtain the same level of solution quality as MAENS with much less computational time.
CARP MAENS MAENS+ MS operator Divide-and-conquer
Xiaomeng Chen
School of Information Science and Technology University of Science and Technology of China Hefei, China
国际会议
杭州
英文
83-88
2011-10-28（万方平台首次上网日期，不代表论文的发表时间）