Some days back I was searching for NP hard problems and I found out this “Travelling salesman problem”. I read about this on Wiki and I thought of solving it through JavaScript. I knew about google distance matrix api and got an idea of solving this problem by using this api. I read on wikipedia about some mathematical formulation and all the theories related to this.

**Statement:-**

“Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?”.

**Solution:-**

Suppose we have three cities A, B and C. So by distance matrix api we will get distances of A-A, A-B, A-C, B-B, B-A, B-C, C-A, C-B, C-C. I will thank google for this. Now I will create a matrix of the distances, like this:

|[A-A A-B A-C]| |[0 A-B A-C]|

|[B-A B-B B-C]| = |[B-A 0 B-C]|

|[C-A C-B C-C]| |[C-A C-B 0]|

Just check that the distance from A-B and B-A are not equal because it is the distance related to road. It’s not necessary that the path for A-B will be same for B-A that’s why distances are not equal. So going ahead I will calculate the permutations of all the cities and will store it in an array, like this:

I will name city A as 1, B as 2 and C as 3.

then the permutations will be

[1,2,3]

[1,3,2]

[2,1,3]

[2,3,1]

[3,1,2]

[3,2,1]

and I append “1” at the front and at the end of each permutation. So now our new permutation array will become like this:

[1,1,2,3,1] -> So it will be 1 to 1 to 2 to 3 to 1

[1,1,3,2,1]

[1,2,1,3,1]

[1,2,3,1,1]

[1,3,1,2,1]

[1,3,2,1,1]

After this, I will proceed with the mapping of these permutations and the distance matrix which we created above. So by doing this I will calculate all the distances related to every permutation and the permutation with shortest distance will be your shortest route.

I created a npm package which you can check out here and GitHub repo which you can visit here. I uploaded the demo on appfog and you can visit it on this link http://short-route-demo.ap01.aws.af.cm/.

To solve NP hard problems we have to follow some combinatorial optimization and computational complexity theories. Actually I don’t know about these two phrases mentioned above but this is my approach through JavaScript. I didn’t solved this problem fully, need some optimization though in mapping algorithm I wrote because I think it will fail for large no. of cities.

You are fully welcome to state your own views and comments and if this helped you then I will be touched. 🙂