Thursday, September 18, 2014

Solving the Traveling Salesman Problem with R

Given a list of places you want to go, what is the shortest possible route that visits each place and returns to the place where you first started? This is the basic idea behind the Travelling Salesman Problem (TSP).

Most of us have faced this problem before, either when planning a trip with many cities/tourist attractions, or maybe when dealing with more complex stuff like optimizing public transport systems, air line operations, shipping routes etc. Computationally speaking, this used to be a difficult problem, but things are changing and the number of programs to solve the TSP is increasing.

Todd W. Schneider has created a brilliant code to build interactive solutions to the Traveling Salesman Problem using R and Shiny . In this post here, you may read in detail how the simulation process works and you may also play trying to find the shortest route through some world cities or through all of the US State capitals. (ht Tariq Khokhar).

The full code is available here.

[image credit: Todd W. Schneider]

No comments: