TSP Generator   <-   Research   <-   Sean Forman   <-   You Are Here

On-line TSP Generator by Sean Forman
sforman@sju.edu
http://www.sju.edu/~sforman/

Introduction

Hamiltonian Circuits and the Traveling Salesman Problem (TSP) are often covered as part of Graph Theory sections in many mathematics courses.

TSP is taken from the idea of a salesperson getting up in the morning and then having to visit a large number of clients and then return home at the end of the day. The salesman wishes to find the shortest route to visit all of the clients. Thinking mathematically, this requires the determination of the shortest circuit (a tour that begins and ends in the same city) connecting a given set of cities. Typically, students are introduced to the TSP and shown several common heuristics that can be used to find an approximate (sometimes optimal) solution.

I have designed a web application, TSP Generator, that takes as an input a list of user-provided cities (up to 30), and produces a variety of outputs useful to our instructors and students covering this subject. I use this tool as a teaching aid. It allows me to quickly generate example, real-life problems for the students to solve.

Given a list of cities, TSP Generator produces the

• city-to-city distance matrix,
• approximate solutions using two common heuristics (Repetitive Nearest Neighbor Algorithm and the Cheapest Link Algorithm),
• in some cases, the optimal circuit among all possible circuits (found using a branch and bound algorithm), and
• a map of the inputted cities is displayed.

To try out

1. Go to http://www.sju.edu/~sforman/research/usa_tsp.html
2. Enter a list of cities and states (such as Philadelpha, PA)
3. Submit the list
4. You can choose various map sizes and map areas

Implementation Details

• Written in perl.

• Cities are converted into latitude and longitude via a zip code table.

• Inter-city distances are computed by great circle distance calculation.

  http://www.ncgia.ucsb.edu/education/curricula/giscc/units/u014/tables/table03.html

• Complete solution is found using a branch and bound algorithm.

For Fun: The biggest TSP's ever solved by researchers at Georgia Tech.