Originally sent to subscribers of the BaseClass newsletter
The Travelling Salesman Problem is a classic computer science problem, known for having no efficient solution.
Why should I care?
There are many real-life problems that are very similar to the Travelling Salesman Problem.
Learning about problems like this will help you to recognize when you're facing something equally difficult to solve.
In 5 minutes or less:
This is the 'Travelling Salesman Problem' (or TSP):
Given a list of cities, what is the shortest route that visits each city once and then returns to the origin city?
It sounds simple, but when we add enough cities it becomes impossible for a computer to solve in a realistic time frame.
Let's see why..
The 'brute force' approach.
There's only one way to find the shortest solution to the Travelling Salesman Problem, we have to try every possible option in turn.
We'll pick a simple example, four cities:
We'll start from A. We can go to either B, C or D next, Let's imagine that we go to B. From there, we have the option to visit either C or D. Once we get to either of those, we then travel to the remaining city before returning back to A.
To recap; from our first city we have 3 choices of where to go next. Once we pick one of those, we have 2 remaining cities to choose from. From there, there’s only 1 city left.
That means that the total number of routes we must try is 3 x 2 x 1 = 6.
Now let's add another city, 'E':
Once we pick a place to start, we now have a choice of 4 others cities to visit. From each of those, we have to pick one of the remaining 3 to visit next. From each of those, there are 2 cities to pick from.. you get the idea.
The number of possible permutations for five cities is 4 x 3 x 2 x 1 = 24. We've added one city, but there are now four times the number of options!
Some of these routes are duplicates (we travel the same route, but in reverse) so they can be discounted. That doesn't really help us though, as the number of possible routes will still grow very quickly.
With only 10 cities, there are 181,440 possible routes. Add one more and there are now over 1.8 million. By the time we get to just 15 cities, there are over 43 Billion possible routes!
With enough cities, the number of routes becomes so large that we just couldn't compute it in a reasonable timescale.
There is a relatively more efficient method to calculate all possible permutations using dynamic programming, but it doesn't matter - it still becomes too slow at scale.
'Solving' the TSP
Since we can't truly solve this problem, the best we can do is look for a good approximation.
One way to do this is using the Nearest Neighbor method:
Starting from a random city, pick the nearest city and go there. Keep picking the nearest city until you've been to all of them once, before returning back to the starting point.
This is the simplest algorithm to find an approximate solution, but there are other algorithms (with varying complexity) that can usually find shorter routes.
Until recently, the best has been an algorithm developed in 1976 by Nicos Christofides.
Christofides' algorithm is capable of finding solutions that are at most 50% longer than the 'perfect' trip.
In 2019, Karlin, Klein and Oveis Gharan proved that an algorithm originally developed in 2010 could actually beat Christofides' algorithm by a tiny fraction of a percent.
This may not sound significant, but it proves that it is possible to improve on that algorithm, and opens the door for more solutions.
The TSP in disguise
It's easy to dismiss the Travelling Salesman Problem as a purely academic problem, not applicable to every day development. It does, however, have real world implications.
'Last Mile Delivery' is the commonly used example. This is the process of delivering something from a transport hub to its final destination. For example, the Amazon truck delivering hundreds of parcels to individual houses.
When you look closer though, other problems start to look sightly like the TSP:
- What is the quickest way to pick items in a warehouse to fulfill an order?
- How can we schedule a bus route to visit all of the stops in the shortest time/distance?
- What is the shortest way to route the wiring in an electrical component?
The Travelling Salesman Problem is in a class of problems called 'NP-hard'. We'll cover 'NP-hard' in another issue, but learning about NP-hard problems like the TSP will help you to recognise when you're facing something similar in your own work.
Need to calculate every possible permutation of things in a collection? That sounds a lot like the Travelling Salesman Problem.
Want to know more?
Check out these links:
- An excellent page demonstrating multiple algorithms for the TSP
- Speeding Up The Traveling Salesman Using Dynamic Programming
- A Wired article about the 2019 improvements, and an explanation of the new algorithm
- Nicos Christofides' paper from 1976, describing his algorithm
- Karlin, Klein and Oveis Gharan's paper from 2019
Top comments (0)