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

Add Comment
3 Answer(s)

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!

Answered on February 2, 2020.
Add Comment

How the hell is a quantum computer supposed to help you more with the semantics (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) any more than a classical computer, the model involved is going to be equally as superfiscial.

Answered on March 1, 2020.
Add Comment

D-Wave is probably the closest fit for what you are searching for. However, many real-world optimization problems will not fit to their hardware. They can only solve very specific  classes of optimization problems. As stated here: https://medium.com/twodigits/3-reasons-quantum-computing-is-overrated-9d87d11aa248 :

“””

Reports from D-Wave [3] focus on practical devices for optimization tasks. It is very misleading when they claim, that they handle so-called NP-Hard problems. What their devices can do is finding approximate solutions to those problems (a much easier task, which can also be done by ordinary computers), but a convincing proof, that they can guarantee to find the global optimum has not yet been delivered, and it seems likely, that they cannot do that [4, 5].

“””

I agree with the point that a large amount of input data is probably an indication that it might not be a good fit for quantum computing any time soon, as stated in rcooper’s answer.

Answered 7 days ago.
Add Comment

Your Answer

By posting your answer, you agree to the Terms & Privacy policy.