Vehicle routing problems (VRPs) form a class of combinatorial problems with
wide practical applications. While previous heuristic or learning-based works
achieve decent solutions on small problem instances of up to 100 cities, their
performance deteriorates in large problems. This article presents a novel
learning-augmented local search framework to solve large-scale VRP. The method
iteratively improves the solution by identifying appropriate subproblems and
$\textit{delegating}$ their improvement to a black box subsolver. At each step,
we leverage spatial locality to consider only a linear number of subproblems,
rather than exponential. We frame subproblem selection as regression and train
a Transformer on a generated training set of problem instances. Our method
accelerates state-of-the-art VRP solvers by 10x to 100x while achieving
competitive solution qualities for VRPs with sizes ranging from 500 to 3000.
Learned subproblem selection offers a 1.5x to 2x speedup over heuristic or
random selection. Our results generalize to a variety of VRP distributions,
variants, and solvers.

本文使用学习增强的局部搜索框架来解决大规模车辆路径问题（VRP），其中使用回归来训练 Transformer 模型来选择恰当的子问题，并且在实验中表现优异。