So you are here at FOSDEM in Brussels. Also sightseeing? Geocaching? Tried to optimize your way along the sights or to find many caches without making it a hike? Then you've got the traveling salesman problem! Famous in computer science because finding the optimum is extremely difficult and finding good approximations can be done easily.
Last year we had a talk about 3geonames.org where the Hilbert curve was mentioned to be used in name generation. When researching about this space curve it turned out that such space filling curves give good approximations for the traveling salesman problem. This has already been evaluated scientifically. Route finding using thees curves is extremely simple. Other algorithms need much more computational effort. Using a space filling curve to find a route proposal and improving it with 2-Opt optimization algorithm gives the quality of 2-Opt at high speed. Even so fast that it keeps track with interactive changes of the waypoints on a moving map display.
This mechanism gives short routes for your sightseeing or geocaching planning and can also be used professionally if you have to visit several locations on a single tour as in package delivery, meals on wheels, or elderly care.
Speakers: Thomas Bremer