Solving the problem of the traveling politician
Republican presidential hopeful Mitt Romney begins his three-day tour of Iowa today in anticipation of next week’s caucuses. What is the optimal path for him to travel in order to hit all 99 counties?
This is a version of something known as “the traveling salesman problem,” one of the great unsolved problems in mathematics. But three professors specializing in the field of operations research appear to have solved “the traveling politician problem,” at least when it comes to Iowa.
Above is a map developed by William Cook, a professor of industrial and systems engineering at Georgia Tech, and Alain Kornhauser and Robert Vanderbei, professors of operations research and financial engineering at Princeton.
“The white path traces the quickest possible tour through the state, hitting all 99 county seats in 55.5 hours and 2,739 miles,” Cook explained in a recent opinion piece in The New York Times. “The trip is circular, so you can start and stop at any of the 99 and travel the same total distance.”
To construct the optimal tour, the professors had to compute point-to-point trips from county seat to county seat for each pair of counties, adding up to nearly 10,000 individual trips. They did this by using a software called CoPilot developed by Kornhauser.
The colors in the map above are based on Vanderbei’s Purple America map, which shows Democatic counties in blue and Republican counties in red.
Related
About this blog
EQN is a blog from Princeton University’s School of Engineering and Applied Science that highlights faculty, students and alumni who, through innovation and leadership, are changing the world.
Recent Entries
- Starshade deploys for first time
- Hale ’11 and Ohlendorf ’05 shine in the major leagues
- Flood risk study receives $2.3 million Rockefeller Foundation grant
- Ice cream social August 9 to feature vintage technology
- Jennifer Rexford ’91 one of top 10 ‘cloud trailblazers’
- Dan Boneh *96 wins prize for advances in cryptography
- Computer science researchers untangle a hairy problem
- Technology Review: mining cellphone data without violating privacy
- Dean H. Vincent Poor elected fellow of Royal Society of Edinburgh
- Bob Kahn wins Queen Elizabeth Prize for Engineering
Email EQN
Monthly Archives
- September 2013 (3)
- July 2013 (1)
- June 2013 (2)
- May 2013 (2)
- March 2013 (5)
- February 2013 (2)
- January 2013 (5)
- November 2012 (5)
- October 2012 (3)
- September 2012 (4)
- July 2012 (4)
- June 2012 (8)
- May 2012 (1)
- April 2012 (3)
- March 2012 (4)
- February 2012 (3)
- January 2012 (4)
- December 2011 (3)
- November 2011 (2)
- October 2011 (3)
- September 2011 (6)
- August 2011 (6)
- July 2011 (9)
- June 2011 (9)
- May 2011 (4)
- April 2011 (10)
- March 2011 (2)
- February 2011 (2)
- January 2011 (1)
- November 2010 (3)
- October 2010 (5)
- September 2010 (7)
- August 2010 (1)
- June 2010 (3)
- May 2010 (3)
- March 2010 (5)
- February 2010 (3)
- January 2010 (3)
- December 2009 (5)
- November 2009 (8)
- October 2009 (4)
- August 2009 (2)
- July 2009 (3)
- June 2009 (9)
- May 2009 (2)
- April 2009 (4)
- March 2009 (1)
- February 2009 (2)
- January 2009 (1)
- December 2008 (1)
- November 2008 (5)
- August 2008 (1)
- July 2008 (2)
- June 2008 (2)
- May 2008 (5)
- March 2008 (2)
- January 2008 (1)
- December 2007 (2)
- November 2007 (1)
- October 2007 (3)
- September 2007 (2)
- July 2007 (9)
- June 2007 (5)
- May 2007 (8)
- April 2007 (5)
- March 2007 (4)
- February 2007 (11)
- January 2007 (13)
- December 2006 (4)
- July 2006 (2)