TSP Generator   <-   Sean Forman   <-   You Are Here

Explanation of traveling salesman problems and methods of solving them

When given a set of cities from the United States, this script will generate a map and data necessary to construct a Traveling Salesman Problem for the given set of cities. It determines inter-city great circle distances, and generates a matrix of inter-city distances. It will also apply a series of heuristic techniques to find approximate solutions to the given TSP problem (Repetitive Nearest Neighbor and Cheapest Link).

Enter a list of up to 30 cities in the following format:

Philadelphia, PA
Des Moines, IA
Los Angeles, CA

List of Cities (City, ST)
State Abbreviations
AK - Alaska
AL - Alabama
AR - Arkansas
AZ - Arizona
CA - California
CO - Colorado
CT - Connecticut
DC - District of Columbia
DE - Delaware
FL - Florida
GA - Georgia
HI - Hawaii
IA - Iowa
ID - Idaho
IL - Illinois
IN - Indiana
KS - Kansas
KY - Kentucky
LA - Louisiana
MA - Massachusetts
MD - Maryland
ME - Maine
MI - Michigan
MN - Minnesota
MO - Missouri
MS - Mississippi
 
MT - Montana
NC - North Carolina
ND - North Dakota
NE - Nebraska
NH - New Hampshire
NJ - New Jersey
NM - New Mexico
NV - Nevada
NY - New York
OH - Ohio
OK - Oklahoma
OR - Oregon
PA - Pennsylvania
RI - Rhode Island
SC - South Carolina
SD - South Dakota
TN - Tennessee
TX - Texas
UT - Utah
VA - Virginia
VT - Vermont
WA - Washington
WI - Wisconsin
WV - West Virginia
WY - Wyoming

Size of the Map
 Small (600 x 400)
 Medium (720 x 480)
 Large (1024 x 720)

Area Shown by Map
 As big as needed
 Lower 48 United States
 All 50 United States


This page is an editor's pick at Michael Trick's Operations Research Page.

The map technology is from the Census Bureau.