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

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

15 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. © 2014 IEEE.

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 Inc.
Pages	1313-1320
Number of pages	8
ISBN (Print)	9781479914883
DOIs	https://doi.org/10.1109/CEC.2014.6900305
Publication status	Published - Jul 2014
Externally published	Yes

Access to Document

10.1109/CEC.2014.6900305

Cite this

@inproceedings{27da12f2fa24483a8b2077d877e25978,

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

author = "Yi MEI and Xiaodong LI and Xin YAO",

year = "2014",

month = jul,

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 Inc.",

address = "United States",

}

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 Inc., 2014. p. 1313-1320 6900305.

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

TY - GEN

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

AU - MEI, Yi

AU - LI, Xiaodong

AU - YAO, Xin

PY - 2014/7

Y1 - 2014/7

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. © 2014 IEEE.

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. © 2014 IEEE.

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 paper (refereed)

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

ER -

Variable neighborhood decomposition for Large Scale Capacitated Arc Routing Problem

Abstract

Access to Document

Other files and links

Fingerprint

Cite this