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

There is an option in Google Maps API DirectionsRequest called optimizeWaypoints, which should do what you want. This can only handle up to 8 waypoints, though.

Alternatively, there is an open source (MIT license) library that you can use with the Google Maps API to get an optimal (up to 15 locations) or pretty close to optimal (up to 100 locations) route.

See http://code.google.com/p/google-maps-tsp-solver/

You can see the library in action at www.optimap.net

Answer 2

Google has a ready solution for Travel Salesman Problem. It is OR-Tools (Google's Operations Research tools) that you can find here: https://developers.google.com/optimization/routing/tsp

What you need to do basically is 2 things:

• Get the distances between each two points using Google Maps API: https://developers.google.com/maps/documentation/distance-matrix/start

• Then you will feed the distances in an array to the OR-Tools and it will find a very-good solution for you (For certain instances with millions of nodes, solutions have been found guaranteed to be within 1% of an optimal tour).

You can also note that:

In addition to finding solutions to the classical Traveling Salesman Problem, OR-Tools also provides methods for more general types of TSPs, including the following:

• Asymmetric cost problems — The traditional TSP is symmetric: the distance from point A to point B equals the distance from point B to point A. However, the cost of shipping items from point A to point B might not equal the cost of shipping them from point B to point A. OR-Tools can also handle problems that have asymmetric costs.

• Prize-collecting TSPs, where benefits accrue from visiting nodes

• TSP with time windows

Additional links:

• OR-tools at Github: https://github.com/google/or-tools
• Get Started: https://developers.google.com/optimization/introduction/get_started

Answer 3

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 4

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.

Answer 5

Just found http://gebweb.net/optimap/ It looks nice and easy. Online version using google maps.