Slashgeo

Where's the Traveling Salesman for Google Maps?

posted by Satri on Thursday January 17, @06:51PM        Permalink  Trackback URI  Slashdotthis  Diggthis  Del.icio.us
from the who's-the-salesman-anyway? dept.

About a week ago Slashdot discussed solving the traveling salesman problem with Google Maps. Their summary: "Has anyone tackled the Traveling Salesman Problem with Google Maps or any other online mapping tool? I've searched, but can't find anything. To me this seems like such an obviously cool function. I'm not up to date on algorithms, so perhaps this isn't really tractable for large values of n. But for small numbers (maybe up to 5), this could at least be brute-forced. I would love to use this when I have errands to run, and I want an overall optimal route. So if this hasn't been done, someone please do it!" A quick search on the geoblogs gave me some blog references to the challenge, but nothing recent; Christian Spanring, Steve's Little World, Mapperz and The Map Room.

Trackbacks:

• NONE
• NONE
• NONE
• NONE
• NONE
• NONE
• NONE
• NONE
• NONE

«  Hitachi New StarBoard Interactive Surface | Free SPOT 4/5 Orthoimagery Over Canada  »

Related Stories

Application Domains: UPS Using Software To Eliminate Left Turns [+]

Slashdot discuss a story named UPS using software to eliminate left turns. Their summary: "The NY Times has a story about UPS using software to dramatically reduce the number of left turns their drivers take. With a fleet of vehicles their size, the time and money saved by pre-planning routes that try to eliminate left turns means big savings."

• TSP

  (Score:3, Informative)

  by mapperz (840) on Friday January 18, @04:26AM (#2153)

  Try http://gebweb.net/optimap/ [gebweb.net] how it is done http://gebweb.net/blogpost/2007/07/05/behind-the-s cenes-of-optimap/ [gebweb.net] "NEW! The solver source code tsp.js is now available under the Common Public License version 1.0." http://gebweb.net/optimap/tsp.js [gebweb.net]

  [ Reply to This ]
• Multimap API has it, Microsoft too

  (Score:3, Informative)

  by mcknut (1461) on Friday January 18, @07:20AM (#2154)

  This is available as a feature in the Multimap API. You can see an example here:
  
  http://www.multimap.com/apidocs/1.2/demos/routing. htm [multimap.com]
  
  Enter four locations and check the box that says "Optimize route" and it should find the optimal path to use for the "via" points. You can obviously use more than four points in your own routes too.
  
  This is also available from the Open API (though it's not mentioned in the documentation).
  
  The recent update to Virtual Earth also includes an improved routing module that offers similar functionality, see here for more details:
  
  http://msdn2.microsoft.com/en-us/library/bb877838. aspx [microsoft.com]
  

  [ Reply to This ]
• Non-web Route Optimization with Streets and Trips

  (Score:3, Informative)

  by Anonymous Voxel on Friday January 18, @12:13PM (#2156)

  I posted my thoughts on web based route optimization along with a look at how to do it with Streets and trips on the Virtual Earth Blog:
  
  http://virtualearth.spaces.live.com/blog/cns!2BBC6 6E99FDCDB98!10973.entry [live.com]
  
  regards,
  Steve lombardi
  virtual earth program manager

  [ Reply to This ]
  • Re:Routing Optimization and fleet management by Anonymous Voxel (Score:1) Monday January 21, @09:35AM