Online Parameter Tuned SAHiD Algorithm for Capacitated Arc Routing Problems

Changwu HUANG, Yuanxiang LI, Xin YAO

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


The Capacitated Arc Routing Problem (CARP) is a general and challenging arc routing problem. As the problem size increasing, exact methods are not applicable, and heuristic and meta-heuristic algorithms are promising approaches to solve it. To obtain good performance, parameter values of heuristics or meta-heuristics should be properly set. In recent years, automatic parameter tuning, which includes off-line and online parameter tuning, has attracted considerable attention in the evolutionary computation community. At present, parameters are usually determined through simple off-line parameter tuning, such as empirical analysis or grid search, when designing algorithms for CARP. However, using off-line parameter tuning on CARP has some disadvantages, among which the computational cost is the serious one. This work proposed an online parameter tuning approach using exponential recency-weighted kernel density estimation (ERW-KDE), and combines it with the SAHiD algorithm, which is an hierarchical decomposition based algorithm for CARP, to constitute the online parameter tuned SAHiD (OPT-SAHiD) algorithm. The experimental results show that OPT-SAHiD significantly outperforms the compared algorithms on two CARP benchmark sets owing to the proposed online automatic parameter tuning approach. The proposed online automatic parameter tuning approach based on ERW-KDE not only improves the performance of SAHiD algorithm, but also removes the additional computational overhead required for offline parameter tuning. © 2020 IEEE.
Original languageEnglish
Title of host publication2020 IEEE Congress on Evolutionary Computation, CEC 2020 - Conference Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Print)9781728169293
Publication statusPublished - Jul 2020
Externally publishedYes

Bibliographical note

This work was supported by Guangdong Basic and Applied Basic Research Foundation (Grant No. 2019A1515110575), Guangdong Provincial Key Laboratory (Grant No. 2020B121201001), the Program for Guangdong Introducing Innovative and Enterpreneurial Teams (Grant No. 2017ZT07X386), Shenzhen Science and Technology Program (Grant No. KQTD2016112514355531), the Program for University Key Laboratory of Guangdong Province (Grant No. 2017KSYS008).


  • automatic parameter tuning
  • Capacitated arc routing problem
  • kernel density estimation
  • online parameter tuning


Dive into the research topics of 'Online Parameter Tuned SAHiD Algorithm for Capacitated Arc Routing Problems'. Together they form a unique fingerprint.

Cite this