  The vehicle routing problem is a well known class of NP-hard combinatorial
optimisation problems in literature. Traditional solution methods involve
either carefully designed heuristics, or time-consuming metaheuristics. Recent
work in reinforcement learning has been a promising alternative approach, but
has found it difficult to compete with traditional methods in terms of solution
quality. This paper proposes a hybrid approach that combines reinforcement
learning, policy rollouts, and a satisfiability solver to enable a tunable
tradeoff between computation times and solution quality. Results on a popular
public data set show that the algorithm is able to produce solutions closer to
optimal levels than existing learning based approaches, and with shorter
computation times than meta-heuristics. The approach requires minimal design
effort and is able to solve unseen problems of arbitrary scale without
additional training. Furthermore, the methodology is generalisable to other
combinatorial optimisation problems.
