What is a practical solution to the Travelling Sal

问题:

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)?

回答1:

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

回答2:

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/

回答3:

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

• API Documentation: Using Waypoints in Routes
• Introduction and demo blog post

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

回答4:

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.