  Learning how to automatically solve optimization problems has the potential
to provide the next big leap in optimization technology. The performance of
automatically learned heuristics on routing problems has been steadily
improving in recent years, but approaches based purely on machine learning are
still outperformed by state-of-the-art optimization methods. To close this
performance gap, we propose a novel large neighborhood search (LNS) framework
for vehicle routing that integrates learned heuristics for generating new
solutions. The learning mechanism is based on a deep neural network with an
attention mechanism and has been especially designed to be integrated into an
LNS search setting. We evaluate our approach on the capacitated vehicle routing
problem (CVRP) and the split delivery vehicle routing problem (SDVRP). On CVRP
instances with up to 297 customers, our approach significantly outperforms an
LNS that uses only handcrafted heuristics and a well-known heuristic from the
literature. Furthermore, we show for the CVRP and the SDVRP that our approach
surpasses the performance of existing machine learning approaches and comes
close to the performance of state-of-the-art optimization approaches.
