Capacitated Vehicle Routing (CVRP)

Inspiration

Vehicle routing connects an everyday challenge—delivering goods efficiently—with a difficult optimization problem: how do we serve every customer without exceeding vehicle capacity?

Inspired by Pasqal’s neutral-atom challenge, we explored how quantum computing could support the customer-grouping stage of the Capacitated Vehicle Routing Problem (CVRP). Our central question was not whether quantum computing is faster, but how to translate a constrained logistics problem into a model that neutral-atom hardware can approximately represent.

What it does

Our project groups customers into vehicles while respecting vehicle capacities and encouraging geographically compact groups.

It compares three QUBO formulations—binary slack, unbalanced penalization, and variable reduction—using both classical simulated annealing and quantum emulation. We benchmark small, medium, and large instances containing 4, 10, and 15 customers.

The workflow reports variable counts, capacity-demand ratios, feasible-solution rates, and solution quality against exact classical clustering references. It also visualizes customer groups, atom layouts, and laser pulses.

Our quantum optimization focuses on clustering, not visit order. Separate classical evaluation tools can assess routes within fixed groups and compare them with full-CVRP references.

How we built it

We built the project in Python using Jupyter notebooks, NumPy, pandas, and Matplotlib, with shared modules for instance validation, optimization, evidence collection, and reporting.

First, we formulated customer assignments and capacity constraints as QUBOs. We established exact classical clustering references through enumeration for smaller problems and capacity-constrained subset dynamic programming for the largest tier.

Next, we used Pulser to map binary variables to atoms and construct neutral-atom pulse sequences. Atom separation determines pairwise Rydberg interactions, while a global laser controls excitation amplitude and detuning. We ran these sequences locally with state-vector emulation for S and matrix-product-state emulation for M and L.

Finally, we assembled saved classical and quantum outputs into a reproducible comparison notebook. No physical QPU submission was performed.

Challenges we ran into

The biggest challenge was that writing a QUBO is not the same as implementing it faithfully on quantum hardware. Desired pairwise coefficients cannot be chosen independently when they must arise from distances in a two-dimensional atom array. A global detuning also cannot reproduce different linear coefficients for every variable.

Encoding capacity introduced another trade-off. Binary slack provides a clear feasibility guarantee for the target QUBO but requires additional atoms. Smaller encodings save variables, yet their penalty choices can alter which solutions are preferred.

Quantum emulation also became more demanding as problem size increased. We needed explicit time and memory limits, recorded approximation settings, and reporting that distinguished missing runs, failed runs, and completed runs with no feasible answer.

Accomplishments that we're proud of

Built an end-to-end comparison of six classical/quantum methods across three problem tiers.
Implemented a binary-slack encoding with a justified penalty bound and independent target-model checks.
Reduced the largest formulation from 80 variables with binary slack to 60 with unbalanced penalization, with a 64-variable alternative.
Quantified hardware-mapping errors instead of treating a legal atom layout as an exact implementation.
Preserved raw samples and reported feasibility without repairing quantum answers into valid solutions.
Created explanatory notebooks, visualizations, and LaTeX tables that make the modeling and hardware trade-offs easier to understand.

What we learned

We learned to separate three questions: Is the mathematical model correct? Does the physical Hamiltonian represent it accurately? Does the pulse produce useful solutions? Success at one stage does not guarantee success at the next.

We also learned that fewer variables do not automatically mean better optimization. Penalty strength, unwanted interactions, unequal linear terms, and pulse dynamics all affect the outcome.

Most importantly, exact classical references and transparent reporting are essential. Feasibility, solution quality, embedding fidelity, and computational resources tell us more than a single best result—and our experiments do not establish quantum speedup.

What's next for Capacitated Vehicle Routing (CVRP)

Our next steps are to improve atom placement, investigate more expressive detuning controls where supported, and test broader pulse schedules. We also want to validate penalty choices on held-out instances rather than tuning and evaluating on the same benchmark inputs.

For larger problems, we would expand emulator-convergence studies and explore decomposition strategies that keep quantum subproblems within practical resource limits.

To move closer to full CVRP, we would more systematically evaluate the routes produced by our customer groups and investigate how clustering decisions affect total travel distance. A future hardware run would then let us compare physical-device behavior with our current emulation results.