Google Maps API v3 Combinatorics: Shortest Route With Many People, Many Locations

Question

Unfortunately, I am missing an idea to solve the following problem:

I have 20 locations, which have to be visited one time, and 4 persons, who manage the routes. Also, I have the same origin and the same destination for each driver.

Now, I want...

• Everyone to drive approximately the same time
• Every location to be visited just one time, it does not matter who it is.
• The amount of time and length for all 4 routes summed up to be minimal, that means, it is not absolutely necessary, that one single route is optimal.

I only know how to shorten one single route (setOptimizeWaypoints:true) and how to work with waypoints... distance matrix... etc. so I have not any clue how to combine more than one route.

I use maps API v3 in GWT 2.5.1., but I am also experienced in pure JavaScript. Any ideas?

Answer 1

That's not a problem you'll be able to solve with the right call to the API. Have a look at http://en.wikipedia.org/wiki/Travelling_salesman_problem