The views expressed here are solely those of the author and do not necessarily represent the views of FreightWaves or its affiliates.
I first encountered the traveling salesman problem (TSP) during my discrete mathematics course as an undergraduate student at Connecticut College. It has been something I have thought about since, especially since the problem or its variants have applications in how one manages supply chain networks.
On February 10, IEEE Spectrum published Toshiba’s Optimization Algorithm Sets Speed Record for Solving Combinatorial Problems, and that got me thinking about the TSP, and other combinatorial optimization problems again. In this article I try to connect the dots and explain why Toshiba’s announcement is exciting news for software innovation in supply chain.
Defining the problem – the traveling salesman problem
The TSP can be stated this way – assume we have a list of cities. We are given the distance between each pair of cities. What is the shortest possible path that visits each city and returns to the origin city?
If you work in supply chain or operations, there’s no doubt that you have encountered versions of TSP disguised in other clothing. Things get interesting when we think of TSP within a dynamic system that is governed by inherent randomness – in other words, most real world problems.
Defining the problem – the rucksack problem
The rucksack problem is a version of the TSP. It may be stated this way – given a rucksack of limited size, we are given a set of items. Each of the items has a weight and a value. How many items can we combine in the rucksack so that the total weight is less than or equal to a specified limit, while the combined value of the items is maximized?
Again, if you work in supply chain or operations, there’s no doubt that you have encountered versions of the rucksack problem. Here too, things get interesting when we think of the problem in the context of a dynamic system governed by inherent randomness, that is, the weight and value of each item changes randomly over time. Also, what if we relaxed the constraint so that we could increase or decrease the number of rucksacks over time? Another interesting question is – what opportunity costs do we incur by waiting? How does the decision to wait or not wait affect our ability to maximize value?
Defining the problem – the assignment problem
In Commentary: How can machine learning be applied to improve transportation?, which ran on FreightWaves on Tuesday, July 23, 2019, I described the assignment problem: “Numerous resources and numerous demands are distributed over a network such that any of the resources can be assigned to satisfy any of the demands, subject to a budget. Each resource incurs costs in the process of satisfying any given demand. Each resource can generate a profit or incur a loss in the process of satisfying any given demand. There is a resource-specific budget as well as a network-wide budget. Assign all the resources in the network to satisfy demands in a way that maximizes the network’s profit.”
The assignment problem becomes a dynamic assignment problem when we are dealing with real-world problems where uncertainty is inherent to the process.
Defining the problem – combinatorial optimization problems
The TSP, the rucksack problem and the assignment problem belong to a class of problems called combinatorial optimization problems. Combinatorial optimization problems are problems in which we seek optimal outcomes from a finite, but exponentially large set of possible solutions. Generally, this category of problems is solved using mathematical techniques, and the problem is governed by several constraints. Also, the set of possible solutions is too large for an exhaustive examination of each possible solution.
Why Toshiba’s announcement is exciting
More details about the work done by Toshiba is available here – Simulated Bifurcation Machine (SBM) Technologies. This work is exciting because it takes a combinatorial optimization algorithm that the researchers at Toshiba discovered during their work on quantum computing and formulates the algorithm so that it can be implemented on classical computers for the first time.
In computer science, combinatorial optimization problems are among some of the hardest problems to solve.
Without going into the intricate details, this means that combinatorial optimization problems can be solved much faster than in the past. Allowing decisions to be made much more quickly about where relatively limited resources should be deployed in a network that is randomly placing relatively unlimited demands on those resources. According to Toshiba, their results suggest that SBMs can solve such problems as much as 10 times faster than the alternative. Naturally, Toshiba’s competitors beg to differ, and this announcement is likely to initiate an arms race to create machines that solve these problems more quickly and more efficiently than even in the very recent past.
Also, it is not difficult to see how optimization techniques such as those described earlier, applied at scale, can have a big impact in a number of important ways.
I am not suggesting that this particular technology will be available for use in the field tomorrow, or even this year. But I would be surprised if companies have not already started exploring how to use this new discovery in practical ways that go beyond a limited proof of concept. For example, if you are a researcher you can take this new technology for a spin on Amazon Web Services.
If you are a team working on algorithms to solve combinatorial optimization problems in supply chains, we’d love to tell your story in FreightWaves. I am easy to reach on LinkedIn and Twitter. Alternatively, you can reach out to any member of the editorial team at FreightWaves at [email protected].
The reference archive – dig deeper into this topic with FreightWaves
Commentary: How can machine learning be applied to improve transportation?
Commentary: Applying machine learning to improve the supply chain
