A memetic algorithm for uncertain Capacitated Arc Routing Problems

Juan WANG, Ke TANG, Xin YAO

Research output: Book Chapters | Papers in Conference ProceedingsConference paper (refereed)Researchpeer-review

31 Citations (Scopus)

Abstract

The Capacitated Arc Routing Problem (CARP) is a widely investigated classic combinatorial optimization problem. Being a deterministic model, it is far away from the real world. A more practical problem model of CARP is the Uncertain CARP (UCARP), with the objective of finding a robust solution which performs well in all possible environments. There exist few algorithms for UCARP in previous work. In this paper, a Memetic Algorithm (MA) and its modified version in time consumption for UCARP are proposed. Experimental results on two benchmark test sets show that with an integrated fitness function and a large step-size local search operator, the new MAs show excellent ability to find robust solutions for UCARP. We also present a less time-consuming version of our MA which shows significant advantages in time consumption. © 2013 IEEE.
Original languageEnglish
Title of host publicationProceedings of the 2013 IEEE Workshop on Memetic Computing, MC 2013 - 2013 IEEE Symposium Series on Computational Intelligence, SSCI 2013
PublisherIEEE Computer Society
Pages72-79
Number of pages8
ISBN (Print)9781467358910
DOIs
Publication statusPublished - Apr 2013
Externally publishedYes

Keywords

  • evolutionary algorithm
  • robust optimization
  • UCARP

Fingerprint

Dive into the research topics of 'A memetic algorithm for uncertain Capacitated Arc Routing Problems'. Together they form a unique fingerprint.

Cite this