Math Movement

The Traveling Salesman Problem (TSP) is an NP-hard problem in combinatorial optimization. Given a list of cities and the distance between each pair of cities, the TSP requires finding a shortest possible tour that visits each city exactly once and returns to the starting point. The TSP is one of the most intensely studied problems in computational math. For an extensive resource regarding history, applications and research of the TSP, see Traveling Salesman Problem.

The TSP increases in difficulty as the number of cities grows. This is connected to the computational difficulty of the problem. For instance, solving a TSP with 30 cities would be very difficult by hand. For instance, in 1962, Proctor and Gamble ran a contest that required solving a TSP on 33 cities. The poster is seen to the right. More than one person submitted an optimal value and among them was an early TSP researcher, Professor Gerald Thompson of Carnegie Mellon University.

A group in my discrete math modeling class is working on a TSP-like problem for a non-profit organization. They are wanting to recommend carpool groups to families whose children attend a local school. An important part of the problem is acquiring the pairwise costs of traveling between two homes. This could be distance or possibly time, as sometimes distance isn’t an accurate measure of the cost since we often want to minimize driving time.

The group found the Google API and requested help in pulling driving distances from Google for known locations. As I read the documentation, I began fiddling with MATLAB code and in the end had a working program. Thinking this might be helpful to others, I decided to create a function getGoogleMap.m that grabs the driving distance and time from Google between two inputted addresses. Then, I created a driver googleTable.m that creates a city by city table of distances and times between locations. The code creates the tables in text and in HTML.

As I experimented with the code, I used the following locations: the Space Needle, the Empire State Building, Davidson College, the Alamo, and the Hollywood sign, which were numbered 1 to 5, respectively. You can also see the locations and their numbers in the picture above. This code creates the following tables, again produced in HTML by the MATLAB code. I simply pasted the resulting HTML into this blog.

Again, I also inputted times between locations as distance isn’t always the best measure of the length of a trip.

Ironically, I’m discussing the TSP in modeling today. The code was developed for my students but will soon play a role in my teaching.

I’ll leave you with a popular teaser that I use in class. Sometimes, seeing that something can be formulated as a TSP or TSP-like is a key observation in modeling. Consider the following game from http://archive.ite.journal.informs.org/Vol3No1/Chlond/Touching.htm.

In the start position above zero touches 2 squares from other numbers, 1 touches 3 squares from other numbers, 2 touches 4 squares from other numbers, and so on to 9, which touches 4 squares from other numbers. If you multiplied each number by the number of squares it touched, and summed the result, you get

0(2) + 1(3) + 2(4) + 3(6) + 4(7) + 5(8) + 6(5) + 7(6) + 8(9) + 9(4) = 277

Can you find a lower value? What configuration leads to the lowest possible value? Click the link above for an applet that let’s you try. Further, how is this like a TSP? One change to the game will make it a TSP! How? Why? That’s the tease in the teaser!

Beware – the game can be a bit addictive!