We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Memetic algorithm based on extension step and statistical filtering for large-scale capacitated arc routing problems.
- Authors
Shang, Ronghua; Du, Bingqi; Dai, Kaiyun; Jiao, Licheng; Xue, Yu
- Abstract
The capacitated arc routing problem (CARP) is a classical NP-Hard combinatorial optimization problem. In this paper, we present a memetic algorithm based on Extension step and Statistical filtering for Large-Scale CARP (ESMAENS) which has improvements in both the global search strategy and the local search strategy. Firstly, ESMAENS adopts the Route Distance Grouping decomposition scheme (RDG) to decompose the large-scale CARP into some independent sub-problems. Then, the initial population would evolve into a new group by using the Evolutionary Algorithm. Furthermore, ESMAENS introduces the extension step search strategy to search the potential solutions around the current solution. As a result, with the increase of the iteration number, it avoids getting to the premature convergence. Meanwhile, the diversity of the population can be increased. Finally, in the local search strategy, the statistical filter is used to filter out some solutions and make the algorithm get the lower bound at a faster convergence rate with a high stability. Compared with RDG-MAENS, experimental results on Beullen’C, D, E, F, egl and EGL-G test set show that ESMAENS has a better convergence rate, and the stability of solutions obtained is improved. Furthermore, ESMAENS achieves a global search for the solutions. Especially for the large-scale EGL-G test set, ESMAENS can converge to a lower bound at a faster convergence rate, and it is suitable for solving large-scale CARP.
- Subjects
MATHEMATICAL optimization; LARGE scale systems; NUMERICAL analysis; PARAMETERS (Statistics); STOCHASTIC convergence
- Publication
Natural Computing, 2018, Vol 17, Issue 2, p375
- ISSN
1567-7818
- Publication type
Article
- DOI
10.1007/s11047-016-9606-x