A memetic algorithm for uncertain Capacitated Arc Routing Problems

Juan WANG; Ke TANG; Xin YAO

doi:10.1109/MC.2013.6608210

A memetic algorithm for uncertain Capacitated Arc Routing Problems

Juan WANG, Ke TANG, Xin YAO

Research output: Book Chapters | Papers in Conference Proceedings › Conference paper (refereed) › Research › peer-review

32 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 language	English
Title of host publication	Proceedings of the 2013 IEEE Workshop on Memetic Computing, MC 2013 - 2013 IEEE Symposium Series on Computational Intelligence, SSCI 2013
Publisher	IEEE Computer Society
Pages	72-79
Number of pages	8
ISBN (Print)	9781467358910
DOIs	https://doi.org/10.1109/MC.2013.6608210
Publication status	Published - Apr 2013
Externally published	Yes

Keywords

evolutionary algorithm
robust optimization
UCARP

Access to Document

10.1109/MC.2013.6608210

Cite this

@inproceedings{ace9c326b2e14dcfa18c02e14f8809b5,

title = "A memetic algorithm for uncertain Capacitated Arc Routing Problems",

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. {\textcopyright} 2013 IEEE.",

keywords = "evolutionary algorithm, robust optimization, UCARP",

author = "Juan WANG and Ke TANG and Xin YAO",

year = "2013",

month = apr,

doi = "10.1109/MC.2013.6608210",

language = "English",

isbn = "9781467358910",

pages = "72--79",

booktitle = "Proceedings of the 2013 IEEE Workshop on Memetic Computing, MC 2013 - 2013 IEEE Symposium Series on Computational Intelligence, SSCI 2013",

publisher = "IEEE Computer Society",

address = "United States",

}

A memetic algorithm for uncertain Capacitated Arc Routing Problems. / WANG, Juan; TANG, Ke; YAO, Xin.
Proceedings of the 2013 IEEE Workshop on Memetic Computing, MC 2013 - 2013 IEEE Symposium Series on Computational Intelligence, SSCI 2013. IEEE Computer Society, 2013. p. 72-79 6608210.

Research output: Book Chapters | Papers in Conference Proceedings › Conference paper (refereed) › Research › peer-review

TY - GEN

T1 - A memetic algorithm for uncertain Capacitated Arc Routing Problems

AU - WANG, Juan

AU - TANG, Ke

AU - YAO, Xin

PY - 2013/4

Y1 - 2013/4

N2 - 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.

AB - 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.

KW - evolutionary algorithm

KW - robust optimization

KW - UCARP

UR - http://www.scopus.com/inward/record.url?scp=84886553285&partnerID=8YFLogxK

U2 - 10.1109/MC.2013.6608210

DO - 10.1109/MC.2013.6608210

M3 - Conference paper (refereed)

SN - 9781467358910

SP - 72

EP - 79

BT - Proceedings of the 2013 IEEE Workshop on Memetic Computing, MC 2013 - 2013 IEEE Symposium Series on Computational Intelligence, SSCI 2013

PB - IEEE Computer Society

ER -

A memetic algorithm for uncertain Capacitated Arc Routing Problems

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this