Case Study 37.1: The Logistics Pilot

The situation

A regional distribution company runs 240 delivery vehicles. Their route optimizer is a commercial solver that has been tuned for eleven years; it produces daily routes in about four minutes and nobody has looked closely at it in a long time.

A quantum computing vendor proposes a pilot. The pitch is specific and not unreasonable:

Vehicle routing is a combinatorial optimization problem. QAOA is the near-term quantum algorithm for combinatorial optimization. Your problem sizes are within reach of current hardware if formulated as QUBO. Six-month pilot, fixed price.

The operations director asks their analyst — who has read this chapter — for a recommendation.

Step 1: find out what the incumbent actually does

The analyst's first move is not about quantum computing at all. They open the solver's log.

The commercial solver is a branch-and-bound code. On yesterday's instance it reported:

   best solution found     14,208.4 km
   best bound              14,201.9 km
   gap                     0.046%
   time                    3m 51s

The incumbent already produces a certificate. It is not merely returning a good route; it is returning a route and a proof that no route is more than 0.046% better. §37.7's finding is not a quantum-specific observation — it is how serious optimization software has worked for decades, and the incumbent's users have been relying on it without noticing.

That single log line reframes the pilot. The question is no longer "can QAOA find a good route." It is "can QAOA replace a solver that proves its answers are within 0.05% of optimal?"

Step 2: establish the bar, not the floor

The vendor's materials compare QAOA against random assignment and against greedy nearest-neighbour construction. Both comparisons are favourable.

Both are also the wrong comparison, and §37.1's arithmetic shows why. On MaxCut, random assignment scores 0.5 of the edges with no algorithm at all. Beating it is not evidence of anything. The bar is the best classical method, and in this case the analyst can name it exactly, because it is running in production and printing its own gap.

⚠️ Note the structure of the vendor's error, because it is not dishonesty and it recurs. Comparing against a weak baseline is easier to do well — you get a clean chart, a large multiple, and a reproducible result. Comparing against the incumbent requires understanding the incumbent. The flattering comparison is also the cheaper one to run, which is Chapter 21 §21.7's lesson and Chapter 36 Case Study 36.1's, arriving a third time.

Step 3: price the instance

The company's daily problem has 240 vehicles and roughly 3,000 stops. A QUBO formulation with one binary variable per (vehicle, stop, position) triple is far beyond any current device, so the vendor proposes a decomposition: cluster the stops geographically, solve each cluster with QAOA, stitch.

The analyst prices one cluster — 20 stops, formulated as a 20-qubit problem:

>>> from vqelab.combinatorial import qaoa_shot_budget
>>> b = qaoa_shot_budget(p=3, epsilon=0.01)
>>> b["total_shots"], b["device_seconds"]
(13000000, 1300.0)

Twenty-two minutes of exclusive device time per cluster, at $p=3$ and 1% precision, assuming 100 optimizer iterations converge. With roughly 150 clusters that is 55 hours of QPU time per daily route — against a four-minute end-to-end classical solve that handles the whole problem at once, including the interactions between clusters that the decomposition throws away.

And the decomposition is not free. Routing quality lives substantially in the cross-cluster decisions; a method that must partition the problem before it can start has given up the part the solver is best at.

Step 4: the recommendation, and its shape

The analyst's memo does not say "quantum computing does not work."

Recommend declining this pilot as scoped, and I want to be precise about why.

Our solver returns a route and a bound. Yesterday it proved its answer was within 0.046% of optimal. QAOA returns a bitstring with no bound — so even a good QAOA route would leave us unable to tell it apart from a bad one without running the classical solver to check. At that point we have paid for both.

This is not a hardware-maturity issue and it does not improve when the devices do. It is a difference in what the two methods produce.

Cost, for completeness: ~22 minutes of QPU per 20-stop cluster at 1% precision, ~150 clusters, ~55 hours per daily route, against 3m 51s for the whole problem classically. The decomposition also discards the cross-cluster structure our solver is best at.

What I would fund instead: the vendor is right that this is a combinatorial optimization problem and right that we should be looking at our solver. We have not benchmarked it against alternatives since 2015. A three-week bake-off against two modern solvers would likely find more improvement than this pilot, at a fraction of the cost — and if it does not, that is a much stronger reason to look at exotic methods.

What this case study is about

The analyst won the argument with a log line. The incumbent's 0.046% gap was on screen every day and nobody had read it — which is why §37.7's certificate finding matters practically and not just theoretically. Optimization practitioners rely on bounds constantly; the reliance is invisible until something proposes to remove it.

Three of this book's threads meet here:

  • Chapter 21 §21.7 — benchmarking against the method nobody uses.
  • Chapter 36 Case Study 36.1 — a correct number that answers a question nobody asked.
  • §37.6 — a good mean and a bad answer, which is what "we found a route" conceals.

The general form: when a new method is proposed, find out what the incumbent produces, not just how well it scores. Score is one dimension. Certificates, warm-start behaviour, incrementality, explainability, and failure modes are others, and a method can win on score while losing on all of them.

Questions

  1. The analyst priced one cluster at $p=3$ and $\epsilon = 0.01$. What would $\epsilon = 0.05$ do to the total, and is 5% precision defensible for this application? Compute it.
  2. The vendor could reply: "routing does not need a certificate — you just need a route that is good enough." Is that right? Construct the strongest version of that argument, then rebut it using something in the operations director's job rather than in the mathematics.
  3. The decomposition discards cross-cluster structure. Estimate — with stated assumptions — how much route quality that costs, and say what measurement would settle it.
  4. The analyst recommends a classical solver bake-off instead. What result from that bake-off would make the quantum pilot more attractive, and why?
  5. The hard one. Suppose the vendor returns with warm-started QAOA: initialize from the classical solver's solution and use QAOA to improve it locally. This removes the optimization loop, keeps the certificate (the classical bound still applies), and only needs to beat the incumbent by a little. Is that a better proposal? Price it, and say what you would need to see before funding it.