  This paper presents an approach to learn the local-search heuristics that
iteratively improves the solution of Vehicle Routing Problem (VRP). A
local-search heuristics is composed of a destroy operator that destructs a
candidate solution, and a following repair operator that rebuilds the
destructed one into a new one. The proposed neural network, as trained through
actor-critic framework, consists of an encoder in form of a modified version of
Graph Attention Network where node embeddings and edge embeddings are
integrated, and a GRU-based decoder rendering a pair of destroy and repair
operators. Experiment results show that it outperforms both the traditional
heuristics algorithms and the existing neural combinatorial optimization for
VRP on medium-scale data set, and is able to tackle the large-scale data set
(e.g., over 400 nodes) which is a considerable challenge in this area.
Moreover, the need for expertise and handcrafted heuristics design is
eliminated due to the fact that the proposed network learns to design the
heuristics with a better performance. Our implementation is available online.
