The Traveling Salesman's U.S. Roadtrip

June 04 2010 Samir Khan 524
Maple 14

6

I spend much of my time traveling for business. These trips often last a week, and we try to visit as many potential customers as possible, and in the most efficient order. This involves matching our hosts' calendars with our own, booking the most cost effective travel options, and coping with last-minute cancellations and changes. It isn’t easy!

This has become so much easier with the advent of shareable calendars and mapping services, like Google Maps.  Unfortunately, no software tools yet predict the human element, so we always have a degree of uncertainty to look forward to.

With complicated multipart trips we often stick pins in a map as waypoints.  Given that I see the world through geek-tinted glasses, I wanted to build a virtual pinboard map of the US using Maple. 

After some targeted googling, I found a text file at http://www.evl.uic.edu/pape/data/WDB that contained discretized US map data (describing national and state boundaries, and rivers, in terms of the longitude and latitude).  This could be easily plotted in Maple (after downsampling the data to reduce its size).

I also needed a method of pinpointing locations on the map – simply eyeballing towns and cities wasn’t practical.  I stumbled upon http://www.populardata.com, which offers a text file that contains US zip codes, and their corresponding longitudes and latitudes (as well as city, county and state names).  After importing this data into a PostgreSQL database, I interrogated it through Maple using its database connectivity tools.

Programmatically build SQL queries and interrogate databases in Maple 

I could now supply Maple with a list of US zip codes, extract their longitudes and latitudes, and plot the locations on a map.  This meant I could bin my barely-legible paper map, and leave at least part of my travel planning to Maple (although some did comment this wasn’t the best idea I’ve ever had…)

The mathematicians reading this may recognize an opportunity to apply concepts from graph theory and explore the classic Traveling Salesman Problem.  Each location represents a node in an undirected graph, and the shortest route that travels through each location and returns to the beginning is the Hamiltonian cycle.

Maple offers features to plot an undirected graph with a user-selected number of nodes, and calculate the optimal route.  The “weight” of the edges is distance between nodes, and with the Haversine formula you can account for the curvature of the earth.

A roadtrip across the US with user-selected zip codes…

…and its representation as an undirected graph with the Hamiltonian cycle

I've attached worksheet I developed to map US locations and explore the Traveling Salesman Problem (you’ll need to install PostgreSQL before you can use the zip code database).

You can also ask the database more complex questions by changing the SQL query in Maple. For example, "SELECT city FROM zip_codes WHERE latitude BETWEEN 39 AND 40 AND state='CO'" will extract cities that overlap latitudes 39 to 40 in Colorado

Download Application: The Traveling Salesman's US Roadtrip

Please Wait...