Guide

Quantum computing for logistics: routing and scheduling, and what the trials show

Vehicle routing, scheduling and loading are combinatorial optimisation problems, and each can be rewritten as a QUBO that a quantum annealer or a QAOA circuit accepts. That makes logistics a natural candidate, and it is the most piloted industry use of quantum optimisation. No pilot has beaten the classical solvers that run logistics today: the published trials solve small instances or hand most of the work to classical code. What a logistics team can use now is the formulation itself, on classical and quantum-inspired solvers.

Updated

The short answer

The problems
Vehicle routing, delivery sequencing, crew and machine scheduling, container and truck loading, network design: all choices among a finite number of combinations
How they reach a quantum computer
As a QUBO or Ising model: binary variables, an objective with terms of at most two variables, and constraints turned into penalties[1]
The cost of the encoding
A tour through NN stops takes about N2N^2 binary variables, one qubit each, before any overhead of the hardware
What the trials ran
Small instances on QPUs, or company-scale instances cut into pieces with classical code doing most of the work; most published solutions are hybrid[9]
The classical bar
Exact solvers have proved an optimal tour through 85,900 cities[13], and heuristics route fleets of thousands of stops daily
Quantum advantage
None shown on a logistics problem, on annealers or on gate-based machines
In eigenkit
QUBO and Ising to state and check the problem, exact enumeration for small sizes, and QAOA on a simulator or a QPU backend. No annealing or simulated bifurcation solver

Why logistics is the usual example

A dispatcher choosing which truck visits which customer in which order is choosing one combination out of a number that grows factorially with the stops. The same structure sits under crew rosters, berth and gate assignment, warehouse picking and container loading. These problems are NP-hard, companies solve them every day with heuristics that are good but not provably optimal, and a small improvement is worth money. That is the profile people look for when they ask where a quantum computer might help.

It is also a class of problem with a known route onto quantum hardware. Lucas collected formulations of the standard hard problems, the travelling salesman among them, as Ising models that a quantum annealer minimises[1], and the same models are the cost function of QAOA on gate-based machines. Routing with capacities and time windows has been worked out in several alternative encodings, which differ in how many qubits they need and how hard the result is to solve[6].

What the route does not come with is a proof of speed-up. For these problems no quantum algorithm is known to beat the best classical ones by more than a polynomial factor, and the heuristic quantum methods have no guarantee at all. Whether they help is an empirical question, which is why the trials matter.

How a route becomes qubits

The standard encoding of a tour, the one the code below uses. The QUBO page covers the general method.

  1. One binary variable per city and stop

    xc,s=1x_{c,s} = 1 means city cc is visited at stop ss of the tour. With the depot fixed as the start, NN cities take (N−1)2(N-1)^2 variables.

  2. The distance as products of two variables

    If city cc is at stop ss and city dd at stop s+1s + 1, the tour pays the distance between them: the term Dcd xc,s xd,s+1D_{cd}\, x_{c,s}\, x_{d,s+1}. Summed over all pairs and stops, this is the length of the tour.

  3. Constraints as penalties

    Every city must appear at exactly one stop and every stop must hold exactly one city. Each rule becomes a term P (∑x−1)2P\,(\sum x - 1)^2, which is zero when the rule holds and costs PP or more when it does not.

  4. Choose the penalty weight

    Too small, and the cheapest answer skips cities. Too large, and the distances become a small ripple on a landscape of penalties, which is hard for any solver and worse for a noisy one.

  5. Solve, then check the answer is a tour

    A solver returns a bit string. It is a route only if it satisfies every constraint, and most bit strings do not.

    Run it on a real QPU with EigenOrbit RouterIn eigenkit: pip install "eigenkit[router]", then provider=RouterConfig(device=...) (docs).

A four-city tour as a QUBO, solved exactly and with QAOA

import itertools
import numpy as np
from eigenkit.optimization import QAOA, QUBO

D = np.array([[0, 2, 9, 10], [2, 0, 6, 4], [9, 6, 0, 3], [10, 4, 3, 0]], dtype=float)
n = 3                                   # the depot is city 0; cities 1 to 3 take stops 0 to 2
x = lambda city, stop: (city - 1) * n + stop

def tour_qubo(penalty):
    Q = np.zeros((n * n, n * n))
    def add(i, j, w):
        Q[min(i, j), max(i, j)] += w
    for c in range(1, 4):
        add(x(c, 0), x(c, 0), D[0, c])              # from the depot to the first stop
        add(x(c, n - 1), x(c, n - 1), D[c, 0])      # from the last stop back
        for d, s in itertools.product(range(1, 4), range(n - 1)):
            if c != d:
                add(x(c, s), x(d, s + 1), D[c, d])  # c at stop s, d at the next one
    once = [[x(c, s) for s in range(n)] for c in range(1, 4)]    # every city at one stop
    once += [[x(c, s) for c in range(1, 4)] for s in range(n)]   # every stop has one city
    for group in once:                               # penalty * (sum - 1)^2
        for i in group:
            add(i, i, -penalty)
        for i, j in itertools.combinations(group, 2):
            add(i, j, 2 * penalty)
    return QUBO(Q, constant=penalty * len(once))

qubo = tour_qubo(penalty=20.0)
print(qubo.brute_force())                 # ((0, 0, 1, 1, 0, 0, 0, 1, 0), 18.0)
print(tour_qubo(penalty=1.0).brute_force())   # ((0, 0, 0, 0, 0, 0, 0, 1, 0), 4.0)

strings = list(itertools.product([0, 1], repeat=n * n))
valid = [np.array(s).reshape(n, n).sum(0).tolist() == [1] * n
         and np.array(s).reshape(n, n).sum(1).tolist() == [1] * n for s in strings]
best = [qubo.energy(list(s)) == 18.0 for s in strings]
print(sum(best), sum(valid), len(strings))    # 2 6 512

for layers in (1, 2, 3):
    p = QAOA(layers=layers, random_state=0).solve(qubo).probabilities
    print(layers, round(float(p[best].sum()), 3), round(float(p[valid].sum()), 3))
# 1 0.018 0.023
# 2 0.006 0.013
# 3 0.039 0.11

Four cities, nine qubits, on eigenkit's exact simulator. Enumeration finds the shortest tour, depot, city 2, city 3, city 1 and back, of length 18. With the penalty set to 1 the minimum visits a single city: the constraints were written correctly and lost to the objective. Of the 512 bit strings only 6 are tours and 2 are the shortest one, in its two directions. The last three lines are the probability that QAOA's final state gives the shortest tour, and any valid tour, when measured.

Reading the example

A uniformly random bit string is the shortest tour with probability 2 in 512, about 0.4%, and a valid tour with probability about 1.2%. After three layers, QAOA gives the shortest tour 3.9% of the time and some valid tour 11% of the time. That is ten times better than chance, and it still means that nine measurements in ten return something that is not a route at all.

More layers did not help steadily. Two layers did worse than one here, because the optimiser found a poorer set of angles: the landscape of penalties is rough, and the result depends on where the search starts. All of this is on a noiseless simulator.

And the instance has three orderings to compare. A person solves it by inspection, and a loop over the six permutations solves it exactly. The example is useful for one thing: it shows every step of the method, and where the method loses probability, on a case small enough to check.

How the encoding grows

Binary variables for one vehicle visiting NN points with the start fixed, (N−1)2(N-1)^2, and the number of distinct tours, (N−1)!/2(N-1)!/2. Each variable is one logical qubit; hardware with limited connectivity needs several physical qubits for each.

Points NBinary variablesDistinct toursWhere this size stands
493The example above; exact on any laptop
51612The size of published QAOA studies of vehicle routing[5]
1081181,440Trivial for a classical solver; 81 qubits is already beyond exact state-vector simulation
20361about 6×10166 \times 10^{16}Solved exactly by classical methods
502,401about 3×10623 \times 10^{62}About the size of one truck's sub-problem in a company-scale study[7]
1009,801about 5×101555 \times 10^{155}Routine for classical heuristics and exact solvers
85,900about 7.4×1097.4 \times 10^{9}beyond writing downSolved to proven optimality classically[13]

Variable counts and tour counts are computed from the formulas. Capacities, time windows and several vehicles add variables on top.

What the published trials ran

