Optimal map routing with Google Maps

Question

Is there a way using the Google Maps API to get back an "optimized" route given a set of waypoints (in other words, a "good-enough" solution to the traveling salesman problem), or does it always return the route with the points in the specified order?

Answer 1

It always gives them in order.

So I think you'd have to find the distance (or time) between each pair of points, one at a time, then solve the traveling salesman problem yourself. Maybe you could convince Google Maps to add that feature though. I guess what constitutes a "good enough" solution depends on what you're doing and how fast it needs to be.

Answer 2

In a typical TSP problem, the assumption is one can travel directly between any two points. For surface roads, this is never the case. When Google calculates a route between two points, it does a heuristic spanning tree optimization, and usually comes up with a fairly close to optimal path.

To calculate a TSP route, one would first have to ask Google to calculate the pair-wise distance between every node in the graph. I think this requires n*(n-1) / 2 calcs. One could then take those distances and perform a TSP optimization on them.

OpenStreetMaps.org has a Java WebStart application which may do what you want. Of course the calculations are being run client side. The project is open source, and may be worth a look.

Are you trying to find an optimal straight line path between locations, or the optimal driving route? If you just want to order the points, if you can get the GPS coordinates, it becomes a very easy problem.