A Traveling Salesman tour visits a list of destinations using the shortest path. There’s an obvious way to find the shortest path connecting N points: try all N! paths and see which one is shortest. Unfortunately, that might take a while.
Texas has 254 counties, and so calculating a tour of Texas counties by brute force would examine 254! paths, over 10500 paths. In theory, large Traveling Salesman problems are unsolvable. In practice they can often be solved quickly. As is often the case, the key is to give yourself just a little slack and look for solutions that are close to optimal.
I’ve used the example of a Traveling Salesman tour of Texas before because it makes a nice visual. People asked me for the code that made the image, but I didn’t save the code and didn’t remember offhand how to re-create it. So here’s the code for future reference.
Incidentally, computing the tour itself took only a second or two. Creating the visualization took several seconds.
texas = Entity["AdministrativeDivision", "Texas"]; counties = texas["Subdivisions"]; tour = FindShortestTour[texas["Subdivisions"]]; GeoGraphics[{Thick, Red, GeoPath[counties[[tour[[2]]]]]}]
Here counties
is a list of objects representing Texas counties, sorted by alphabetical order, from Anderson County to Zavala County.
The tour
object is a pair of a distance and a list of integers. The distance, 6780.74 nautical miles, is the length of the tour. The integers are the indexes of the counties in the tour.
{6780.74 nmi, {1, 107, 234, …, 201, 37, 1}}
The tour starts with the first county, Anderson County. It’s got to start somewhere, and I expect it always starts with the first item in the list. Next it goes to the 107th county, Henderson County, and so on. Because FindShortestTour
returns a closed tour, the tour ends where it started, in Anderson County.
Related posts: Traveling Salesman tours of Africa, Americas, Eurasia and Oceania.
For a moment, upon seeing the map with the red line, I thought this was an article about extreme gerrymandering! :-)
Having lived there for my early years, I can say it’s no coincidence that Dallas and Ft. Worth are not sequential. They’re very different places.
Nice post John! It never fails to amaze me that just a few lines of code can achieve so much! This often seems the case with Mathematica.
Now I gotta try some segments of the tour for some mini-vacations!