Monday, June 22, 2015
The Evolution of the Traveling Salesman
There are a few interactive maps that attempt to solve the perennial Traveling Salesman Problem (TSP). This is the challenge to find the shortest route possible given a number of predefined stops. Among the most interesting solutions has been the Forio Route Optimizer, which finds the quickest route (with a number of stops), while also factoring in real-time traffic conditions on the roads.
I also like this new TSP map which iterates through solutions live on a map. Which means you can watch as better and better solutions evolve over time. The Ann Arbor Yum Planner allows you to solve the Traveling Salesman Problem for a number of Ann Arbor businesses. You can select from the city's restaurants, cafes, bars, takeouts, deliveries or bakeries to evolve a quick route which takes in all of the businesses or any combination of the business categories.
The map starts with a route and then mutates the route. From these off-spring routes it selects the four best routes. It then repeats this iteration hundreds of times until settling on an acceptable route.