  Routing problems are a class of combinatorial problems with many practical
applications. Recently, end-to-end deep learning methods have been proposed to
learn approximate solution heuristics for such problems. In contrast, classical
dynamic programming (DP) algorithms can find optimal solutions, but scale badly
with the problem size. We propose Deep Policy Dynamic Programming (DPDP), which
aims to combine the strengths of learned neural heuristics with those of DP
algorithms. DPDP prioritizes and restricts the DP state space using a policy
derived from a deep neural network, which is trained to predict edges from
example solutions. We evaluate our framework on the travelling salesman problem
(TSP) and the vehicle routing problem (VRP) and show that the neural policy
improves the performance of (restricted) DP algorithms, making them competitive
to strong alternatives such as LKH, while also outperforming other `neural
approaches' for solving TSPs and VRPs with 100 nodes.
