A memetic algorithm for periodic capacitated arc routing problem

Yi MEI, Ke TANG, Xin YAO

Research output: Journal PublicationsJournal Article (refereed)peer-review

63 Citations (Scopus)

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 $mnv$) and a secondary objective (minimizing the total cost $tc$). An important factor that makes PCARP challenging is that its primary objective $mnv$ 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 $mnv$. 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. © 2006 IEEE.
Original languageEnglish
Article number5954191
Pages (from-to)1654-1667
Number of pages14
JournalIEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics
Volume41
Issue number6
Early online date20 Jul 2011
DOIs
Publication statusPublished - Dec 2011
Externally publishedYes

Bibliographical note

This work was partially supported by an EPSRC Grant (No. EP/E058884/1) on “Evolutionary Algorithms for Dynamic Optimisation Problems: Design, Analysis and Applications,” the National Natural Science Foundation of China under Grants U0835002 and 61028009, and the grant for Distinguished Young Scholars of Anhui Province. This paper was recommended by Associate Editor H. Takagi.

Fingerprint

Dive into the research topics of 'A memetic algorithm for periodic capacitated arc routing problem'. Together they form a unique fingerprint.

Cite this