Diversity-driven selection of multiple crossover operators for the capacitated arc routing problem

Pietro Consoli; Xin Yao

doi:10.1007/978-3-662-44320-0_9

Diversity-driven selection of multiple crossover operators for the capacitated arc routing problem

Pietro Consoli, Xin Yao

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

7 Citations (Scopus)

Abstract

The Capacitated Arc Routing Problem (CARP) is a NPHard routing problem with strong connections with real world problems. In this work we aim to enhance the performance of MAENS, a stateof- the-art algorithm, through a self-adaptive scheme to choose the most suitable operator and a diversity-driven ranking operator. Experimental results on 181 problem instances show how these techniques can both improve the results of the current state-of-the-art algorithms and provide good directions to develop EAs with a more robust approximation ratio.

Original language	English
Title of host publication	Evolutionary Computation in Combinatorial Optimisation
Subtitle of host publication	14th European Conference, EvoCOP 2014, Granada, Spain, April 23-25, 2014, Revised Selected Papers
Editors	Christian Blum, Gabriela Ochoa
Publisher	Springer
Pages	97-108
Number of pages	12
Volume	8600
ISBN (Electronic)	9783662443200
ISBN (Print)	9783662443194
DOIs	https://doi.org/10.1007/978-3-662-44320-0_9
Publication status	Published - 23 Apr 2014
Event	14th European Conference on Evolutionary Computation in Combinatorial Optimization, EvoCOP 2014 - Granada, Spain Duration: 23 Apr 2014 → 25 Apr 2014

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8600
ISSN (Print)	03029743
ISSN (Electronic)	16113349

Conference

Conference	14th European Conference on Evolutionary Computation in Combinatorial Optimization, EvoCOP 2014
Country/Territory	Spain
City	Granada
Period	23/04/14 → 25/04/14

Keywords

Approximation Algorithms
Capacitated Arc Routing Problem
Memetic Algorithm
Self-Adaptation
Stochastic Ranking

ASJC Scopus subject areas

Computer Science(all)
Theoretical Computer Science

Access to Document

10.1007/978-3-662-44320-0_9

Evolutionary Approximation Algorithms for Optimisation: Algorithm Design and Complexity Analysis
Yao, X.
Engineering & Physical Science Research Council
29/04/11 → 28/10/15
Project: Research Councils

Cite this

Consoli, P., & Yao, X. (2014). Diversity-driven selection of multiple crossover operators for the capacitated arc routing problem. In C. Blum, & G. Ochoa (Eds.), Evolutionary Computation in Combinatorial Optimisation : 14th European Conference, EvoCOP 2014, Granada, Spain, April 23-25, 2014, Revised Selected Papers (Vol. 8600, pp. 97-108). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8600). Springer. https://doi.org/10.1007/978-3-662-44320-0_9

Consoli, Pietro ; Yao, Xin. / Diversity-driven selection of multiple crossover operators for the capacitated arc routing problem. Evolutionary Computation in Combinatorial Optimisation : 14th European Conference, EvoCOP 2014, Granada, Spain, April 23-25, 2014, Revised Selected Papers. editor / Christian Blum ; Gabriela Ochoa. Vol. 8600 Springer, 2014. pp. 97-108 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{fdb689f909964ea09436bcd23622c329,

title = "Diversity-driven selection of multiple crossover operators for the capacitated arc routing problem",

abstract = "The Capacitated Arc Routing Problem (CARP) is a NPHard routing problem with strong connections with real world problems. In this work we aim to enhance the performance of MAENS, a stateof- the-art algorithm, through a self-adaptive scheme to choose the most suitable operator and a diversity-driven ranking operator. Experimental results on 181 problem instances show how these techniques can both improve the results of the current state-of-the-art algorithms and provide good directions to develop EAs with a more robust approximation ratio.",

keywords = "Approximation Algorithms, Capacitated Arc Routing Problem, Memetic Algorithm, Self-Adaptation, Stochastic Ranking",

author = "Pietro Consoli and Xin Yao",

year = "2014",

month = apr,

day = "23",

doi = "10.1007/978-3-662-44320-0_9",

language = "English",

isbn = "9783662443194",

volume = "8600",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "97--108",

editor = "Blum, {Christian } and Gabriela Ochoa",

booktitle = "Evolutionary Computation in Combinatorial Optimisation",

note = "14th European Conference on Evolutionary Computation in Combinatorial Optimization, EvoCOP 2014 ; Conference date: 23-04-2014 Through 25-04-2014",

}

Consoli, P & Yao, X 2014, Diversity-driven selection of multiple crossover operators for the capacitated arc routing problem. in C Blum & G Ochoa (eds), Evolutionary Computation in Combinatorial Optimisation : 14th European Conference, EvoCOP 2014, Granada, Spain, April 23-25, 2014, Revised Selected Papers. vol. 8600, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8600, Springer, pp. 97-108, 14th European Conference on Evolutionary Computation in Combinatorial Optimization, EvoCOP 2014, Granada, Spain, 23/04/14. https://doi.org/10.1007/978-3-662-44320-0_9

Diversity-driven selection of multiple crossover operators for the capacitated arc routing problem. / Consoli, Pietro; Yao, Xin.
Evolutionary Computation in Combinatorial Optimisation : 14th European Conference, EvoCOP 2014, Granada, Spain, April 23-25, 2014, Revised Selected Papers. ed. / Christian Blum; Gabriela Ochoa. Vol. 8600 Springer, 2014. p. 97-108 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8600).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Diversity-driven selection of multiple crossover operators for the capacitated arc routing problem

AU - Consoli, Pietro

AU - Yao, Xin

PY - 2014/4/23

Y1 - 2014/4/23

N2 - The Capacitated Arc Routing Problem (CARP) is a NPHard routing problem with strong connections with real world problems. In this work we aim to enhance the performance of MAENS, a stateof- the-art algorithm, through a self-adaptive scheme to choose the most suitable operator and a diversity-driven ranking operator. Experimental results on 181 problem instances show how these techniques can both improve the results of the current state-of-the-art algorithms and provide good directions to develop EAs with a more robust approximation ratio.

AB - The Capacitated Arc Routing Problem (CARP) is a NPHard routing problem with strong connections with real world problems. In this work we aim to enhance the performance of MAENS, a stateof- the-art algorithm, through a self-adaptive scheme to choose the most suitable operator and a diversity-driven ranking operator. Experimental results on 181 problem instances show how these techniques can both improve the results of the current state-of-the-art algorithms and provide good directions to develop EAs with a more robust approximation ratio.

KW - Approximation Algorithms

KW - Capacitated Arc Routing Problem

KW - Memetic Algorithm

KW - Self-Adaptation

KW - Stochastic Ranking

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

U2 - 10.1007/978-3-662-44320-0_9

DO - 10.1007/978-3-662-44320-0_9

M3 - Conference contribution

AN - SCOPUS:84922030067

SN - 9783662443194

VL - 8600

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 97

EP - 108

BT - Evolutionary Computation in Combinatorial Optimisation

A2 - Blum, Christian

A2 - Ochoa, Gabriela

PB - Springer

T2 - 14th European Conference on Evolutionary Computation in Combinatorial Optimization, EvoCOP 2014

Y2 - 23 April 2014 through 25 April 2014

ER -

Consoli P, Yao X. Diversity-driven selection of multiple crossover operators for the capacitated arc routing problem. In Blum C, Ochoa G, editors, Evolutionary Computation in Combinatorial Optimisation : 14th European Conference, EvoCOP 2014, Granada, Spain, April 23-25, 2014, Revised Selected Papers. Vol. 8600. Springer. 2014. p. 97-108. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-662-44320-0_9

Diversity-driven selection of multiple crossover operators for the capacitated arc routing problem

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Projects

Evolutionary Approximation Algorithms for Optimisation: Algorithm Design and Complexity Analysis

Cite this