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

Advertisement

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!

Update on Open Source Contribution: Mar01

Hey there folks!

This week I worked on two projects and learned a bunch of cool stuff.

MojiScript

The first project that I worked on this week is MojiScript.


MojiScript is an Async First, opinionated, and functional language designed to have 100% compatibility with JavaScript engines. This will allow full access to JavaScript modules (NPM) and all tooling already available to JavaScript. This means that MojiScript language features can run in any JavaScript application and vice-versa.

I worked on the issue given below:

The issue I worked on

Setting up the project was easy.

Even the fix was also pretty simple. I just searched for ‘mojiscript/types/is’ text in VS Code search box and found the file (is.mdx) which contain this line of code. And then, I just changed the line from ‘mojiscript/types/is’ to ‘mojiscript/type/is’.

Later, I also change the same code of line in ‘unless.mdx’ and ‘when.mdx’.

My pull request

In the end, I submitted the pull request with my changes and it got merged.

Project Repo Link

Issue Link

Pull Request Link

And then an amazing thing happened

Joelnet (Main code maintainer) added me on MojiScript’s contributor’s list with a link to my personal website.

Readme.md file of MojiScript

Another project that I worked on this week is the Brewery Finder.

Brewery Finder

This is a website built to find any local or nearby brewer. Currently, it only provides breweries information located in the United States.

The website is written in React.

Again, It was a great opportunity for me to work with React.

Also, in one of my school course, I have to work with a project which uses APIs to fetch data. So, my professor recommended me to check some projects on GitHub which utilize APIs to get an idea of implementing APIs in projects. So, Brewery Finder was a good project to work on.

I worked on the issue given below:

The issue I worked on

The fix was not that easy I had to search for hours to find the best solution. Then suddenly JQuery came across my mind and I fixed the issue in minutes.

The owner seems to like my fix.

I submitted the pull request with my changes and it got merged.

Project Repo Link

Issue Link

Pull Request Link

And then suddenly…

The owner reopened the issue and he fixed the issue without Jquery.

Reopened and closed

He fixed it with just one line i.e. given below:

onMouseDown={e => e.preventDefault()}

Ahhh, I didn’t know we can use ‘OnMouseDown’ method. Before fixing it with Jquery I tried the same way but instead, I used the ‘onClick’ method. However, it didn’t work for me.

Well, now I know.

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!

Update on Open Source Contribution: Feb22

Hey there folks!

This week I worked on two projects and got an invitation to join an amazing community on Slack.

Community Connect

The first project that I worked on this week is Community Connect.


“Community Connect” is a health resource web application that aims to consolidate information about businesses and organization available in communities that promote healthy lifestyle choices. A health resource is defined as services or materials that improve the quality of life of others, ranging from affordable child care, substance abuse counseling, domestic violence support, and more. 

The website is written in React.

Again, It was a great opportunity for me to work with React.

I worked on the issue given below:

Setting up the project was easy. I just forked, cloned and did ‘yarn install’.

Even the fix was also pretty simple. I just searched for ‘Category’ text in VS Code search box and found the file (CategoryList.js) which contain this form. And then, I just the text from ‘Category’ to ‘Filter by Category’.

My pull request

In the end, I submitted the pull request with my changes and it got merged.

Project Repo Link

Issue Link

Pull Request Link

This is not the END

Since the issue, I fixed was simple. I asked for permission to work on another issue but the issue was already fixed. Later, I got a reply from the code maintainer to join their Slack channel (Code for Boston).

As soon as I joined the Slack channel. I got a text from Galiat (code maintainer) to assist her on contributing.md.

Slack chat
My suggestion regarding contributing.md doc

So I provided her a suggestion to add project setup steps in contributing.md to save some developer’s time.

It’s the first time I got invited by someone to join a developers community to work together. And, I excited and looking forward to fixing more issues on this project with other fellow developers.

Vegeta-Server

Another project that I worked on this week is Vegeta-Server.

A RESTful API server for Vegeta, a load testing tool written in Go.

Vegeta is a versatile HTTP load testing tool built out of a need to drill HTTP services with a constant request rate. The Vegeta library is written in Go, which makes it ideal to implement the server in Go.

I worked on the issue given below:

Setting up the project was easy.

For this issue, I moved some code examples from one MD file to a newly created MD file.

Since I haven’t changed any document in an Open-Source project before, it was a good issue for me to work on.

My pull request

In the end, I submitted the pull request with my changes and it got merged.

Project Repo Link

Issue Link

Pull Request Link

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!

Update on Open Source Contribution: Feb14

Hey there folks!

This week I worked on The Teacher Fund unreleased website. This website is maintained by Joel Wasserman who also works at Google.


TeacherFund is a charity to support teachers in a way that encourages great teachers to stay, and potentially great teachers to choose to teach as a career path. This includes providing supplemental funds and supplies to school teachers in need.

The website is written in React using Next.js.

So this was a great opportunity for me to work with React and NextJS.

Since I am taking initial steps in contributing to the Open Source projects. I tried finding an issue which is easy to fix. It almost took me four hours to find an issue

Later, I asked for permission to work on the issue and soon, I got assigned to work on it.

The Issue

Setting up the project was easy. I just forked, cloned and did ‘npm install’.

Now the goal is to add a background image to the SignIn/SignUp page.

To add a background image to React, I did some research on google and found an easy way to do it by just adding a style attribute with backgroundImage to the div.

And all I added was just one line to the div element

<div className="main-container" style={{backgroundImage:`url(${"/static/images/abc_blackboard.jpg"})`, backgroundSize:'100% 80%', backgroundRepeat: 'no-repeat'}}>

Voila…

Final Changes
My pull request

In the end, I submitted the pull request with my changes and it got merged.

Project Repo Link

Issue Link

Pull Request Link

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!