Click here to flash read.
The Adaptive Large Neighborhood Search (ALNS) algorithm has shown
considerable success in solving complex combinatorial optimization problems
(COPs). ALNS selects various heuristics adaptively during the search process,
leveraging their strengths to find good solutions for optimization problems.
However, the effectiveness of ALNS depends on the proper configuration of its
selection and acceptance parameters. To address this limitation, we propose a
Deep Reinforcement Learning (DRL) approach that selects heuristics, adjusts
parameters, and controls the acceptance criteria during the search process. The
proposed method aims to learn, based on the state of the search, how to
configure the next iteration of the ALNS to obtain good solutions to the
underlying optimization problem. We evaluate the proposed method on a
time-dependent orienteering problem with stochastic weights and time windows,
used in an IJCAI competition. The results show that our approach outperforms
vanilla ALNS and ALNS tuned with Bayesian Optimization. In addition, it
obtained better solutions than two state-of-the-art DRL approaches, which are
the winning methods of the competition, with much fewer observations required
for training. The implementation of our approach will be made publicly
available.