8 out of 10 Travelling Salesmen use this map…

.. or should.

I just stumbled* across this rather neat Google Map “Mashup”: Optimap, it attempts to solve the classic ‘Travelling Salesman’ problem, that is find the shortest route to take in an arbitrary list of locations, reordering the locations as appropriate. Doing this manually is tedious at best, but you can miss some useful shortcuts, it’s also no easy task for a computer to solve, but with some clever maths (more on the authors blog!), its possible for a computer to have a good stab at it.

Anyway try it out:Optimap

Only thing missing is import/export functions :) – wonder in fact if the author could push to get this integrated into the real Google Maps engine, that would be so cool!

(* actually I read about it in the Google Maps API group)

4 Responses to “8 out of 10 Travelling Salesmen use this map…”

  1. Geir says:

    Hi, what is it you mean by import / export functions? If it’s really useful, maybe I can implement it :)

    Another thing I’m planning to implement is a way of forcing the relative order of certain destinations. Say you have a list of things to do, and among those, you have to pick up a dvd at location A and bring it to a friend at location B. Obviously, you will want to visit A before B.

  2. Barry says:

    Hi,

    Just thinking a way of loading a list if Waypoints, and then it can run the alogorithm on it. Possibly just a large textbox, paste in a list of locations one per line and it would then geocode and use each one. (If you just leave the API to geocode them could even accept the “My House@56.345,-2.434″ format :)

    The icing on the cake would be to be able to export the sorted list, (or in the case of the import textbox, it just reorders them into the optimim order ;) – or somesort of GeoRSS and/or KML output would be great too. (you could just use Google Maps to do this with a http://maps.google.com/?q=from:{add1}+to:{add2}+to:{add3} url)

  3. Geir says:

    I implemented a very crude import/export feature, which is available at http://gebweb.net/optimap/import.php. It takes a list of latitude, longitude pairs from a textarea and creates markers at these points. The optimal route is then displayed in another textarea, as a re-ordered list of coordinates. The start / end point appears twice in the output list. I might do GeoRSS / KML at some point too :)