Adaptive-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

1 Citation (Scopus)


The Capacitated Arc Routing Problem (CARP) is a seminal and challenging problem in combinatorial optimization. Heuristics and meta-heuristics are usually used to address it. When designing or applying heuristics and meta-heuristics, parameter setting, that is, identifying optimal parameter setting for the algorithms, is routinely encountered. Automatic parameter setting, which is dedicated to automatically finding optimal parameter settings for the algorithms, has attracted considerable attention in recent years. However, automatic parameter setting approaches are rarely investigated for CARP. At present, when designing algorithms for CARPs, parameter settings are commonly determined by empirical experimental analysis or according to some guidelines. This paper introduces an adaptive parameter setting method using kernel density estimation to the SAHiD algorithm, which is a scalable approach to CARP, and correspondingly constitutes the so-called Adaptive-SAHiD algorithm. Experimental studies on two CARP benchmark sets with medium-scale and large-scale instances are conducted to evaluate the proposed algorithm's performance. The results show that Adaptive-SAHiD performs better than the compared algorithms, owing to the adaptive parameter setting. The Adaptive-SAHiD algorithm not only eliminates parameter setting problem for end users but also enhances the performance of the original SAHiD algorithm. © 2019 IEEE.
Original languageEnglish
Title of host publication2019 IEEE Symposium Series on Computational Intelligence, SSCI 2019
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages8
ISBN (Print)9781728124858
Publication statusPublished - Dec 2019
Externally publishedYes

Bibliographical note

This work was supported by National Key R&D Program of China (Grant No. 2017YFC0804003), the Program for Guangdong Introducing Innovative and Enterpreneuri-al Teams (Grant No. 2017ZT07X386), Shenzhen Peacock Plan (Grant No. KQTD2016112514355531), the Program for University Key Laboratory of Guangdong Province (Grant No. 2017KSYS008), and the Science and Technology Innovation Committee Foundation of Shenzhen (Grant Nos. ZDSYS201703031748284, JCYJ20180504165652917).


  • adaptive parameter setting
  • automatic parameter setting
  • capacitated arc routing problem (CARP)
  • kernel density estimation


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

Cite this