Traveling Salesman Problem Solver for KML placemarks
The Traveling Salesman Problem (TSP) is a classic computer science challenge: What path do you choose when visiting a set of destinations so as to minimize the distance traveled? It's a problem for which there aren't any easy shortcuts or a quick formula, and hence it's become something of a cause célèbre among mathematicians and programmers for measuring the efficiency of algorithms and the processing speed of grid computers.
One of the most impressive recent TSP calculations minimized the distance traveled between Swedish towns — all 24,978 of them(!). I was hoping to overlay the map of the shortest route onto Google Earth, but the projection isn't right. The raw data is available, so I might well turn it into a KML file sometime.
In the meantime, though, I wanted to make my own TSP solver for KML files of placemarks.
Instructions: Collect up to nine placemarks in a folder. (Hint, you can also right-click on city icons and save them as placemarks.) Right-click on the folder and Save it locally as a KML file (NOT as a KMZ file). Use the TSP Solver to upload the file and wait around 10 seconds. You'll get a KML file back that contains the shortest route between those placemarks. Guaranteed:-)
Unfortunately, This being a PHP script running on a server, nine placemarks is all that the algorithm can manage in a reasonable time. Ten placemarks would take 10 times longer. The current algorithm isn't very efficient, in any case, and I'll be playing with better solutions in the coming weeks, but I just wanted to get a base system working now. Any speed suggestions are most welcome, or else feel free to roll your own, better TSP solver.
Permalink |
Del.icio.us
|
Connotea
Comments
Excellent.
Posted by: Alan Glennon at 0:57 UTC, August 26, 2006
Heh. I love FME. It took me something like 15 minutes and 8 transformers to figure out how to convert the TSP data into KML:
Jason
Posted by: Jason Birch at 7:54 UTC, August 26, 2006
That's awesome Jason, thanks.
Posted by: Stefan at 21:07 UTC, August 26, 2006
I get the error:
Fatal error: Call to a member function on a non-object in /home/ogle/public_html/tsp/index.php on line 40
kmz file is here:
http://www.cs.drexel.edu/~cera/tmp/TSP.kmz
Any help is appreciated.
Posted by: Chris Cera at 22:02 UTC, August 26, 2006
That's a KMZ file, Chris.
Posted by: Stefan at 22:07 UTC, August 26, 2006
Wow, works great. Thank you Stefan.
Posted by: Chris Cera at 3:52 UTC, August 28, 2006
Curious!
Only a comment: The permutation heuristic, isnt very great idea. You must use another more efficient heuristic or solve by MILP solver.
More info on: http://personales.upv.es/arodrigu/rutas/
Posted by: Alex at 9:27 UTC, September 15, 2006
Thanks. very fast solution. I am assuming that it caluculates "as the crow flies" versus actual surface roads. Is that assumption correct? Even if so, it's still impressive work.
Posted by: ben at 22:14 UTC, June 17, 2007
Post a comment
Blogs linking in
NeoGeo Jobs
Ogle Earth: Recent posts
Ogle Earth's links
Archives
Movable Type 3.2