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

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