What is a practical solution to the Travelling Salesman prblem, using Google Maps?

Question

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

Answer 1

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/

Answer 2

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