There are two kinds of problems in supply chain where quantum computing offers early promise. The first is simulation; the easiest examples are using simulation for network design (e.g., warehouse locations) or simulation for factory design. The second is optimization; how can we best route material, vehicles, people etc., in the most optimal way. This article will focus on the optimization problems.
Further refining our definition of usefulness, supply chain leaders want optimization problems that work in real time. Our optimal solution changes with demand, such as customer orders, and our constraints, for example, the number of trucks, planes or people available right now. We need optimal solutions that run in a few seconds or less, based on the current situation. Practically, this means optimization problems need to run quickly, and they also must be closely tied to primary applications; ERP, WMS, MES, and even robotics data.
Manual solutions to scheduling and routing work fine for small problems. A dispatcher or manufacturing planner presented with a small list of trucks or jobs to schedule will likely find a reasonable solution just using a spreadsheet or a white board. While the manual solution might not be the mathematically optimal solution, the results are good enough and the difference between a manual approach and a computer-generated answer doesn’t justify the setup costs to use a computer solution. However, this is true for only very small problems, approximately 10 trucks or 10 individual deliveries or 10 manufacturing jobs. Interestingly, the academic literature on the exact gains achieved by using a computer over a manual solution is mixed. There are some specific studies that suggest smaller problems, say computer matching 25 picks by a few forklifts in a warehouse results in gains of +10%.
Many current computer programs have simple matching logic; i.e. pairing loads to trucks based on some rules, such as the truck’s proximity to the load, and driver hours available. ERP programs often schedule manufacturing jobs simply by due date. These programs have little mathematical optimization embedded in the software and for many problems. This approach delivers a “good enough” solution, even if it’s not perfectly optimized. Many transportation management systems (TMS) began with these simple matching solutions and are broadly in use throughout the industry. More sophisticated software uses linear algebra equations to find a truly optimal solution. Linear algebra solutions are well established, the computer programs run fast, and produce excellent solutions. Supply chain practioners often find linear optimization software difficult to set up, but once operational, the results bring notable benefits. A third approach is to use machine learning (AI), which offers a good solution based on historical patterns. Arguably, all of these tactics produce good solutions, and some are mathematically ideal solutions. Better still, these methods run fast and are widely available. If that’s true, what do we need quantum computers for?
We need quantum computers when we add more variables, vehicles, or routes than the current programs can handle. Even using high performance super computers, there are real world problems that can’t be solved within years or decades. In the last article, I used an example of a single truck that had 25 deliveries. The number of possible solutions is too large for a classical computer to solve. However, we can solve these problems using classical computers by adding constraints or rules. For example, if some of the 25 stores are only open for to accept deliveries at certain times, then the number of possible solutions drops dramatically. In other words, real world conditions make the problem easier to solve. Technically, these constraints make our number of feasible solutions smaller, or our solution ‘space’ is reduced. Our classical computers can then generate all the feasible solutions, and simply sort for the lowest cost option.
With real world limitations on possible solutions, the line where we need quantum computers is unclear. In other words, it depends on the way we set up the problem. Going back to our 25-store delivery problem, our qualitative problem is “find the route between all the stores that has the lowest cost (time or gas consumption, etc.).” Quantitatively, we would write this as
Minimize ∑ Ci,j xi,j
Subject to
∑ xi,j =1, i from 1..n
∑ xi,j =1, j from 1..n
Where i ≠ j
This simple, unconstrained problem nears the limits of a classical computer when the number of stores (n) is still small, perhaps 15 for a PC, 30 for larger computers and this can vary depending on some approaches in programming and hardware. This problem, known as the Traveling Salesman problem doesn’t have an algorithm to shorten the number of steps to a solution. The only known way to solve this is to calculate all the possible combinations and sort for the smallest. This means hardware limitations prevent us from solving large versions of the problem. However, if we add some simple constraints, say some of the stores are only open for deliveries at certain times, then the problem is manageable for our current computers. This makes sense instinctively. But, if we keep adding constraints, or more variables, for example allowing the program to consider weather, traffic, etc. then, somewhat counter intuitively, the problem becomes intractable and classical computers struggle. Confusing our attempts to define when quantum is appropriate, there are (classical) algorithms that use approximation methods that get close to an optimal solution, even when the problem is very large. Thus, the line where quantum computers can take over is unclear.
Most of our real-world problems are small enough that classical computers are satisfactory. Our 25-delivery example has a limited solution space if each stop on the route requires an extensive unloading effort. The driver simply cant make too many stops, keeping the solution manageable. Parcel delivery drivers might do 200+ single box deliveries in a shift. Parcel routing solutions can be simplified by forcing sequential stops that are close to each other – no one would create a route that doesn’t follow this logic. So again, our need for quantum solutions is further reduced by pragmatic constraints. These practical limitations, due to driver hours or total distances between stops, etc., means many logistics businesses may never need a quantum computer; PCs and even excel are enough.
Future quantum computers may have one advantage that classical computers cant match; speed. As quantum hardware improves, the speed to find a solution will compel many enterprises to shift to quantum, even if the problem is still small enough for classical computers to solve. The operational tempo of a distribution center demands that routing problems are solved in seconds. Solutions that run in minutes or hours are unlikely to be used consistently by operational staff that are doing the actual work; they need answers immediately.
It’s still too early to definitively say when quantum computing is appropriate based on the size of the problem or the speed of the solution. As quantum hardware and software improvements arrive, this line will become clearer.
Finally, we have to ask ourselves if having an absolute optimal solution is worth it. Our current classical optimization may be good enough. This is the topic for the next article. Stay tuned.