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.

Here it is.

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.