How to perform route optimization (Travelling Salesman) for Google Maps?

Question

I would greatly appreciate for any clues and/or links to resources and/or solution(s) for the following problem:

I have a delivery people, driving from location to location with various packages. I'd like to provide such person with Android device and utilize Google's maps and traffic information. The solution should find the shortest or fastest path to locations. There will be 40-100 locations the person will travel per day. Mostly those will be in the same city or nearby cities.

Similar solution exists in MapPoint but doesn't utilize traffic information (however inaccurate it is):

http://www.youtube.com/watch?v=XXPxNvuhiPw

Once again - I am grateful for any input to solve such case.

Isn't this pretty much the same as the Travelling salesman problem (http://en.wikipedia.org/wiki/Travelling_salesman_problem)? — Rodrigo Castro, Dec 20 '12 at 01:55
Unless Google Maps has an API to calc the shortest route, you can't, because you don't have the graph. EDIT: Looks like there's an API: http://stackoverflow.com/a/12433303/813951 — Mister Smith, Dec 21 '12 at 09:47
Mister Smith - you gave me a great clue where to look for the solution! Thank You very much! — Roman Kagan, Jan 09 '13 at 18:33

score 0 · Answer 1 · answered Jun 01 '15 at 09:07

You can use set the optimize parameter to true in the Directions API. You are however limited to 8 waypoints per request (23 for Maps API for Work customers). This is unsurprising since the Travelling Salesman problem is computationally expensive to solve for large numbers of locations.

From the documentation.

By default, the Directions service calculates a route through the provided waypoints in their given order. Optionally, you may pass optimize:true as the first argument within the waypoints parameter to allow the Directions service to optimize the provided route by rearranging the waypoints in a more efficient order. (This optimization is an application of the Travelling Salesman Problem.)

How to perform route optimization (Travelling Salesman) for Google Maps?

1 Answers1