Travelling Salesman Problem explained in 5 minutes

Photo by Alvaro Reyes on Unsplash

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

Update on Open Source Contribution: April 05

Hey there folks!

Last month I worked on an issue in AntennaPod. Check out my previous blog post to know more about it.

Project Link

Issue link

Pull Request link

Finally, after multiple commits my PR has been merged.

This Month

This week I worked on Microsoft Calculator.

If you are a Windows person you might have came across Microsoft Calculator.

This is how it used to look before
Now it’s the most powerful calculator application

The application is written in C++

The issue that I chose to work on:

Issue link

I found there were several controls (AppBar, OperatorTextBox and OperandTextBox) that were no longer used and were laying in the codebase for no reason. So my task was to remove those controls and its instances from the source code.

I have already submitted my PR, waiting for their review.

Pull request link

Although it was a code cleaning task, I was introduced to an ancient C++ code. I have to say its well written and maintained. Even the setting up the project was a piece of cake.

Overall, It was a great opportunity for me to work on a Microsoft project.

In upcoming weeks, I will be working and fixing more issue in Open Source projects and definitely will post a blog update about it.

Stay Tuned!