Solving the capacitated vehicle routing problem with timing windows using rollouts and MAX-SAT
This addresses the problem of efficient and high-quality routing for logistics and transportation, offering a tunable trade-off between computation time and solution quality, though it appears incremental as it builds on existing methods.
The paper tackles the capacitated vehicle routing problem with timing windows by proposing a hybrid approach combining reinforcement learning, policy rollouts, and a satisfiability solver, achieving solutions closer to optimal than existing learning-based methods and with shorter computation times than meta-heuristics on a public dataset.
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.