How does Google Maps´ "optimizeWaypoints" solve Travelling Salesmen?
google-maps, google-maps-api-3, heuristics, java, traveling-salesman
Solution
The Wikipedia page on the Travelling Salesman Problem references a number of algorithms for finding solutions. (But unless `N` is small, avoid the "exact" algorithms!)
According to this post from a Google employee, the source code for the Googles route calculation algorithms is available here:
- http://code.google.com/p/or-tools/source/browse/trunk/examples/cpp/tsp.cc
- http://code.google.com/p/or-tools/source/browse/trunk/src/constraint_solver/routing.h
... but it is not entirely clear if this is the "production" code for Google Maps.
From a comment in the source code:
// Solving the vehicle routing problems is mainly done using approximate methods
// (namely local search,
// cf. http://en.wikipedia.org/wiki/Local_search_(optimization)), potentially
// combined with exact techniques based on dynamic programming and exhaustive
// tree search.
This general issue (Google Maps vs TSP) is also discussed in various other SO questions.
References:
- Optimal map routing with Google Maps
- Travelling Salesman with Google Maps API or any other
- What is a practical solution to the Travelling Salesman prblem, using Google Maps?
Problem
I want to solve a Travelling Salesman Problem like Google Maps does in its `DirectionsRequest` with `request.setOptimizeWaypoints(true);`. It orders some Waypoints in a route so that the travelling-costs are minimal. My question: Does anybody know which algorithm stands behind it? Any heuristic? Could not find any information by google, so far. I informed myself and found a lot of insertion-heuristics, nearest neighbour, and so on... Or is it an exact solution procedure?