TrialProblemWhat ran on quantum hardwareWhat it shows
Volkswagen, traffic flow, 2017[2]Redistributing cars over routes in a dense road networkParts of the problem on a D-Wave annealer, inside a hybrid quantum and classical methodA real-world problem can be mapped and run; the QPU's limited size and connectivity forced the hybrid approach
Volkswagen and Lisbon, bus routes, 2019[4]Live routing of conference shuttle busesRoute optimisation calls to a D-Wave QPU from a navigation app, with live traffic dataA quantum processor can sit in a live service; the paper makes no claim of beating a classical router
Capacitated vehicle routing, 2019[3]Routing vehicles with capacity limitsSub-problems on a D-Wave annealer after the problem is partitioned classicallyThe mapping to QUBO is the hard part, and the study asks whether the hybrid method pays off against classical ones
QAOA for vehicle routing, 2022[5]Instances of 4 and 5 locations with 2 or 3 vehicles[5]Nothing: simulated in QiskitQAOA's result depends on the optimiser, the depth, the starting angles and the instance itself
Supply chain routing, 2022[7]Multi-truck routing at the scale of a company's operationsNothing: one truck at a time, each a problem of about 2,500 binary variables[7], solved with simulated annealing and a hybrid cloud solver as stand-insThe workflow is ready for quantum hardware that does not exist yet, and already useful with classical annealing
Transport optimisation, 2022[8]Capacitated vehicle routing, with a reduced encodingA prototype circuit on a real device, with performance-enhancing toolingCircuit performance improved by more than 20 times[8] over the unoptimised run; no comparison of solution quality with classical routing

The pattern across the literature, as a 2024 overview of the field also finds: annealing dominates, most solutions are hybrid, and hardware limits the size.

What stands in the way

The encoding is expensive. A classical solver stores a tour of NN stops as NN numbers. The QUBO needs about N2N^2 bits, and almost all of the 2N22^{N^2} states it can represent are not tours. The quantum method spends most of its effort staying inside the tiny valid set, as the example shows. Encodings that build the constraints into the circuit reduce the waste and cost depth.

Noise limits depth and size. Stilck França and García-Patrón bounded what noisy devices can do on optimisation problems and concluded that substantial quantum advantages are unlikely[12] for classical optimisation at the noise rates of the time. Routing circuits are deep because distance terms connect many pairs of qubits that are not neighbours on the chip.

Error correction does not rescue a quadratic speed-up. The provable quantum gain for unstructured optimisation is quadratic, the Grover kind. Sanders and colleagues compiled the leading quantum optimisation heuristics for error-corrected hardware and found that their results discourage the notion that any quantum optimization heuristic realizing only a quadratic speedup will achieve an advantage[11] on modest fault-tolerant machines without large improvements in error correction.

The classical bar is high. Routing is one of the most studied problems in operations research. Exact methods have certified optimal tours through tens of thousands of cities[13], and commercial solvers handle capacities, time windows and driver rules that no quantum formulation carries at scale. A review of quantum optimisation by researchers from across the field asks for comparisons against these solvers, with clear metrics, before any claim is made[10].

What a logistics team can do today

  1. Write one real decision as an optimisation model

    Variables, objective, constraints. This is the step with lasting value: the model outlives any solver, and many teams find their current process was never written down this way.

  2. Solve it with a classical solver first

    A mixed-integer or constraint solver, or a routing library, gives the baseline and often the answer. Our comparison of QAOA against MILP shows how lopsided this is at small sizes.

  3. Try quantum-inspired solvers on the QUBO form

    Simulated annealing and simulated bifurcation take the same QUBO a quantum annealer would, run on ordinary hardware, and handle far larger problems than any QPU. If the QUBO form of your problem is going to work anywhere, it works here first.

  4. Run a small instance through QAOA or an annealer to learn the workflow

    A dozen qubits on a simulator, then on a QPU. The purpose is to learn what the formulation, the penalties and the noise do, not to get a route.

  5. Set the test that would change your mind

    The same instance, the same time limit, the cost of the route as the metric, against your production solver. Until a quantum run wins that test at a size you care about, it is research.

Questions

How is quantum computing used in logistics?

Routing, scheduling and loading problems are rewritten as a QUBO, a model with binary variables and penalties for broken constraints, and given to a quantum annealer or to the QAOA algorithm on a gate-based machine. In published work the quantum processor solves small instances or pieces of a larger problem, with classical code doing the rest.

Can a quantum computer solve the vehicle routing problem?

It can solve very small instances. Published QAOA studies handle four or five locations, and annealer studies cut larger problems into pieces. Classical solvers route thousands of stops and have proved optimal tours through tens of thousands of cities, so no quantum result is competitive today.

How many qubits does the travelling salesman problem need?

