What the heck is TSP?

An algorithmic problem in which a set of nodes are given with their distance from each other, and we must connect all of them without going to the same node twice and connect the last node back to the initial node with the shortest route as possible.

Let’s understand it through a scenario

The most popular scenario of this problem is of a traveling salesperson. Suppose a salesman visit a bunch of houses to sell a product. In order to save his traveling cost, he needs to find the shortest route possible.

For this scenario, let us assume he travels from his office to three houses and then back to the office. And, the traveling cost between the office and houses are given below in the table:

In the table,

• The travel cost from the office to house 1 will be $5
• The travel cost from the office to the house 2 will be $10
• The travel cost from the office to house 3 will be $25
• The travel cost from the house 1 to office will be $10
• The travel cost from the house 1 to the house 2 will be $5
• The travel cost from the house 1 to the house 3 will be $35
• The travel cost from the house 2 to office will be $15
• The travel cost from the house 2 to house 1 will be $20
• The travel cost from the house 2 to the house 3 will be $20
• The travel cost from the house 3 to the office will be $5
• The travel cost from the house 3 to house 2 will be $30
• The travel cost from the house 3 to house 1 will be $10

Now let’s draw it on a tree diagram and solve by calculating total costs of all the individual routes

Cost Analysis are as follows:
➢ Office -> House1 -> House2 -> House3 -> Office – $35
➢ Office -> House1 -> House3 -> House2 -> Office – $65
➢ Office -> House2 -> House1 -> House3 -> Office – $70
➢ Office -> House2 -> House3 -> House1 -> Office – $70
➢ Office -> House3 -> House2 -> House1 -> Office – $65
➢ Office -> House3 -> House1 -> House2 -> Office – $75

So, the salesman should take the first route as it is the cheapest among all the other routes.

This is one way of solving the Traveling Salesman Problem. There are many other ways to solve this problem like the cutting-plane method. The TSP is applied to lots of other real-life situations like transportation and logistics services. Another good TSP example can be a school trip around the world. Overall, TSP is a very famous problem. It is still solved using the newest techniques like the neural network approach.

I hope you learned something!

Sources
http://www.math.uwaterloo.ca/tsp/index.html
https://www.youtube.com/watch?v=BAejnwN4Ccw
https://www.csd.uoc.gr/~hy583/papers/ch11.pdf
https://www.youtube.com/watch?v=XaXsJJh-Q5Y
http://www.iro.umontreal.ca/~dift6751/paper_potvin_nn_tsp.pdf