Tour of Iowa's 99 Counties
The Problem of the Traveling Politician, New York Times, December 21, 2011.
99 Counties, 1 Week, 1 Iowa Columist, Kyle Munson driving our optimal tour!
If you are serious about winning the Iowa Caucuses, then you are going to want to make a stop in each of the 99 state counties.
Here is the optimal route to hit every county seat, starting and ending in Des Moines.
You cover the entire state in 55.5 hours of driving time and 2,740 miles.
William Cook, Alain Kornhauser, Robert Vanderbei
County-to-County
The first step in constructing an optimal tour is to compute the point-to-point trips, from county seat to county seat.
We need to do this for each pair of counties, so nearly 10,000 individual trips.
For this we used the CoPilot software developed by ALK Technologies, headed by Princeton's Kornhauser.
For each of the 9,702 pairs, the software computed the driving time for the quickest route between the two county seats; we also obtained the shortest mileage for each pair, but saving time on the road seems more natural than shaving off a few miles by traveling on smaller streets.
Computing the Full Tour
We now have to put the trips together into a 99-stop tour.
Not as easy as it might sound.
Leaving Des Moines we have 98 choices for our second stop, then for each of these 97 choices for the third stop, then for each of these 96 choices for the fourth stop, and so on until we hit our last county and drive back to Des Moines.
That is 98 times 97 times 96 times ... times 3 times 2 times 1 possible tours.
This is a big number: it is larger than 9 followed by 153 zeros.
That is way too many tours to check one at a time.
The task of choosing the best of these tours is known as the traveling salesman problem, or TSP.
The general TSP is one of the great unsolved problems in mathematics, but for our particular example we were able to compute the quickest tour through the 99 cities with a technique known as the cutting-plane method.
The computer time took only three seconds!
Purple Iowa
The color scheme used for the Iowa counties is adopted from Vanderbei's Purple America.
Blue is for democrats, red is for republicans, and green is for all other candidates.
Each county's color is a mix of these three color components in proportion to the results for that county in the 2008 Presidential Election.
Sioux County in the west is solidly red and Johnson County in the east is definitely blue, but otherwise the 2012 candidates will be traveling through various shades of purple along their 99-county tour.
Tours by the 2012 Candidates
To keep up on the Iowa trips taken by this year's candidates, check the Des Moines Register candidate tracker.
In particular, Representative Bachmann is in the middle of a trip to cover the 99 counties in 10 days.
Here are some other news stories on political tours of Iowa.
