Adaptive-SAHiD Algorithm for Capacitated Arc Routing Problems

摘要

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.