DocumentCode :
1273533
Title :
A Memetic Algorithm for Periodic Capacitated Arc Routing Problem
Author :
Mei, Yi ; Tang, Ke ; Yao, Xin
Author_Institution :
Nature Inspired Comput. & Applic. Lab., Univ. of Sci. & Technol. of China, Hefei, China
Volume :
41
Issue :
6
fYear :
2011
Firstpage :
1654
Lastpage :
1667
Abstract :
This paper investigates the Periodic Capacitated Arc Routing Problem (PCARP), which is often encountered in the waste collection application. PCARP is an extension of the well-known Capacitated Arc Routing Problem (CARP) from a single period to a multi-period horizon. PCARP is a hierarchical optimization problem which has a primary objective (minimizing the number of vehicles ) and a secondary objective (minimizing the total cost ). An important factor that makes PCARP challenging is that its primary objective is little affected by existing operators and thus difficult to improve. We propose a new Memetic Algorithm (MA) for solving PCARP. The MA adopts a new solution representation scheme and a novel crossover operator. Most importantly, a Route-Merging (RM) procedure is devised and embedded in the algorithm to tackle the insensitive objective . The MA with RM (MARM) has been compared with existing meta-heuristic approaches on two PCARP benchmark sets and a real-world data set. The experimental results show that MARM obtained better solutions than the compared algorithms in much less time, and even updated the best known solutions of all the benchmark instances. Further study reveals that the RM procedure plays a key role in the superior performance of MARM.
Keywords :
optimisation; crossover operator; hierarchical optimization problem; memetic algorithm; meta-heuristic approach; periodic capacitated arc routing problem; route-merging procedure; waste collection application; Algorithm design and analysis; Combinatorial mathematics; Evolutionary computation; Logistics; Optimization; Routing; Transportation; Capacitated arc routing problems; combinatorial optimization; evolutionary algorithms; memetic algorithms;
fLanguage :
English
Journal_Title :
Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on
Publisher :
ieee
ISSN :
1083-4419
Type :
jour
DOI :
10.1109/TSMCB.2011.2158307
Filename :
5954191
Link To Document :
بازگشت