6

What is a practical solution to the Travelling Salesman problem, using Google Maps / geolocation / route finding?

I don't need the best solution, within 5% would be fine.

For example, I have 20 locations in the UK to visit, in any order. This may need to scale to hundreds of locations.

What sort of algorithm can I use, given that I can lookup distances (but don't want to lookup hundreds of distances)?

Nicolas Kaiser
  • 1,628
  • 2
  • 14
  • 26
fadedbee
  • 42,671
  • 44
  • 178
  • 308

4 Answers4

7

There is this TSP project implemented in JS http://code.google.com/p/google-maps-tsp-solver/

You can see live demo here http://gebweb.net/optimap/

Kunukn
  • 2,136
  • 16
  • 16
4

Google does have a parameter on their directions API which will optimize the route as a travelling salesman problem:

From the documentation (the key part is &waypoints=optimize:true|...):

The following example calculates a road trip route from Adelaide, South Australia to each of South Australia's main wine regions using route optimization.

http://maps.googleapis.com/maps/api/directions/json?origin=Adelaide,SA
  &destination=Adelaide,SA
  &waypoints=optimize:true|Barossa+Valley,SA|Clare,SA|Connawarra,SA|McLaren+Vale,SA
  &sensor=false

Inspection of the calculated route will indicate that the route is calculated using the following waypoint order:

"waypoint_order": [ 1, 0, 2, 3 ]

For a one-off it's probably easier to use OptiMap as recommended by @Kunukn

rcoup
  • 5,372
  • 2
  • 32
  • 36
2

you can use long lat to estimated roughly how far apart the locations are, then make a few lookups for those that are nearby each other.

a simpler alternative is to separate your map into 3 x 3 sections. Only look up routes for locations in adjacent sections.

these techniques aren't 100% accurate though.

And even if you look up all the paths, you should end up with no more than 190 lookups.

Fun Mun Pieng
  • 6,751
  • 3
  • 28
  • 30
  • I should add that this may need to scale to a few hundred locations, in time. – fadedbee Oct 12 '11 at 07:49
  • 1
    in that case, depending on how accurate you want the results to be, you might be able to divide the map into more sections.. or estimate the distance based on the long lat. – Fun Mun Pieng Oct 12 '11 at 07:50
1

I you are looking for a polynomial approximation for the Euclidean TSP, several algorithms have been suggested. Have a look here.

Lior Kogan
  • 19,919
  • 6
  • 53
  • 85
  • Thanks, this looks useful. Can my problem be considered Euclidean? Four points in a square: the travel-time between opposite corners may be more that the travel-time along two sides. (e.g. there is a motorway along those two edges.) – fadedbee Oct 12 '11 at 08:06
  • 1
    Since you're looking for an approximation anyway, I believe such considerations are generally neglectable. If not - look for the asymmetric TSP. – Lior Kogan Oct 12 '11 at 08:15
  • Thanks, I'm going to go with http://en.wikipedia.org/wiki/Travelling_salesman_problem#Ant_colony_optimization initially, then I look at the more academic (intimidating) approaches if that does not perform well enough. – fadedbee Oct 12 '11 at 08:20