QC Ware and Aisin Test Hybrid Solvers on Fleet Routing

Calculating efficient routes for truck fleets requires navigating a complex web of possibilities; with just 23 stops, a complete search for the optimal path would take approximately 18,000 years on a computer testing a billion routes per second. Researchers are now exploring quantum computing as a potential solution, with QC Ware and Aisin having modeled a supply chain network with 23 nodes and a fleet of 50 to 100 trucks in a 2022 study. Their work used D-Wave’s hybrid solver to propose routes, a step toward applying quantum annealing to real-world logistics challenges.

Lucas’s Ising Formulation Scales with Route Complexity

With 23 stops, encoding a single round trip route using Andrew Lucas’s Ising model formulation requires 484 binary variables; this surprisingly high number illustrates the computational complexity inherent in even relatively simple routing problems. The formulation directly addresses the question, “is stop v the j-th stop of the route?” by assigning a variable to each potential stop and position in the sequence, demanding significant computational resources as the problem scales.

This approach, detailed by Lucas, necessitates penalty terms to ensure each stop appears exactly once in the route and each position holds only one stop, further increasing the complexity. The number of possible routes explodes factorially with each additional stop; for a single round trip with a fixed depot, there are (N-1)! /2 distinct routes, where N represents the total number of stops.

At 23 stops, this translates to approximately 5.6 x 10²⁰ possible routes, a figure that quickly overwhelms classical computational methods. A computer attempting to check one billion routes per second would require around 18,000 years to exhaust all possibilities, highlighting why heuristic search methods, like quantum annealing, are being explored as viable alternatives.

The team’s work demonstrates that the number of couplings, the pairs of variables with a weight between them, increases with the square of the stop count, reaching 19,866 at 23 stops, QC Ware says. The researchers found that for 30 stops, the number of possible routes climbs to approximately 4.4 x 10³⁰, further emphasizing the need for innovative computational approaches to tackle these complex logistical challenges.

QC Ware and Aisin Test Hybrid Solvers on Fleet Routing

The scale of computational demand in fleet routing increases rapidly with each added stop; a problem with 23 nodes requires 484 binary variables and 19,866 couplings to encode a single potential route. Researchers found that expanding to 30 stops escalates the variable count to 841 and the number of couplings to 46,284, demonstrating the swift growth in complexity as network size increases. Each truck’s route was formulated as a binary optimization problem containing approximately 2,500 variables, then solved using both simulated annealing and D-Wave’s hybrid solver.

The team treated the routing challenge as the capacitated vehicle routing problem, a common framework for minimizing total cost while serving customers with a limited fleet capacity. Both solvers, according to the researchers, currently serve as placeholders awaiting improvements in quantum hardware capabilities.

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.

Stay current

See today’s quantum computing news on Quantum Zeitgeist for the latest breakthroughs in qubits, hardware, algorithms, and industry deals.

Avatar of Ivy Delaney

Ivy Delaney

Ivy Delaney has been working with neural networks and machine learning since the mid-nineties, back when a couple of hidden layers and a long afternoon of training counted as ambitious. She has watched the field go from academic curiosity to the thing quietly running underneath everything, and she brings that long view to quantum computing. For Quantum Zeitgeist she covers the ground where the two fields meet. That means quantum machine learning and the variational algorithms it leans on, and it also means the less glamorous but more interesting story of classical machine learning already doing real work inside quantum machines, decoding error-correcting codes, calibrating noisy hardware and learning the error models that simulators depend on. She writes about the hardware those algorithms have to run on too, and about the post-quantum cryptography scramble that the same hardware has set off. Her stories typically start with the paper, whether that is peer-reviewed work, conference proceedings or an arXiv preprint, with the source linked so you can hold a claim up against the research it came from. She is unimpressed by benchmarks that will not say what they beat, and by demonstrations that only work in the press release.

Latest Posts by Ivy Delaney: