# Solving the capacitated vehicle routing problem with timing windows using rollouts and MAX-SAT

arXiv: https://arxiv.org/abs/2206.06618 · HTML: https://mlsanity.com/paper/2206.06618/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 39 references that are in the map.
- First posted on arXiv 14 Jun 2022.

## Builds on (most cited first, 9 of 9)

- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Reinforcement Learning for Solving the Vehicle Routing Problem](https://mlsanity.com/paper/1802.04240/) (2018)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [Thinking Fast and Slow with Deep Learning and Tree Search](https://mlsanity.com/paper/1705.08439/) (2017)
- [Combinatorial Optimization by Graph Pointer Networks and Hierarchical Reinforcement Learning](https://mlsanity.com/paper/1911.04936/) (2019)
- [Reinforcement Learning with Combinatorial Actions: An Application to Vehicle Routing](https://mlsanity.com/paper/2010.12001/) (2020)
- [Learning to Solve Combinatorial Optimization Problems on Real-World Graphs in Linear Time](https://mlsanity.com/paper/2006.03750/) (2020)
- [Multi-Vehicle Routing Problems with Soft Time Windows: A Multi-Agent Reinforcement Learning Approach](https://mlsanity.com/paper/2002.05513/) (2020)
- [Fast Approximate Solutions using Reinforcement Learning for Dynamic Capacitated Vehicle Routing with Time Windows](https://mlsanity.com/paper/2102.12088/) (2021)

## Built on by (most cited first, 2 of 2)

- [Multi-Agent Learning of Efficient Fulfilment and Routing Strategies in E-Commerce](https://mlsanity.com/paper/2311.16171/) (2023)
- [Enhancing Local Search for MaxSAT with Deep Differentiation Clause Weighting](https://mlsanity.com/paper/2512.05619/) (2025)

## Abstract (arXiv)

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.