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.