When studying computer science, one will inevitably be introduced to the traveling salesman problem (TSP). Since it was first written about in 1832, it has taken many forms, but the most common is the symmetric TSP, which looks like this:
Given a list of cities and the distances between each pair, what is the shortest possible route that visits each city exactly once and returns to the origin?
It sure sounds simple, and, for small instances, it is. Consider a salesman that has to visit 7 different cities and return to where he started. As animated here, there are 360 different paths that visit those 7 cities. The issue, however, is that the number of possibilities grows exponentially. Add 7 more cities, and there are 3,113,510,400 potential paths. Add just 7 more cities for a total of 21 locations, and you’re up to 1,216,450,000,000,000,000 possibilities (that’s pronounced “1 quintillion, 216 quadrillion, 450 trillion”).
That’s a big number, but computers are fast, right? Well, let’s consider one final instance. Suppose we have to visit 80 locations, which in the world of parcel delivery drivers would actually constitute a slow day. That results in 40 x 10∧80 possibilities. That’s a 4 with 81 zeros after it. To put that in perspective, physicists estimate that there are about 10∧80 atoms in the universe – not on earth, not in our solar system, but literally in the whole universe. Said differently, there are 40 times as many ways to visit just 80 locations as there are atoms in the entire freaking universe!
But wait, it gets worse. In the real world of transportation and logistics, it’s not just about visiting a list of cities. There are pick-ups and deliveries to be performed, there are disparate vehicle types and transportation modes, there are time windows, mixture rules, and other assorted side constraints.
This is where operations research and the use of heuristics come into play. Heuristics are algorithms that trade optimality, completeness, or precision for speed. A colleague of mine once described his job as an operations research scientist as “giving bad answers to questions whose solutions would have otherwise been worse … or even non-existent.” In certain problems, algorithms can provide truly optimal answers. In others, like the TSP noted above, the best we can do is to find a decent answer in a reasonable amount of time. That’s what a heuristic does, and there are a lot of clever heuristics applied to problems like the TSP – large neighborhood search, genetic algorithms, and ant colony optimization to name a few. The common theme about all of them, however, is that they are (1) continually evolving and (2) computationally intensive.
Continued Evolution
Solution approaches to problems like the TSP are consistently being researched. New ideas and approaches are offered on a nearly constant basis, and it is important to work with a supply chain solutions provider that stays current on the state of the art in finding answers to these complex transportation problems. It takes ongoing investment alongside significant expertise and a passion for innovation to continue to offer transportation optimization solutions that deliver the most optimal results.
Computational Intensity
Built to take advantage of multi-processor / multi-core systems, solution approaches almost universally benefit from additional computational capacity; that is, more, bigger, and faster computers. Given the complexity of these problems and the huge impact that solution quality can have on total transportation spend, it makes sense to take advantage of the scalability available in cloud-based solutions. Even basic “compute optimized” servers pack about 8 times the computational capacity of your average desktop or laptop computer. This translates to better solutions in less time, and cloud-based supply chain software solution providers are uniquely positioned to offer access to these high performance and highly scalable systems in a cost-effective manner.
How many atoms was that, again?
Despite Moore’s law and advances in the science of solving hard problems like the TSP (literally, “hard” in the sense that the TSP belongs to a class of problems known as NP-hard … seriously, look it up), it requires continued investment and cutting-edge technology to provide solutions that are increasingly less bad. Keeping in mind that solution quality is just as important as solution speed, make sure you find a supply chain software provider that is well equipped to provide both.
Chris Johnson is VP of Research and Development at LeanLogistics where he oversees all research and development activity at the company and is responsible for the LeanTMS® product roadmap. A LeanLogistics employee since 2004, Chris served as the lead technologist of several initiatives including optimization, LeanFleet®, LeanSource®, and LeanDex® before taking his current role. With a background in computer science and mathematics, his unique approach to software development continues to drive LeanLogistics’ technology solutions.
The Most Famous Problem in Computer Science (and Transportation)
When studying computer science, one will inevitably be introduced to the traveling salesman problem (TSP). Since it was first written about in 1832, it has taken many forms, but the most common is the symmetric TSP, which looks like this:
Given a list of cities and the distances between each pair, what is the shortest possible route that visits each city exactly once and returns to the origin?
It sure sounds simple, and, for small instances, it is. Consider a salesman that has to visit 7 different cities and return to where he started. As animated here, there are 360 different paths that visit those 7 cities. The issue, however, is that the number of possibilities grows exponentially. Add 7 more cities, and there are 3,113,510,400 potential paths. Add just 7 more cities for a total of 21 locations, and you’re up to 1,216,450,000,000,000,000 possibilities (that’s pronounced “1 quintillion, 216 quadrillion, 450 trillion”).
That’s a big number, but computers are fast, right? Well, let’s consider one final instance. Suppose we have to visit 80 locations, which in the world of parcel delivery drivers would actually constitute a slow day. That results in 40 x 10∧80 possibilities. That’s a 4 with 81 zeros after it. To put that in perspective, physicists estimate that there are about 10∧80 atoms in the universe – not on earth, not in our solar system, but literally in the whole universe. Said differently, there are 40 times as many ways to visit just 80 locations as there are atoms in the entire freaking universe!
But wait, it gets worse. In the real world of transportation and logistics, it’s not just about visiting a list of cities. There are pick-ups and deliveries to be performed, there are disparate vehicle types and transportation modes, there are time windows, mixture rules, and other assorted side constraints.
This is where operations research and the use of heuristics come into play. Heuristics are algorithms that trade optimality, completeness, or precision for speed. A colleague of mine once described his job as an operations research scientist as “giving bad answers to questions whose solutions would have otherwise been worse … or even non-existent.” In certain problems, algorithms can provide truly optimal answers. In others, like the TSP noted above, the best we can do is to find a decent answer in a reasonable amount of time. That’s what a heuristic does, and there are a lot of clever heuristics applied to problems like the TSP – large neighborhood search, genetic algorithms, and ant colony optimization to name a few. The common theme about all of them, however, is that they are (1) continually evolving and (2) computationally intensive.
Continued Evolution
Solution approaches to problems like the TSP are consistently being researched. New ideas and approaches are offered on a nearly constant basis, and it is important to work with a supply chain solutions provider that stays current on the state of the art in finding answers to these complex transportation problems. It takes ongoing investment alongside significant expertise and a passion for innovation to continue to offer transportation optimization solutions that deliver the most optimal results.
Computational Intensity
Built to take advantage of multi-processor / multi-core systems, solution approaches almost universally benefit from additional computational capacity; that is, more, bigger, and faster computers. Given the complexity of these problems and the huge impact that solution quality can have on total transportation spend, it makes sense to take advantage of the scalability available in cloud-based solutions. Even basic “compute optimized” servers pack about 8 times the computational capacity of your average desktop or laptop computer. This translates to better solutions in less time, and cloud-based supply chain software solution providers are uniquely positioned to offer access to these high performance and highly scalable systems in a cost-effective manner.
How many atoms was that, again?
Despite Moore’s law and advances in the science of solving hard problems like the TSP (literally, “hard” in the sense that the TSP belongs to a class of problems known as NP-hard … seriously, look it up), it requires continued investment and cutting-edge technology to provide solutions that are increasingly less bad. Keeping in mind that solution quality is just as important as solution speed, make sure you find a supply chain software provider that is well equipped to provide both.
Chris Johnson is VP of Research and Development at LeanLogistics where he oversees all research and development activity at the company and is responsible for the LeanTMS® product roadmap. A LeanLogistics employee since 2004, Chris served as the lead technologist of several initiatives including optimization, LeanFleet®, LeanSource®, and LeanDex® before taking his current role. With a background in computer science and mathematics, his unique approach to software development continues to drive LeanLogistics’ technology solutions.
TAGS
Subscribe to Our YouTube Channel
TOPICS
Categories
Subscribe to Our Podcast
TRENDING POSTS
Sponsors