In the standard encoding, about N squared for N cities: one binary variable for each city at each position in the tour. Ten cities take 81 variables with the start fixed, and a hundred take 9,801. Hardware with limited connectivity needs several physical qubits per variable on top of that.

Has quantum computing improved a real logistics operation?

There have been live pilots, such as bus routing in Lisbon in 2019 that called a quantum annealer. None has published evidence that the quantum step gave better routes than a classical solver would have on the same problem. The benefit reported is usually the optimisation model itself.

Is quantum annealing or QAOA better for logistics?

Annealers take much larger problems today, thousands of variables, and dominate the published logistics work. QAOA runs on gate-based machines at a few dozen qubits. Neither has shown an advantage over classical heuristics on logistics problems, and both accept the same QUBO, so the formulation can be written once.

What should a logistics company do about quantum computing now?

Write one decision problem as an optimisation model, solve it with a classical solver, and try quantum-inspired solvers such as simulated bifurcation on its QUBO form. That gives the baseline any future quantum run must beat and usually improves the current process. Running a small instance on a QPU is worth doing to learn the workflow, not to get routes.

Sources

  1. A. Lucas. Ising formulations of many NP problems. Frontiers in Physics 2, 5, 2014. arXiv:1302.5843.
  2. F. Neukart, G. Compostella, C. Seidel, D. von Dollen, S. Yarkoni, B. Parney. Traffic flow optimization using a quantum annealer. Frontiers in ICT 4, 2017. arXiv:1708.01625.
  3. S. Feld, C. Roch, T. Gabor, C. Seidel, F. Neukart, I. Galter, W. Mauerer, C. Linnhoff-Popien. A hybrid solution method for the capacitated vehicle routing problem using a quantum annealer. Frontiers in ICT 6, 2019. arXiv:1811.07403.
  4. S. Yarkoni, F. Neukart, E. Moreno Gomez Tagle, N. Magiera, B. Mehta, K. Hire, S. Narkhede, M. Hofmann. Quantum shuttle: traffic navigation with quantum computing. arXiv preprint, 2020. arXiv:2006.14162.
  5. U. Azad, B. K. Behera, E. A. Ahmed, P. K. Panigrahi, A. Farouk. Solving vehicle routing problem using quantum approximate optimization algorithm. IEEE Transactions on Intelligent Transportation Systems, 2022. arXiv:2002.01351.
  6. S. Harwood, C. Gambella, D. Trenev, A. Simonetto, D. Bernal Neira, D. Greenberg. Formulating and solving routing problems on quantum computers. IEEE Transactions on Quantum Engineering 2, 1–17, 2021.
  7. S. J. Weinberg, F. Sanches, T. Ide, K. Kamiya, R. Correll. Supply chain logistics with quantum and classical annealing algorithms. arXiv preprint, 2022. arXiv:2205.04435.
  8. C. D. B. Bentley, S. Marsh, A. R. R. Carvalho, P. Kilby, M. J. Biercuk. Quantum computing for transport optimization. arXiv preprint, 2022. arXiv:2206.07313.
  9. F. Phillipson. Quantum computing in logistics and supply chain management: an overview. arXiv preprint, 2024. arXiv:2402.17520.
  10. A. Abbas, A. Ambainis, B. Augustino, A. Bärtschi, H. Buhrman, C. Coffrin, G. Cortiana, V. Dunjko et al. Challenges and opportunities in quantum optimization. Nature Reviews Physics, 2024. arXiv:2312.02279.
  11. Y. R. Sanders, D. W. Berry, P. C. S. Costa, L. W. Tessler, N. Wiebe, C. Gidney, H. Neven, R. Babbush. Compilation of fault-tolerant quantum heuristics for combinatorial optimization. PRX Quantum 1, 020312, 2020. arXiv:2007.07391.
  12. D. Stilck França, R. García-Patrón. Limitations of optimization algorithms on noisy quantum devices. Nature Physics 17, 1221–1227, 2021. arXiv:2009.05532.
  13. D. L. Applegate, R. E. Bixby, V. Chvátal, W. Cook, D. G. Espinoza, M. Goycoolea, K. Helsgaun. Certification of an optimal TSP tour through 85,900 cities. Operations Research Letters 37, 11–15, 2009.

Run it yourself with eigenkit

eigenkit is EigenOrbit's open-source Python library: write a circuit once, run it on any simulator or QPU, and test it against a classical baseline on your own data before you invest in it or rule it out.

$ pip install eigenkit