Link

Robert Kosara, a research scientist at data visualization software company Tableau, has been solving puzzles using the US’s nearly 4,2000 ZIP codes for years, writes Christopher Ingraham at The Washington Post. Kosara had a question:

What would it look like if you drew a single line through all Zip codes in the lower 48 in numeric order? Kosara wrote some code and let it rip, and what he ended up with was a map that clearly delineated state boundaries and gave a reasonable approximation of population density to boot. Since it looked as though it were created by scribbling in arbitrary regions of a U.S. map, he dubbed it the ZIPScribble map.

Kosara ran some calculations and discovered that if you started at the lowest-numbered Zip code (00544, Holtsville, NY) and walk through every Zip code in the continental U.S. in numeric order all the way up to the highest-numbered Zip code (99403, Clarkston, WA), the path you’d need to take would be roughly 1,155,268 miles long. Which naturally brought up a second question: What would be the shortest route you could take through all 37,000 of those zip codes?

This type of problem actually has a storied history in computer science. It’s known as the Traveling Salesman Problem: Say a salesman has a bunch of cities in his route — what’s the shortest trip he can take through all of them? This type of computation is used as a benchmark in computer science because it has a lot of applications, from route-finding to the creation of circuit boards, and because it gets complicated really, really quickly. For instance, a network of only 20 points contains roughly 1.2 quintillion(1,200,000,000,000,000,000) possible solutions, only one of which can be the shortest. That’s on the order of magnitude of the number of grains of sand on earth.

What, then, of a traveling salesman problem with more than 37,000 points?

Kosara took a crack at it. He called it the Traveling Presidential Candidate Problem, after a hypothetical presidential candidate who wanted to visit all 37,000 contiguous Zip codes to clinch the nomination.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.