|
| Tour of 3,100 county seats. Click for a larger image. For an interactive version Click here. |
The moto of the Extra Miler Club is Because the shortest distance between two points is no fun!
A grand target of many members is to visit all counties in the USA. To date, forty people have made it to the elite 100% Club of county completers.
I first heard about the club in February 1998, through an article in the Wall Street Journal: "After 538,427 miles at the wheel: So many counties, so little time". I quickly got in touch with Roy Carson, a co-founder of the club, and traded mail about computing a shortest road trip to visit all US county seats. The shortest distance between two points may not be fun, but, for a fan of the traveling salesman problem, finding a shortest route through 3000+ cities sounded like plenty of fun.
Well, some 17 years later, technology for finding point-to-point distances (Google Maps) and improvements in our understanding of the mathematics behind the traveling salesman problem make computing and displaying an optimal US county route possible.
|
|
| Tour of 3,100 county seats. Click for a larger image. For an interactive version Click here. |
The optimal tour of 3,100 county seats weighs in at 150,418,864 meters, or roughly 93,466 miles. That is considerably shorter than the 538,427 miles that were covered in the trips reported in the Wall Street Journal, but the Extra Milers no doubt found nice side trips to make along the way.
The 150,418,864-meter trip is the shortest possible, given the point-to-point travel distances we have from Google Maps. Not just a good tour, it is the optimal tour. Here are the distances I used; you can find a drawing of the point set without the solution here. I again offer a $1,000 prize to the first person who finds a shorter tour with this distance table.
Together with solving the example of the traveling salesman problem, we also needed to get around the fact that asking Google for the 4,803,450 travel distances between pairs of cities (that is, 3100 times 3099 divided by 2) would take over 5 years, given their 2,500-queries-per-day limit. The technique we used to handle the distances is a souped-up version of the method we adopted in the college tour, using geometric shortcuts whenever we can. In this case, we managed to solve the problem after asking only for the travel distance between 48,248 pairs of county seats, and two rounds of the distance-generation method. That is, we solved two 3,100-city TSP examples to arrive at the optimal tour; each of the TSP solves took roughly 3 hours on a fast, single-processor linux server.
When I found the solution, I was excited to contact Roy Carson, for a high-five some 17 years late. Sadly, Roy had passed away later in 1998. But the Extra Miler Club remains in good hands and welcomes new fellow travelers.
Note Added. (October 6, 2022) Cody Esser writes that he has been making use of portions of the tour to put up big county counts in short trips. He has a very nice blog post 61 Counties in 6 States with a great photo collection of courthouses in Minnesota, Iowa, Nebraska, South Dakota, Kansas, and Missouri.
If you Google for Extra Miler Club, you will see happy members displaying signs for covering 3,143 counties. Our tour handles only 3,100 of these. First off, we don't cover the 29 county-equivalents in Alaska and the 5 counties in Hawaii. That brings our total up to 3,134. Secondly, 8 independent cities in Virginia are also county seats, Charlottesville, Emporia, Harrisonburg, Lexington, Manassas, Martinsville, Staunton, and Winchester. Visiting these 8 places each kills two birds, but we count them only once in our tour. We are up to 3,142, so still missing one county. I grabbed the county seats from the state-by-state Wikipedia lists, and I believe the missing county-equivalent is the Virgina city of Bedford, which gave up its independent status in 2013. But you Bedford fans should not worry, the stop is still included in our tour, since it remains the seat of Bedford County.
Alternative drawings of the USA Counties Tour
Credits
