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.
The post Creating a Traveling Salesman Tour of Texas with Mathematica first appeared on John D. Cook.