Demystifying Supply Chain Optimization

A little over 6 months ago, I had the opportunity to talk about the most famous problem in Computer Science, the travelling salesman problem (TSP), and its real world corollary, the vehicle routing problem (VRP), which remains one of the most studied problems in transportation.

The issue with these problems and others like them is that they are hard – literally.  That is, they belong to a set of problems known as “NP-Hard”, and to date, no one has found a good way of finding the best possible answer to any of them in a reasonable amount of time.  Said differently, for large instances of these problems (like a TSP with thousands of cities to visit), all the computers on earth put together still wouldn’t be sufficient to find the optimal answer in millions of years.  That’s how quickly the number of potential solutions grows and how difficult they are to solve.

So, that’s the end of it, right?  The best we can ever hope to do on problems whose possible solutions grow exponentially is to get pretty good answers?

Not quite.

Let’s start with a different problem from the transportation space.  Suppose that you have 3 loads you need to tender and 3 carriers (A, B, and C) with whom you work.  Each carrier only has 1 truck available and each carrier has a different rate for each load.  Which load should you assign to which carrier?  In this simple example, there are just 6 possibilities (A, B, C / A, C, B / B, A, C …), and it’s easy to calculate the cost of each scenario and simply pick the best one.

What happens when we double the number of loads and the number of carriers to 6 of each?  720 possible scenarios is what happens.  How about increasing the number of loads, the number of carriers, and the carriers’ capacities to what you might actually encounter in the real world?  I think you know where this is headed … We encounter a mind-numbingly large number of potential solutions just like with the travelling salesman problem.  But this time, we’re substantially less screwed.  In fact, we can usually find the best possible answer in a very reasonable amount of time (i.e. typically, just a few seconds).

What gives?

The difference is that the carrier selection problem described above closely resembles what is generally known as a linear programming problem, a mathematical model in which the constraints can be represented as linear relationships.  It’s worth noting that in this context, “programming” actually has nothing to do with computers.  The phrase was coined by George Dantzig during WWII when the solution algorithm he pioneered helped plan expenditures that would reduce costs while increasing enemy losses.

Since then, the solution algorithms have continued to evolve and commercial, software-based mathematical solvers have been created to answer these problems quickly (in terms of time) and efficiently (in terms of computational capacity).

So how do you tell the difference between a crazy hard problem that you can only get good (rather  than perfect) answers to and one in which you can find the truly optimal answer in a matter of seconds?

Unfortunately, there’s no easy way to tell the difference.  Problems like network flow optimization can commonly be formulated as a linear programming problem and solved quickly.  However, that situation can change quickly with the addition of certain side constraints or other requirements.  The same goes for driver and vehicle assignment in fleets, award allocations in procurement events, and even bin and container packing problems.

Again, all is not lost.  Equipped with this information, you can ask informed questions of your supply chain technology providers and perform more rigorous comparisons of competitive offerings.  Something as simple as “Does your solution guarantee optimal answers?” is a great starting point.  If it does, the provider should be able to explain how that’s possible.  If it doesn’t, it creates an opportunity to discuss the heuristics used to find good answers in reasonable amounts of time.  In the end, this knowledge and the discussions it fosters will help you and your technology partners build better supply chains together.

Chris Johnson, VP Research & Development, oversees all software development and supply chain engineering activity at LeanLogistics. After starting at LeanLogistics as a software developer in 2004, Chris held a number of roles of increasing accountability and served as the lead technologist of several initiatives including LeanSource™, LeanDex™ and LeanFleet™, before taking his current position. With a background in computer science, mathematics, and operations research, his unique approach to software development continues to drive LeanLogistics’ technology solutions.  In addition to his role at LeanLogistics, Chris serves as an adjunct associate professor of computer science at a local university.