Runtime-Sensitive Learned Operator Selection in ALNS: Testing Improvements to Adaptive Operator Selection while Optimizing Runtime

Abstract

We propose and test two variations of the Adaptive Large Neighborhood Search (ALNS) meta-heuristic: First, we add time
sensitivity to the operator selection scheme to optimize the ALNS for both solution quality and runtime. We reward compar-
atively slow operators with reduced rewards for finding improvements. This ensures that the meta-heuristic is slowed down
less by operators which consistently find good solutions but take long to do so. Secondly, we replace the Adaptive Layer with a
Learned Operator Selection Policy trained via Deep-Q Learning. The training takes both solution quality and operator runtime
into account. We test our algorithms against classic ALNS as well as random operator selection. We perform an analysis of
how operator portfolios affect performance. Our chosen problem domain is the Capacitated Vehicle Routing Problem with
100 to 400 customer nodes.

Keywords: adaptive large neighborhood search; vehicle routing; optimization; logistics; deep learning