My efforts to solve “Travelling salesman problem” through JavaScript

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. 🙂