What is The Travelling Salesman Problem?
Tags: computerscience, programming, codenewbie
Published: 2021-03-13 08:43:09

> Originally sent to subscribers of the [BaseClass newsletter](https://www.baseclass.io/)

---

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:

![Island with 4 cities](https://www.baseclass.io/travelling-salesman-problem/1.png)

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':

![Island with 5 cities](https://www.baseclass.io/travelling-salesman-problem/2.png)

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](https://medium.com/basecs/speeding-up-the-traveling-salesman-using-dynamic-programming-b76d7552e8dd), 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.

![Nearest Neighbor](https://www.baseclass.io/travelling-salesman-problem/3.png)

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](https://cse442-17f.github.io/Traveling-Salesman-Algorithms/)
- [Speeding Up The Traveling Salesman Using Dynamic Programming](https://medium.com/basecs/speeding-up-the-traveling-salesman-using-dynamic-programming-b76d7552e8dd)
- [A Wired article about the 2019 improvements, and an explanation of the new algorithm](https://www.wired.com/story/computer-scientists-break-the-traveling-salesperson-record/)
- [Nicos Christofides' paper from 1976, describing his algorithm](https://apps.dtic.mil/dtic/tr/fulltext/u2/a025602.pdf)
- [Karlin, Klein and Oveis Gharan's paper from 2019](https://arxiv.org/abs/1908.00227)