Routing and logistics as QUBOs

Tours, penalties, decoded feasibility

The Problem

Operational framing

Logistics teams care about kilometres or hours, but optimisation layers must first forbid impossible routes. QUBO encodings therefore add large penalties for double visits or empty slots so illegal strings sit in high-energy tails.

The routing walkthrough pairs the mathematics with a visual sanity check similar to the schematic below.

Example: cities as nodes; the polyline is one candidate tour (closed loop).

The Challenge

Penalty engineering dominates engineering time

The Challenge

What makes a routing QUBO brittle

If penalties are mis-scaled relative to true distances, the optimiser minimises constraint violations while ignoring travel cost, or vice versa. On small instances, tweak penalties until illegal tours visibly disappear from low-energy samples.

Decoder responsibilities

Permutation check: reject any string that is not one-hot per row and column.

Distance accounting: only count edges present in the decoded tour.

Symmetry: remember undirected distance matrices halve duplicated edges when appropriate.

The Solution

Hamiltonian viewpoint matches software stacks

The Solution

Why practitioners still mention Hamiltonians

Once in Ising form, the problem slots into the same variational machinery as finance. Software libraries expose Pauli sums; hardware providers compile them to native gates. The business decoder stays classical.

One-hot style layout and distance matrix heatmap (evidence pack)

Implementation

Penalty QUBO + sampler + decoder

Implementation

Part C emphasises the same triple as finance: build Q with penalties, map to Ising, sample, decode, compare to brute force on tiny n.

Replace draw_topk_bitstrings with your variational circuit or simulated annealing baseline.

Sketch of the inner loop

Q, offset = tsp_qubo_with_penalties(dist, penalty=pen)
h, J = qubo_to_ising(Q)
samples = draw_topk_bitstrings(gamma, beta, k=256)
legal = [(bits, qubo_energy(bits, Q) + offset) for bits in samples if is_tour(bits)]
best = min(legal, key=lambda t: t[1])

Logistics and route choice (companion code)

Summary

Tour length 14 in toy distance units

Summary

What 14 means

On the three-city demonstration, both brute-force QUBO evaluation and the best feasible draw among the top sampled strings recovered total length 14 in the same integer units as the distance matrix. Trailing zeros are formatting only.

Sampler mass across tour energies (toy instance)

Continue this saga

Next chapter: Tensor trains and quantum-inspired compression.