You're probably familiar with the classic Travelling Salesman problem: given (say) 20 cities, what is shortest route you can take that passes through all 20 cities and returns to the starting point? It's a difficult problem to solve, because you need to try all possible routes to find the minimum, and there are a LOT of possibilities. For a 20-city tour there are more than 1 trillion trillion routes to try — and that's a fairly small problem!
You can get a good answer (if not necessarily the perfect answer) using various heuristic techniques. Software developer Todd Schneider used the R language to implement a technique called simulated annealing. It starts with a random route (each city in the route is chosen at random, without regard to its distance) and then tries various similar routes and probably adopts the shortest one and repeats the process. I say "probably" because a random element in the annealing process helps the process avoid getting stuck with sub-optimal solutions.
In the animation below (created by Todd), you can see the process in action, trying to find a Salesman tour through the world's major capitals. The initial tour is more than 600,000 miles, but it soon settles down into a compact 80,666-mile tour (you may need to click the image to see the animation):
Todd's R code for the Travelling Salesman problem can be found at Github, and he's also created a Shiny app that lets you solve the problem for your own selection of cities in the USA or around the world, and see a similar animation of the annealing process at work. You can find the app and lots more detail about the algorithm and implementation at Todd's blog at the link below.
Todd W. Schneider: The Traveling Salesman with Simulated Annealing, R, and Shiny (via Brock Tibert)
Comments
You can follow this conversation by subscribing to the comment feed for this post.