distance matrix api

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.


“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?”.


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

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

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