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 14

Hey there folks!

This week I worked on lots of projects and also continued working on Microsoft calculator. Check out my previous blog post to know more about it.

Project link

Issue link

Pull Request link

While testing we encountered internal server problem with the Azure pipelines. It was fixed by one of the code maintainers when he closed and re-opened the PR. And then, suddenly tests started working. I have never seen this kind of fix ever.

I have already finished my tasks. I am just waiting for them to get it merge with the main codebase.

Firefox Fenix


Firefox Fenix is a new browser for Android

Fenix is a Mozilla project. Soon, the default Mozilla Firefox browser will be archived and Fenix will take over it. I think it’s because fenix had lots of cool features. The main one is that Fenix can save state of your browsing. In programming world it’s like saving the state of collection of numerous tabs.

Its written in Kotlin.

Project link

In this project, I worked on two bugs.

Fenix(Issue-1)

The scroll was working fine in portrait mode but broken in landscape mode. To fix the problem I added Scroll view around Linear layout which simply fixed the problem and scroll was working fine in landscape mode.

Issue link

Pull Request link

Fenix(Issue-1)

Again the problem was related to landscape mode of the app. This time the search input text used to lost whenever user tried to switch his device from portrait mode to landscape mode or vice versa. So, to fix it I found a very common and effective solution to this problem. And, it solved the bug but unfortunately code maintainers didn’t liked my fix.

Issue link

Pull request link

Overall, I really liked working with fenix. I am still looking forward to fix more of its issues.

Mifos mobile


Mifos Mobile Banking App for clients

Its an Android Application built on top of the MifosX Self-Service platform for end-user customers to view/transact on the accounts and loans they hold. Data visible to customers will be a sub-set of what staff can see.

This is a native Android Application written in Java with POJO classes in Kotlin.

Project link

In this project, I worked on two bugs.

Mifos(Issue-1)

It was my first time working on this new project so I tried to chose a easy issue to fix and luckily I found a issue related to UI. All I had to do was to align the text(Account Number) in center.

Before

After

Issue link

Pull request link

Mifos(Issue-2)

Now time was to do something that I have never done before. I found a issues in which they needed a confirmation dialog box whenever a user tries to change the password. So I used material dialog class to do it.

New changes

I always wondered how to implement those fancy dialog boxes and today I actually implemented it myself

Issue link

Pull request link

This week I found developers don’t give much importance to the landscape layout of android apps and due to which number of issues are filed related to the app orientation.

Overall, I feel proud to work on so many projects in just two weeks. Most importantly I got a good opportunity to work on Microsoft and Mozilla project.

I will be still looking out for some other exciting Open Source projects to work on so let me know in comments if you have any recommendations.

Stay Tuned!

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!

Open Source Contribution Summary: March Edition

Here there folks!

This month I am working on an issue in AntennaPod. Check out my previous blog post to know more about it.

Project Link

About Issue

Issue link

My task was to add empty view to the Episodes, Download, Playback History and Queue history pages. At first, I had some troubles figuring out how fragments work. Later, I found my way out and added the empty views to the required pages. Throughout the process, the code maintainers of the project helped me and gave me amazing tips in android development.

Result

I have already submitted my pull request and currently maintainers are reviewing my code. Hopefully, my code will get merge by next week.

Pull Request link

I am also looking forward to fix more issues in this project.

Stay Tuned!

Contribution to AntennaPod: March22

A podcast manager for Android

Hey folks,

This week I am working on an issue in AntennaPod. It’s a podcast manager which allows you to subscribe, download top podcasts available in the market.

The project is written in Java and XML.

For the issue, I am adding empty views to various pages. At first I thought the task will be easy but later I found its not that simple. Especially understanding fragments code was a challenge. For almost two days I was lost I had no idea how fragments work. Not only that fragments can be coded in many different ways which makes it more complex to understand as every developer has its own style of writing code. So, I had to do some digging about it.

Issue link

Later I was able to create empty views for some pages. But I wasn’t sure if
my code is according to their project coding standards. So I sent a pull request of my current work for review. Luckily, it passed all the test (hurray!)

Pull request

Then, one of contributor recommended to create only one empty view(xml) instead of recreating empty views for each page. But, he didn’t said anything about my java code (main code) so I believe it’s a good sign.

Now, I am finishing off remaining work and I believe I will submit my final PR to resolve the issue by next week.

Stay Tuned!

Future Open Source Contribution Plan: March Edition

Hey there folks!

This week I will be working on an WordPress android application.

Personally, I have been using wordpress for a quite some time and I love it. It is just so clean and simple to use. Recently, I found that there is an android app for the WordPress which is an Open Source project(repo). These days I have been investing lot of time learning cool things in android development. Soon, I will be uploading my ongoing android projects on Github as Open Source.

For now, I am going to fix some existing bugs or maybe add some cool feature in WordPress app. In process, I will also try to find some undiscovered bugs.

I have already setup my workspace. Throughout the project, I really loved the variable/function naming convention. But, I have to become more familiar with the codebase and get down to work on bugs.

The issues that I am planning to work are as follows:

Issue 1

Issue 2

Issue 3

I will be still looking out for some other exciting Open Source projects to work on so let me know in comments if you have any recommendations.

Stay Tuned!

Open Source Contribution Summary: Feb Edition

As may have seen my older blog posts in which I posted stuff about my participation in Open Source projects whether it is fixing a small bug, improving UI, fixing typos in a document or implementing a cool feature.

If not, check out my previous posts to get more information about my work on Open Source projects in detail.

Blog post 1

Blog post 2

Blog post 3

Pull Requests

Pull Request 1

Pull Request 2

Pull Request 3

Pull Request 4

Pull Request 5

Github Account

Link to my Github

Lessons learned…

  • Earlier when I was finding a good first issue, my main concern was about fixing an issue, but later I got to know setting up the project on a personal desktop is the real pain. So, always check if the project dependencies are compatible with your machine prior to the installation process.
  • You need to know basic Git commands like push, pull.
  • Find issue easily by filtering search results using label. My favourite label ones are good first issue and bug
  • There so many ways to fix a problem and there might be times when code maintainers don’t like your fix so don’t feel bad instead learn from it.
  • Writing comments above your code is a good practice.
  • Don’t look around too much for a solution, its okay to ask for help from your fellow developers or Open Source community.
  • At the end of the day Stack overflow will be your best friend.
  • Don’t rush, take it easy and enjoy the process.

Some cool things…

  • My GitHub contribution activity table has started looking green now.
  • I was invited to join Code For Boston community on slack and worked with awesome developers.
  • I was added on MojiScript contributors list by the owner.

Reflection

  • I am getting very comfortable with React and Android.
  • I learned to implement APIs in a web application and it will be very helpful in future projects.
  • While finding issues, I discovered several projects that uses machine learning and I am looking forward to work on it.

Overall, it was a great experience!

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!