Reviews: Reinforcement Learning for Solving the Vehicle Routing Problem

Many combinatorial optimization problems are only solvable exactly for small problem sizes, so various heuristics are used to find approximate solutions for larger problem sizes. Recently, there have been a number of attempts to use neural networks to learn these heuristics. This work is focused on the vehicle routing problem, a generalization of the well-known traveling salesman problem and task of significant real world interest. The solution explored in the paper is to use standard RL techniques (REINFORCE and A3C) with a slightly modified pointer net architecture. The modification is that the encoder is feedforward convolutional network rather than an RNN, meaning the network is invariant to the ordering of the input sequence.