Adventurers whose spirit Muppet is Count von Count can visit all 50 U.S. states or capitals, 413 national parks or 38 cities or towns named Springfield.
But for the ultimate quantifiable trip, consider this challenge created by a math professor in Canada: Checking off nearly 50,000 sites placed on the National Register of Historic Places. William Cook, of the University of Waterloo, and colleagues from Chile and Denmark have calculated the shortest possible route to all of America’s notable attractions. To complete the journey, you’ll need several pairs of walking shoes and 50 years of vacation – an abbreviated length of time thanks to Cook’s research. Here’s an edited interview with the professor about his travel-by-numbers project.
Q: Before this tour, did you map any other routes?
A: We computed a route of all 24,727 pubs in the United Kingdom. We also solved several small examples just for fun, such as the shortest way to tour all 647 campuses on Forbes’s list of America’s top colleges and the best way to play Pokémon Go.
Q: Why did you pick U.S. history sites?
A: Any locations in the country would have been fine from the mathematical research side, so I decided to spend the time gathering the historic site data as a way of connecting people with the work of mathematical optimization (which we all depend on every day, but it is usually quite dry). There is also a direct connection with The Washington Post. On March 10, 2015, Ana Swanson published an article in The Post’s Wonkblog, headlined “A data genius computes the ultimate American road trip.” The tour through 50 U.S. landmarks was a good one. The story went viral, with coverage around the world. This was great for mathematics, but the articles were misleading in suggesting that finding a perfect tour (one that is the shortest possible) through 50 points is out of the question, since there are too many candidates. I’m hoping our 49,603-point tour helps set the record straight.
Q: How did you decide which sites to include?
A: The National Park Service maintains the National Register of Historic Places. It has 90,540 listings; we trimmed this down to our 50,000-point target. In the trimming, we took care to not have our own decisions bias the selection in a manner that might make the math problem easier to solve. So we used a crude approach that could be carried out with simple computer codes. No doubt, a team of humans would have made a nicer selection, favoring a really cool site for a less attractive one. But we were still left with an amazing sample of U.S. history.
Q: Please explain your culling process.
A: First, we excluded Alaska and Hawaii. Both states have great historic sites but their locations would have resulted in a routing problem. We then set up a computer code to gather the remaining locations, county by county, from the Wikipedia listings for the National Register of Historic Places. The information for each entry includes the latitude and longitude as well as an ID that we used to verify the entry with the National Park Service database. From the Wikipedia pages, we collected 73,807 locations. We excluded 244 sites, mostly shipwrecks and lighthouses, that could not be reached with Google’s walking directions. We then removed 23,066 sites with “House” in the title and 500 sites with “District” in the title. Finally, we added the White House, the Capitol and the Supreme Court Building. These last three are not in the register, but I thought they belonged in a U.S. history tour.
Q: Did you hit any bumps in your research?
A: I’d like to say that everything was hunky dory, but well into the solution process, I realized that I had made two nasty mistakes. Mistake No. 1: The great cities of Baltimore and Chicago have data sets stored in individual directories on Wikipedia rather than in the county structure. To make up for this, I computed side trips to Baltimore and Chicago, covering all of their listings from the register. Mistake No. 2: A number of listings have the same latitude and longitude. This mainly comes from two states claiming the same location, such as the Statue of Liberty. This sadly brought us down to 49,603 distinct points.
Q: How did you discover the shortest route?
A: Like Matt Damon in “The Martian,” the only way to find the shortest possible route is to “science the [expletive] out of this!” The work started in 1954 at the Rand Corp., where they found the shortest tour through 49 cities in the United States, one in every state plus Washington. It has involved hundreds of research papers and slow but steady improvements in our understanding of the mathematics of routing and optimization. The U.S. history tour is by far the most difficult problem of this type that has every been solved.
Q: Could a traveler feasibly follow this route and, if so, how long would it take?
A: The route was created with Google walking directions. One caveat is that Google uses ferryboat connections, so it is not always possible to travel by foot. Walking the full route would be quite a feat. The U.S. history tour is roughly 100 times longer than the Appalachian Trail. Hikers generally take around six months to complete the trail. So, better plan on about 50 years if you would like to walk the entire tour. In October, I walked a portion of the tour in D.C. and visited 49 sites in 4 1/2 hours.
Q: Any advice on how one can see some or all of the sites?
A: If you plan to travel long stretches of the route, you will want to drive rather than march along step by step. There are 184 legs where you will travel more than 50 miles between stops. The 53.1-mile leg between Magee Ranger Station (stop No. 20,988 in Idaho) and Bull River Guard Station (stop No. 20,989 in Montana) is no doubt pleasant, but it might be nice to see it from behind the wheel of a car, driving along Clark Fork Road. But in urban areas, you will really want to get around by foot or bicycle. I recommend bringing bicycles in your car, so you can zip around city streets.
Q: What is your next project?
A: We would like to find the shortest tour through a data set of all 1,904,711 cities, towns and villages in the world. The current tour we have takes 4,667,876 miles to reach all of the stops. We know this is close to being the shortest possible, but finding the perfect solution will require major advances in the mathematics of optimization.
(c) 2017, The Washington Post · Andrea Sachs
{matzav.com}
