Guides

Quantum computing for truck drivers and route planning

Kevin Castro
Postquant Labs
·3 min read

Quantum computing helps truck drivers through route planning, while the hardware itself stays in a data center. In a published fleet study, the routing problems went to simulated annealing and to D-Wave's hybrid solver, which returned proposed routes for the trucks (QC Ware and Aisin, 2022).

Routing as a quantum problem

Researchers treat truck routing as the capacitated vehicle routing problem. In that problem a fleet of trucks with limited capacity has to serve a set of customers at the lowest total cost. A 2024 paper on hybrid quantum annealing strategies tests two algorithms, and both split the work into two phases: clustering the customers, then routing. The authors report promising solution times and costs. Their abstract gives no problem sizes.

A quantum annealer accepts problems written as a list of yes-or-no variables with weights between pairs of them. In 0/1 form this is a QUBO; written with spins of +1 and -1 it is an Ising model. Andrew Lucas published an Ising formulation of the traveling salesman problem. In his version a variable answers the question "is stop v the j-th stop of the route?" Penalty terms force every stop to appear once and every position in the route to hold exactly one stop. A further term adds up the driving distance between consecutive stops. With the depot fixed as the first stop, a route with N stops needs (N-1)² variables.

Problem size by number of stops

The table below uses Lucas's encoding for a single round trip with a complete distance table. Possible routes are counted as (N-1)!/2: the depot comes first, the other stops come in any order, and driving a route backwards counts as the same route. Couplings are the pairs of variables with a weight between them, worked out as M(M-1)(2M-1) with M = N-1. That formula adds two kinds of pairs:

  • pairs inside a single stop or a single position, which come from the one-stop-per-position penalties
  • pairs of different stops in consecutive positions, which come from the distance term
Stops on the route (N) Binary variables Couplings Possible routes
5 16 84 12
10 81 1,224 181,440
15 196 4,914 about 4.4 × 10¹⁰
23 484 19,866 about 5.6 × 10²⁰
30 841 46,284 about 4.4 × 10³⁰

The number of variables grows with the square of the stop count. The number of possible routes grows far faster. At 23 stops, a computer checking a billion routes per second would need about 18,000 years to try them all, so routing software relies on heuristic search, and annealing is a heuristic of that kind.

A fleet study by QC Ware and Aisin

QC Ware and Aisin modeled a supply chain network with 23 nodes and a typical fleet of 50 to 100 trucks. They assigned routes one truck at a time. For each truck they built a new binary optimization problem of about 2,500 variables. They solved these with simulated annealing and with D-Wave's hybrid solver, and they describe both as placeholders until quantum hardware improves. The authors make no claim of a proven advantage over classical algorithms.

Running a routing problem on Quip

Quip Network accepts optimization problems in this format. Its XQuad toolchain compiles QUBO and Ising models, and the docs list the traveling salesman problem among the problems it covers. The submit-a-job guide gives two practical limits for routing:

  • In the default mode the solver places each variable on a node of the network's registered hardware layout. The dense one-stop-per-position groups in a traveling salesman encoding can make that placement fail. The solver raises PlacementError before it submits anything or charges you.
  • In native mode the solver skips placement and accepts any layout up to 5,000 nodes and 50,000 edges. QPU-backed miners cannot solve native jobs. The simulated annealing miners on the test network can.

Against those limits a single round trip of up to 30 stops fits in one native job. At 31 stops the couplings come to 51,330, so a larger fleet problem has to be split per truck or per cluster, the same way the QC Ware and Aisin study and the hybrid annealing paper split theirs. The Ising topologies page explains the hardware layouts behind placement, and the QUBO solver marketplace comparison works a small QUBO example by hand.

Quip's design notes set a usability goal for the network: a trucker should be able to visit an application developer's site and get a useful result. Getting there means a routing app does the encoding and splitting described above, and the driver sees only the route.

Next step

Start with the submit-a-job guide. It walks through sending a QUBO to the network and choosing between placed and native mode.

Share
Filed underGuides
Newsletter

Don't miss an update

Get new posts and project updates delivered to your inbox. No spam, unsubscribe anytime.