Asked on February 2, 2020 in Optimization.
The kind of problems you’re describing are very common for transportation, logistics, and utility industries. Many of these can be formulated as a variant of the Capacitated Vehicle Routing Problem (CVRP), where one must find the most efficient path to each location for a fleet of vehicles, given a series of constraints like the ones you mentioned above.
As combinatorial optimization problems go, CVRP is a particularly tricky NP-hard problem. Increasing the number of locations and constraints exponentially increases the number of possible solutions, making it nearly impossible to calculate the optimal solution using an exhaustive search on conventional computing resources. Some of the more advanced heuristics, such as the ones outlined in “Efficiently solving very large-scale routing problems” (Arnold, et al., 2019) https://doi.org/10.1016/j.cor.2019.03.006, can handle tens of thousands of nodes but tend to be severely limited when exposed to real-world constraints like time windows.
This complexity makes it an attractive application of Quantum devices like D-Wave’s Quantum Annealer. There have been several publications that explore the VRP using annealing such as:
- “A Hybrid Solution Method for the Capacitated Vehicle Routing Problem Using a Quantum Annealer ” (Feld, et al., 2018) arXiv:1811.07403
- “Quantum Annealing of Vehicle Routing Problem with Time, State, and Capacity” (Irie, et al., 2019) arXiv:1903.06322
Unfortunately, these efforts seem to show that the available technology isn’t quite up to the task. For sufficiently large VRP-type problems, no currently available quantum device has the number of qubits required to provide a meaningful improvement over conventional heuristics. In any case, quantum computing is not necessarily best suited for problems with a very large number of inputs, but it is expected to be most effective where there is a very large number of possible answers. They are typically related, but the association ‘large data therefore quantum computing’ can be misleading. This becomes even more important in the short term due to the small number of qubits available.
The technology does seem to be moving in the right direction, though. D-Wave has announced that their fifth generation annealer is expected to pack 5,000 qubits, with a higher level of connectivity than the previous generation.
In the meantime, there are several promising approaches to solve CVRP problems based on this new technology. Hybrid approaches (where quantum computers and classical computers are combined effectively) and Quantum-Inspired formulations are much more promising for industrial size problems in the short term, which is why these approaches tend to be favoured at 1QBit.
Hope this helps!
- 1093 views
- 3 answers
- 0 votes