• Skip to main content
  • Skip to primary sidebar
  • Skip to footer

eagereyes

Visualization and Visual Communication

  • Explore
    • Starter Pack
    • Blog Calendar
    • Blogroll
    • eagereyesTV YouTube Videos
  • Practical
    • Basics
    • Pie Charts
    • Techniques
    • Book Reviews
    • Journalism
  • Academic
    • Speaking Mistakes
    • Acceptance Rates
    • Papers
    • Conference Reports
    • Lists of Influences
    • Criticism
    • Peer Review
  • Admin
    • About
    • Contact
    • License
New, Improved Traveling Presidential Candidate Map

Robert Kosara / July 4, 2016

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.

Filed Under: Blog 2016 Tagged With: ZIPScribble Maps

Robert Kosara is Data Visualization Developer at Observable. Before that, he was Research Scientist at Tableau Software (2012–2022) and Associate Professor of Computer Science (2005–2012). His research focus is the communication of data using visualization. In addition to blogging, Robert also runs and tweets. Read More…

Reader Interactions

Comments

  1. 3danim8 (aka Ken Black) says

    July 4, 2016 at 10:04 pm

    Hi Robert,

    Very nice work and thanks very much for sharing! You have achieved a very impressive result.

    Are you willing to share the data set that was created by LKH to produce the The Traveling Presidential Candidate Map? I’d be very interested in seeing and working with this file.

    I first encountered the traveling salesman problem in 1984 or so. Ever since then, I have been fascinated by the computational difficulties of approximating the optimal solution.

    Thanks,

    Ken

    Reply
    • Robert Kosara says

      July 4, 2016 at 11:11 pm

      Yes, they’re available! The repository was linked from the interactive map page, but not from here. I’ve added a paragraph at the end above with the links.

      Reply

Leave a Reply Cancel reply

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

Primary Sidebar

More Blog 2016 Articles

  • A Roundup of Year-End News Graphics Roundups
  • The Dumbest User Interface of 2016
  • When Rankings Are Just Data Porn
  • The EagerEyes Holiday Shopping Guide
  • The Problem with Vis Taxonomies

Recently Popular

  • Midjourney is a Trip
  • Data: Continuous vs. Categorical
  • How The Rainbow Color Map Misleads
  • An Illustrated Tour of the Pie Chart Study Results
  • Spreadsheet Thinking vs. Database Thinking
  • The Simple Way to Scrape an HTML Table: Google Docs
  • You Only See Colors You Can Name
  • Facebook
  • GitHub
  • LinkedIn
  • RSS
  • Twitter
  • YouTube

Subscribe via Email

Footer

  • About
  • Contact
  • License

Copyright © 2006–2022 Robert Kosara · All original materials are available under CC-BY-SA