4

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?

Gary Klasen
  • 1,001
  • 1
  • 12
  • 30

1 Answers1

7

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:

... 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:

Community
  • 1
  • 1
Stephen C
  • 698,415
  • 94
  • 811
  • 1,216
  • So it seems to me, concerning local search g-maps it using some algorithms like simulated annealing / tabu search. Thank you Stephen. – Gary Klasen Aug 21 '13 at 14:59