The Vacationeers

vacationeersIrresistable. View it on YouTube. But watch your back.

The Travelling Salesman Problem

optimap_TSP_solverGeir Kokkvoll Engdahl, a Norwegian guy born in ‘83, posted a Google Maps API  implementation of the classic Traveling Salesman Problem (TSP) called “Optimap” on his blog last July, and has since added the ability to enter multiple destinations with lat/long codes, and also the javascript source code (no longer valid link) so we can examine and play with it.   The application, of course, relies on Google’s routing engine (driving directions) to calculate distances between any two points, and it is not certain that this is always the shortest distance.  There is a bit of discussion about this on the Google Maps API Group (search on “optimal route”).  Engdahl’s program uses brute force up to 10 points, and ant colony heuristics from 11-20 points.  With Google’s restrictions on daily driving-direction requests (10,000) the maximum number of points is limited to 20… so this website won’t soon become the UPS routing-tool-of-choice, but may be useful for you travelling googlemen and women.

Update: Engdahl updated Optimap in 2012. See his blogpost.

Update Google Pricing June 2018: So much has happened to Google Maps for developers, but regarding the 10,000 hits limit, that has all changed to another pricing model.
The very latest is found here: https://cloud.google.com/maps-platform/user-guide/pricing-changes/