Around the world in 80k miles

[This article was first published on Revolutions, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

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):

Around the world 2

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)

To leave a comment for the author, please follow the link and comment on their blog: Revolutions.

R-bloggers.com offers daily e-mail updates about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

Never miss an update!
Subscribe to R-bloggers to receive
e-mails with the latest R posts.
(You will not see this message again.)

Click here to close (This popup will not appear again)