- Posted by liammclennan on May 26, 2009
Over the last 12 months I have been doing a lot of work with geospatial web applications. That is a fancy way of saying web apps with maps. A recurring question has been, "given a list of places that a person wants to visit can we provide an optimal path for them to take?". The first time someone asked me this I responded like a programmer, "no, it's impossible." After all, the wikipedia article on the travelling salesman problem says that there are 43 589 145 600 possible tours to visit Germany's fifteen largest cities exactly once.
However, as time passed I was asked the same question again and again and I started to wonder if it was impossible, or just hard.
So my new project is to develop a website that will satisfy the following key user story:
as a user
I wish to enter a set of locations and be told the most efficient path to visit all of them
so that I can optimise my travel
The problem appeals to me because I think there is a clear need, which people might pay to have satisfied, and because of the interesting mathematics involved.
Here is a mockup of the first page, where the user enters their set of locations.
Users can plot the points on the map to visualise the problem or they can ask the site to generate the optimal path. Owing to the computational complexity of the problem the path that they get will not actually be the optimal path, but hopefully a decent approximation.
The results page shows the shortest path on the map, as well as narrative directions.
Working with startups as I do I have observed a distinct terror of publishing ideas for fear that they will be stolen. Bizarrely, some companies even try to keep their ideas a secret after their product has been released. So I decided to do the opposite and post my idea before I have even started and see if anyone steals it.