Variable neighborhood decomposition for Large Scale Capacitated Arc Routing Problem

Yi MEI, Xiaodong LI, Xin YAO

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

15 Citations (Scopus)


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 languageEnglish
Title of host publicationProceedings of the 2014 IEEE Congress on Evolutionary Computation, CEC 2014
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages8
ISBN (Print)9781479914883
Publication statusPublished - Jul 2014
Externally publishedYes


Dive into the research topics of 'Variable neighborhood decomposition for Large Scale Capacitated Arc Routing Problem'. Together they form a unique fingerprint.

Cite this