Menu
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?
442
Google now supports TSP problem. Free version of google map includes start, end and 8 middle points.
To solve the TSP using the Brute-Force approach, you must calculate the total number of routes and then draw and list all the possible routes. Calculate the distance of each route and then choose the shortest one—this is the optimal solution. This method breaks a problem to be solved into several sub-problems.
New hybrid cultural algorithm with local search (HCALS) is introduced to solve traveling salesman problem (TSP).
TSP considers a single vehicle visiting multiple customer locations before returning to the depot, and we want to minimize the total travel time or vehicle distance. VRP differs from TSP because VRP can generate multiple routes to pass through all customer locations 2 .
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.
149
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...
43
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
