Shortest route with no set destination in Google Maps V3?

Question

So I'm just learning javascript to mess with the Google Maps API. I was wondering if anyone had an elegant solution to this problem I'm running into.

A Google Maps route request must contain three things (origin, destination, and travelMode). My travelMode will always be DRIVING. The origin will always be wherever the user is located.

The destination though, needs to vary. I have several waypoints and the user will visit, and would like to provide the shortest trip possible depending on what waypoints are selected and where the user is, ending the route at one of the waypoints (eg: ABC or ACB, but always Axx...x).

Is there any possible way to do this other than calculating every possible path and seeing which has the shortest distance (or time, or whatever I'm evaluating on)? It seems like that would be prohibitively costly (O(n!)).

edit: With the suggested optimizeWaypoints flag set to true this becomes a O(n) problem instead of O(n!), but now I have issues with issuing too many requests in too short of a time period.

Accountant

Answer 1

There is a setting in google directions to provide optimized route (optimizeWaypoints - http://code.google.com/apis/maps/documentation/javascript/services.html#Directions ) you simply set it to true in your directions object

Roundabout

I've done that, but I'm still forced to set a destination. I can't just set this to true and feed the request all my waypoints. What I'm working on now though is simple create n routes for n waypoints, feeding the request A as origin, b-n as destinations and all the waypoints minus the destination for each route. This gives me a route I can calculate a distance for, going to do some heavy testing now to see if this works for any decent number of waypoints. – Accountant

Ok the solution I ended up using was based off this answer so it is getting the check mark. What I have now are my waypoints as well as some REALLY far away location. I send all my waypoints in my request, let Google find the optimal route for those waypoints from my start position to the far away destination and then take the newly ordered waypoints out. Then I set the final waypoint as the new destination, and fire off another request with the set of waypoints now containing one less waypoint. This gives me the route I'm after. – Accountant

I have the same problem, I need to calculate the best destination together with the other points. I liked your solution. Thanks. – Gord

@Accountant Doesn't the location of the far away destination affect the order the waypoints are returned in the first request? E.g. if the far away destination is to the south, won't the last waypoint tend to be the one that is furthest south? – Isaacson

I just wanted to add my 2 cents to this discussion. I am faced by a similar situation and I am thinking for first using the Distance Matrix API to evaluate the farthest way-point from my origin. I think it can be the best candidate to setup as the destination so all other way-points can fit perfectly into the origin and the farthest way-point. Hope this works for me. – Computation

Answer 2

If you want the shortest route you can call first to Google distanceMatrix API and get the sort list of stops.

Then call to API directions with the sort list.

Kosygin

Answer 3

A simple solution would be to specify Origin and Destination as the same and ask Google Maps to optimize the route based on all other waypoints. It will usually either go to the farthest point first, or last, then come back to the origin. You could then make another request without optimizing, this time specifying the Destination as the last optimized waypoint.

Extradition