Memetic algorithm with adaptive local search for Capacitated Arc Routing Problem

Tingting YAO; Xin YAO; Shuangshuang HAN; Yingchun WANG; Dongpu CAO; Feiyue WANG

doi:10.1109/ITSC.2017.8317903

Memetic algorithm with adaptive local search for Capacitated Arc Routing Problem

Tingting YAO, Xin YAO, Shuangshuang HAN, Yingchun WANG, Dongpu CAO, Feiyue WANG

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

3 Citations (Scopus)

Abstract

The Capacitated Arc Routing Problem (CARP) is a challenging combinatorial optimization problem with wide real world applications. Since CARP is NP-hard, many heuristic and meta-heuristic approaches have been applied to solve CARP. In this paper, a novel extension memetic approach, named MAENS-Pls is proposed to improve the state-of-the-art algorithm - Memetic Algorithm with Extended Neighbourhood Search (MAENS) for CARP, in which using an adaptive probability to optimize the frequency and depth of local search. Based on the parameter optimization on all the 8 instances, experimental studies show that the proposed algorithm can significantly improve the average performance of MAENS, and there is an increase in the robust stability and convergence reliability. Furthermore, 4 new best known solutions are found by the proposed algorithm. © 2017 IEEE.

Original language	English
Title of host publication	IEEE Conference on Intelligent Transportation Systems, Proceedings, ITSC
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	836-841
Number of pages	6
Volume	2018-March
ISBN (Print)	9781538615256
DOIs	https://doi.org/10.1109/ITSC.2017.8317903
Publication status	Published - Oct 2017
Externally published	Yes

Funding

This work was supported in part by the National Natural Science Foundation of China 61501461, 61471269, 71232006, 61533019, 91520301 and 61773381; and the Early Career Development Award of SKLMCCS (Y3S9021F34).

Keywords

Adaptive Probability
Capacitated Arc Routing Problem (CARP)
Extended Neighbourhood Search
Frequency and Depth of Local Search
Memetic Algorithm

Access to Document

10.1109/ITSC.2017.8317903

Cite this

@inproceedings{ee2502ad814e49dcb5200903cb3d803d,

title = "Memetic algorithm with adaptive local search for Capacitated Arc Routing Problem",

abstract = "The Capacitated Arc Routing Problem (CARP) is a challenging combinatorial optimization problem with wide real world applications. Since CARP is NP-hard, many heuristic and meta-heuristic approaches have been applied to solve CARP. In this paper, a novel extension memetic approach, named MAENS-Pls is proposed to improve the state-of-the-art algorithm - Memetic Algorithm with Extended Neighbourhood Search (MAENS) for CARP, in which using an adaptive probability to optimize the frequency and depth of local search. Based on the parameter optimization on all the 8 instances, experimental studies show that the proposed algorithm can significantly improve the average performance of MAENS, and there is an increase in the robust stability and convergence reliability. Furthermore, 4 new best known solutions are found by the proposed algorithm. {\textcopyright} 2017 IEEE.",

keywords = "Adaptive Probability, Capacitated Arc Routing Problem (CARP), Extended Neighbourhood Search, Frequency and Depth of Local Search, Memetic Algorithm",

author = "Tingting YAO and Xin YAO and Shuangshuang HAN and Yingchun WANG and Dongpu CAO and Feiyue WANG",

year = "2017",

month = oct,

doi = "10.1109/ITSC.2017.8317903",

language = "English",

isbn = "9781538615256",

volume = "2018-March",

pages = "836--841",

booktitle = "IEEE Conference on Intelligent Transportation Systems, Proceedings, ITSC",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

address = "United States",

}

Memetic algorithm with adaptive local search for Capacitated Arc Routing Problem. / YAO, Tingting; YAO, Xin; HAN, Shuangshuang et al.
IEEE Conference on Intelligent Transportation Systems, Proceedings, ITSC. Vol. 2018-March Institute of Electrical and Electronics Engineers Inc., 2017. p. 836-841.

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

TY - GEN

T1 - Memetic algorithm with adaptive local search for Capacitated Arc Routing Problem

AU - YAO, Tingting

AU - YAO, Xin

AU - HAN, Shuangshuang

AU - WANG, Yingchun

AU - CAO, Dongpu

AU - WANG, Feiyue

PY - 2017/10

Y1 - 2017/10

N2 - The Capacitated Arc Routing Problem (CARP) is a challenging combinatorial optimization problem with wide real world applications. Since CARP is NP-hard, many heuristic and meta-heuristic approaches have been applied to solve CARP. In this paper, a novel extension memetic approach, named MAENS-Pls is proposed to improve the state-of-the-art algorithm - Memetic Algorithm with Extended Neighbourhood Search (MAENS) for CARP, in which using an adaptive probability to optimize the frequency and depth of local search. Based on the parameter optimization on all the 8 instances, experimental studies show that the proposed algorithm can significantly improve the average performance of MAENS, and there is an increase in the robust stability and convergence reliability. Furthermore, 4 new best known solutions are found by the proposed algorithm. © 2017 IEEE.

AB - The Capacitated Arc Routing Problem (CARP) is a challenging combinatorial optimization problem with wide real world applications. Since CARP is NP-hard, many heuristic and meta-heuristic approaches have been applied to solve CARP. In this paper, a novel extension memetic approach, named MAENS-Pls is proposed to improve the state-of-the-art algorithm - Memetic Algorithm with Extended Neighbourhood Search (MAENS) for CARP, in which using an adaptive probability to optimize the frequency and depth of local search. Based on the parameter optimization on all the 8 instances, experimental studies show that the proposed algorithm can significantly improve the average performance of MAENS, and there is an increase in the robust stability and convergence reliability. Furthermore, 4 new best known solutions are found by the proposed algorithm. © 2017 IEEE.

KW - Adaptive Probability

KW - Capacitated Arc Routing Problem (CARP)

KW - Extended Neighbourhood Search

KW - Frequency and Depth of Local Search

KW - Memetic Algorithm

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

U2 - 10.1109/ITSC.2017.8317903

DO - 10.1109/ITSC.2017.8317903

M3 - Conference paper (refereed)

SN - 9781538615256

VL - 2018-March

SP - 836

EP - 841

BT - IEEE Conference on Intelligent Transportation Systems, Proceedings, ITSC

PB - Institute of Electrical and Electronics Engineers Inc.

ER -

Memetic algorithm with adaptive local search for Capacitated Arc Routing Problem

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this