# Quantum Annealing of Vehicle Routing Problem with Time, State and Capacity

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Mar 2019.

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

- [QOPTLib: a Quantum Computing Oriented Benchmark for Combinatorial Optimization Problems](https://mlsanity.com/paper/2404.15852/) (2024)
- [Quantum Artificial Intelligence: A Brief Survey](https://mlsanity.com/paper/2408.10726/) (2024)
- [GNN-Guided Graph Coarsening and Adaptive QUBO Penalties for the Capacitated Vehicle Routing Problem with Time Windows on a Quantum Annealer](https://mlsanity.com/paper/2609.04593/) (2026)
- [Optimizing Package Delivery with Quantum Annealers: Addressing Time-Windows and Simultaneous Pickup and Delivery](https://mlsanity.com/paper/2504.01560/) (2025)
- [Quantum Approaches to Urban Logistics: From Core QAOA to Clustered Scalability](https://mlsanity.com/paper/2512.10813/) (2025)

## Abstract (arXiv)

We propose a brand-new formulation of capacitated vehicle routing problem (CVRP) as quadratic unconstrained binary optimization (QUBO). The formulated CVRP is equipped with time-table which describes time-evolution of each vehicle. Therefore, various constraints associated with time are successfully realized. With a similar method, constraints of capacities are also introduced, where capacitated quantities are allowed to increase and decrease according to the cities which vehicles arrive. As a bonus of capacity-qubits, one also obtains a description of state, which allows us to set a variety of traveling rules, depending on each state of vehicles. As a consistency check, the proposed QUBO formulation is also evaluated by quantum annealing with D-Wave 2000Q.