How does Google OptimizationWaypoints "solve commanders"?

Question

I want to solve a traveling salesman problem like Google Maps in a DirectionsRequest with request.setOptimizeWaypoints(true); . He orders several waypoints on the route so that transportation costs are minimal.

My question is: Does anyone know which algorithm is behind it? Any heuristic? So far, no information has been found on Google.

I informed myself and found many plug-in heuristics, the closest neighbor, etc. Or is this the exact solution procedure?

Answer 1

The Wikipedia page on Problem with the seller indicates a series of decision search algorithms. (But if N is small, avoid "exact" algorithms!)

According to this post from a Google employee, the source code for 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’s not entirely clear whether this is the "production" code for Google Maps.

From the 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 common issue (Google Maps vs TSP) is also discussed in various other SO issues.

Literature:

• Optimal map routing with Google Maps
• Traveler with the Google Maps API or any other
• What is a practical solution for Traveling Salesman advertisers using Google Maps?