Learning-Enhanced Neighborhood Selection for the Vehicle Routing Problem
  with Time Windows
Willem Feijen Guido Schäfer Koen Dekker Seppo Pieterse
Large Neighborhood Search (LNS) is a universal approach that is broadly
applicable and has proven to be highly efficient in practice for solving
optimization problems. We propose to integrate machine learning (ML) into LNS
to assist in deciding which parts of the solution should be destroyed and
repaired in each iteration of LNS. We refer to our new approach as
Learning-Enhanced Neighborhood Selection (LENS for short). Our approach is
universally applicable, i.e., it can be applied to any LNS algorithm to amplify
the workings of the destroy algorithm. In this paper, we demonstrate the
potential of LENS on the fundamental Vehicle Routing Problem with Time Windows
(VRPTW). We implemented an LNS algorithm for VRPTW and collected data on
generated novel training instances derived from well-known, extensively
utilized benchmark datasets. We trained our LENS approach with this data and
compared the experimental results of our approach with two benchmark
algorithms: a random neighborhood selection method to show that LENS learns to
make informed choices and an oracle neighborhood selection method to
demonstrate the potential of our LENS approach. With LENS, we obtain results
that significantly improve the quality of the solutions.