New, Improved Traveling Presidential Candidate Map
Many years ago, when this website was still young, I created a map of all the ZIP codes in the U.S. in numeric order and then wondered about the shortest path through all of them. I dubbed that The Traveling Presidential Candidate Map. Here is an improved version that's interactive and much more efficient than the old one.
Finding the shortest path through a set of points is called the Traveling Salesman Problem (hence the pun). There are many applications, like finding the fastest way of moving a robot arm between many different positions where it needs to do work, or laying out traces on a printed circuit board.
Despite some major advances in the last 15 or so years, finding the optimal path for a large number of points is still a challenge. And the Traveling Presidential Candidate (TPC) Map, with its 37,284 points, is among them.
In my first attempt, I went with a simple algorithm that I had come up with myself that based the tour on a Hilbert curve. I found a claim that such an attempt would lead to a path that was only about "75% optimal" – presumably meaning it was 25% longer than optimal. That was good enough for my purposes, though it was recently criticized by somebody who seems to know what he's talking about.
So with the help of two very prominent researchers in the field of operations research, I've been able to improve the solution to a point that is way beyond what is reasonable given the triviality of this endeavor. While the old tour was about 18% longer than the theoretical minimum, the new one is now less than 0.006% longer. This is based on an estimate of the minimum length generated by the state-of-the-art Concorde program. Its author, William J. Cook, graciously ran it for me. This lower bound is not exact, so it might be longer.
The actual tour was created by a program named LKH, and again the actual author, Keld Helsgaun, configured and ran it (getting these optimization programs to work as best as possible is far from trivial).
It is possible that running both programs for longer would yield both a larger lower bound and a better tour. Though given that they're only 0.006% apart, it really makes very little difference. In physical distance, the tour is 345,873km or 214,916mi long (that's as-the-campaign-helicopter-flies). The theoretical optimal tour is 19.5km or just over 12mi shorter.
I have added the new TPC map to the interactive ZIPScribble maps page for your enjoyment. On the way, I rewrote that map to be based on a new maps backend and fixed a few issues. I'm still working on updating the individual country pages I made many years ago as well, but more on that later.
The code for the interactive map and the data files for the TPC map are available in a github repository. In particular, this file contains the tour in easily-digested CSV format.
Posted by Robert Kosara on July 4, 2016. Filed under ZIPScribble Maps.