Logistics and Scheduling with Quantum Computers
I work in the trucking industry as a freight planner. Currently in our company we use an optimization program called Next Recommend, which essentially takes a bunch of different factors into consideration and helps us plan the freight efficiently; a classical optimization format.
I did not see anything on this site about that so I wanted to open a discussion and see if anyone had information on how Quantum Computers could be used to do this since it can take in to account an enormous amount of input (driver’s start time, start location, hour left to work, distance from customer, weather, traffic, average performance of the driver as well as historical data) to predict an outcome. The best part is not only the ability to calculate this quickly but Quantum Computers could be used to explore all scenarios simultaneously.
So, I welcome everyone to discuss and share any resources you may have on the topic. It may be best t steer away from complicated algorithms or mathematical calculations. Sharing conceptual ideas or simple formulas would be more appealing to a larger audience.
What I have learned is that D-Wave computers are specifically written to perform optimization tasks so they appeal to Enterprises like the larger Fortune 500 company that I work for.
Here’s a website which seems to be geared towards this specific topic in Quantum Computing: https://www.mjc2.com/quantum-computing-logistics-manufacturing-optimization.htm
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!