Variable neighborhood decomposition for Large Scale Capacitated Arc Routing Problem

Yi Mei; Xiaodong Li; Xin Yao

doi:10.1109/CEC.2014.6900305

Variable neighborhood decomposition for Large Scale Capacitated Arc Routing Problem

Yi Mei^*, Xiaodong Li, Xin Yao

^*Corresponding author for this work

Computer Science

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

11 Citations (Scopus)

Abstract

In this paper, a Variable Neighborhood Decomposition (VND) is proposed for Large Scale Capacitated Arc Routing Problems (LSCARP). The VND employs the Route Distance Grouping (RDG) scheme, which is a competitive decomposition scheme for LSCARP, and generates different neighborhood structures with different tradeoffs between exploration and exploitation. The search first uses a neighborhood structure that is considered to be the most promising, and then broadens the neighborhood gradually as it is getting stuck in a local optimum. The experimental studies show that the VND performed better than the state-of-the-art RDG-MAENS counterpart, and the improvement is more significant when the subcomponent size is smaller. This implies a great potential of combining the VND with small subcomponents.

Original language	English
Title of host publication	Proceedings of the 2014 IEEE Congress on Evolutionary Computation, CEC 2014
Publisher	Institute of Electrical and Electronics Engineers (IEEE)
Pages	1313-1320
Number of pages	8
ISBN (Print)	9781479914883
DOIs	https://doi.org/10.1109/CEC.2014.6900305
Publication status	Published - 16 Sept 2014
Event	2014 IEEE Congress on Evolutionary Computation, CEC 2014 - Beijing, China Duration: 6 Jul 2014 → 11 Jul 2014

Conference

Conference	2014 IEEE Congress on Evolutionary Computation, CEC 2014
Country/Territory	China
City	Beijing
Period	6/07/14 → 11/07/14

ASJC Scopus subject areas

Artificial Intelligence
Computational Theory and Mathematics
Theoretical Computer Science

Access to Document

10.1109/CEC.2014.6900305

Cite this

@inproceedings{b8277c5f08374d6bbc846ec1b315d462,

title = "Variable neighborhood decomposition for Large Scale Capacitated Arc Routing Problem",

abstract = "In this paper, a Variable Neighborhood Decomposition (VND) is proposed for Large Scale Capacitated Arc Routing Problems (LSCARP). The VND employs the Route Distance Grouping (RDG) scheme, which is a competitive decomposition scheme for LSCARP, and generates different neighborhood structures with different tradeoffs between exploration and exploitation. The search first uses a neighborhood structure that is considered to be the most promising, and then broadens the neighborhood gradually as it is getting stuck in a local optimum. The experimental studies show that the VND performed better than the state-of-the-art RDG-MAENS counterpart, and the improvement is more significant when the subcomponent size is smaller. This implies a great potential of combining the VND with small subcomponents.",

author = "Yi Mei and Xiaodong Li and Xin Yao",

year = "2014",

month = sep,

day = "16",

doi = "10.1109/CEC.2014.6900305",

language = "English",

isbn = "9781479914883",

pages = "1313--1320",

booktitle = "Proceedings of the 2014 IEEE Congress on Evolutionary Computation, CEC 2014",

publisher = "Institute of Electrical and Electronics Engineers (IEEE)",

note = "2014 IEEE Congress on Evolutionary Computation, CEC 2014 ; Conference date: 06-07-2014 Through 11-07-2014",

}

Mei, Y, Li, X & Yao, X 2014, Variable neighborhood decomposition for Large Scale Capacitated Arc Routing Problem. in Proceedings of the 2014 IEEE Congress on Evolutionary Computation, CEC 2014., 6900305, Institute of Electrical and Electronics Engineers (IEEE), pp. 1313-1320, 2014 IEEE Congress on Evolutionary Computation, CEC 2014, Beijing, China, 6/07/14. https://doi.org/10.1109/CEC.2014.6900305

Variable neighborhood decomposition for Large Scale Capacitated Arc Routing Problem. / Mei, Yi; Li, Xiaodong; Yao, Xin.
Proceedings of the 2014 IEEE Congress on Evolutionary Computation, CEC 2014. Institute of Electrical and Electronics Engineers (IEEE), 2014. p. 1313-1320 6900305.

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

TY - GEN

T1 - Variable neighborhood decomposition for Large Scale Capacitated Arc Routing Problem

AU - Mei, Yi

AU - Li, Xiaodong

AU - Yao, Xin

PY - 2014/9/16

Y1 - 2014/9/16

N2 - In this paper, a Variable Neighborhood Decomposition (VND) is proposed for Large Scale Capacitated Arc Routing Problems (LSCARP). The VND employs the Route Distance Grouping (RDG) scheme, which is a competitive decomposition scheme for LSCARP, and generates different neighborhood structures with different tradeoffs between exploration and exploitation. The search first uses a neighborhood structure that is considered to be the most promising, and then broadens the neighborhood gradually as it is getting stuck in a local optimum. The experimental studies show that the VND performed better than the state-of-the-art RDG-MAENS counterpart, and the improvement is more significant when the subcomponent size is smaller. This implies a great potential of combining the VND with small subcomponents.

AB - In this paper, a Variable Neighborhood Decomposition (VND) is proposed for Large Scale Capacitated Arc Routing Problems (LSCARP). The VND employs the Route Distance Grouping (RDG) scheme, which is a competitive decomposition scheme for LSCARP, and generates different neighborhood structures with different tradeoffs between exploration and exploitation. The search first uses a neighborhood structure that is considered to be the most promising, and then broadens the neighborhood gradually as it is getting stuck in a local optimum. The experimental studies show that the VND performed better than the state-of-the-art RDG-MAENS counterpart, and the improvement is more significant when the subcomponent size is smaller. This implies a great potential of combining the VND with small subcomponents.

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

U2 - 10.1109/CEC.2014.6900305

DO - 10.1109/CEC.2014.6900305

M3 - Conference contribution

AN - SCOPUS:84908592877

SN - 9781479914883

SP - 1313

EP - 1320

BT - Proceedings of the 2014 IEEE Congress on Evolutionary Computation, CEC 2014

PB - Institute of Electrical and Electronics Engineers (IEEE)

T2 - 2014 IEEE Congress on Evolutionary Computation, CEC 2014

Y2 - 6 July 2014 through 11 July 2014

ER -

Variable neighborhood decomposition for Large Scale Capacitated Arc Routing Problem

Abstract

Conference

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this