TSP (Traveling Salesman Problem) solver Using GoogleMap

Question

We are developing an application, in which we will show some available houses for sale in google map. User can select any houses from the map and can find the shortest driving route between all the houses he/she selected.

Can any one please tell me how we can find the shortest route and can show that on the map? Is there any PHP based TSP library, that can help us to achieve what we are trying?

Answer 1

A Google search shows many results.

• http://scrivna.com/blog/travelling-salesman-problem/ - Brute force PHP implementation guaranteed to get the optimal answer. Only suitable for a limited number of nodes.

• http://www.renownedmedia.com/blog/genetic-algorithm-traveling-salesperson-php/ - Genetic algorithm PHP implementation which will approximate the answer. Suitable for large numbers of nodes.

You could probably combine the two, choosing which to run based on the size of the graph.

As @Barbar points out in the comments, there is an existing app that does what you're attempting. There is a blog post explaining how it works.

Answer 2

Its old but it may be useful to people: https://developers.google.com/maps/documentation/javascript/v2/services#RoutesAndSteps

just create waypoints for each house and let google do the math for you...

Answer 3

If the problem satisfy the triangle inequality you can try the Christofides algorithm.