Problem Description

The Traveling Salesman Problem (TSP) requires that we find the shortest path visiting each of a given set of cities and returning to the starting point.  Here's a program that lets you match your skill against the computer to define a path connecting a random set of U.S. cities.  

Background & Techniques

 I want to thank fellow seeker Robert Harrold for suggesting this project.   He runs a wide ranging website including  this education page where he was kind enough to place a link to DFF.   He says that a computer display similar to this program existed on the second floor of the  National Aerospace Museum in Washington, DC during the 80's.  It disappeared one day in 1988, and he's been looking for it ever since.   Maybe this will help, Bob.  Thanks for asking.    

TSP belongs to a class of problems  which for some non-obvious reason are called NP complete.  These problems have no known efficient algorithms for solving them.   "Not  efficient" here means that the time to solve the problem increases exponentially with problem size, i.e. time to solve is an expression that contains N as an exponent.    This is a much faster growth rate than any polynomial time problem.  (Compare values of N² and 2^N  for N=2, 10, 20 and 30 to see the effect of exponential growth in the simplest case.) 

There seems to be a lot of ongoing research on efficient techniques for solving TSP  - the first solution of a 15,000 city case was just found in 2001, up dramatically from the landmark 49 city solution found in 1954.   There are other applications of the TSP beyond  salesmen and school busses.  For example: robotic travel problems like soldering or drilling operations on printed circuit boards, sequencing local genome maps to produce a global map, planning the order in which a satellite interferometer studies a sequence of stars, etc.  A Google search will turn up lots more.   Perhaps as important as the direct applications, TSP provides a base for academic research on discrete optimization problems.  It's definitely intriguing that a problem so easy to state can be so difficult to solve.   

 Exhaustive search breaks down at something less than 15 cities (about a trillion, 10¹², paths to check).   When the number of cities exceeds the low teens,   we'll have to rely on heuristic (rule of thumb) techniques which provide "pretty good" or "good enough" solutions.   

This program shows a map the 48 contiguous USA states and lets you generate a set of up to 50 cities and  click them to form a path with your mileage totaled.    There are both exhaustive search and heuristic technique buttons provided for the computer path search.   

Non-programmers are welcome to read on, but  may want to skip to the bottom of the page now to download the executable version of TSP.

Programmers Notes:

For an advanced program, there were surprisingly few hard problems to solve here.  Total development time was about 3 days, helped considerably by the fact that the actual path search code already existed.

Well, as usual, time is short, life is fleeting, and I have miles to go before I sleep. So let's get on with it!

Addendum December 18, 2009:  It has been 7 years since the original posting, time for an update, prompted by a user request for the ability to specify the starting city for open paths (visit all cities, but no need to return to the starting point).  The original version always started at the western-most city displayed.   Version 2 starts  open path searches at the first city specified by the user.  

September 7, 2011:   For the past month or so I have been "working" on converting the TSP program to use latitude/longitude instead of pixel coordinates to locate cities and measure distances.    There are still a number of features I would like to add, but it's time to take a break and publish what works leaving the rest as items for "Future Explorations".  Here's a summary of changes in TSP Version 3.

Mercator Projections: In order to accurately overlay cities  on a flat map based on their lat/long coordinates, we need a map with known scaling.  I chose the most popular, the Mercator projection, which maps the earth onto a cylinder with its vertical axis through the poles and its diameter matching the earth's diameter at the equator.  Points above and below the equator are "stretched" to lie on the cylinder, like a balloon blown inside of a cylinder.  if we then sliced the cylinder vertically along the prime meridian, the 0 degree latitude line, and "unroll" it, we have a flat map representation of the earth.  Places near the poles get "stretched" more than those nearer the equator and, in fact, generally are not considered usable at more than 85 degrees North or South Latitudes.  Countries near the equator object to the fact that the Mercator projection makes them seem smaller than they actually are in relation to countries further north or south, which is true.   But it seems that the advantages and widespread use of Mercator projections have been enough to over come those objections.

I found a Mercator outline map of the US to replace the one used here previously.   The "MakeCityLocations" program posted a few weeks ago, provides us with a file of selected US Cities with lat/long coordinates.  The first two records in the file contain diagonally separated locations  which the user must locate  on the map image with mouse clicks. on a one time basis.    These points are saved in a init file, TSP3.ini, for future executions   The Lat/Long and the pixel coordinates for two cities is enough to let us scale all of the other cities on the map. 

 TSP3.INI file: INI files predate the Windows registry as a place to save information from run to run of a program.  TSP3.INI currently contains the names and pixel coordinates of the two points used to establish conversion factors for converting Lat/Long to pixel coordinates.    This file also contains the last used  names of the map file and the cities list file.

Defining User Itineraries: Users may now click the "Define User Itinerary" radio button and define their own set of cities to be visited.  Cities may be selected by clicking the city as its name is displayed as the mouse hovers over it.  Selected cities are displayed in red.  Clicking on a city already added will remove it from the itinerary.  Right click anywhere to signal the set is complete.  If the "Round trip" checkbox is not checked, the initial city will display as a red dot.  (For round trips, the initial city does not affect the shortest route distance.) 

Defining User Paths: When an itinerary has been defined, either by the user or a random one,  the user can click cities  in succession to trace the route to follow.  Clicking a point already added to the path will remove all tracks back to that point.  (Handy if you find that you missed a city.)  User and program paths can now be saved in a text file for printing or future reference.

 February 25, 2017:  A programmer trying to convert Latitude/Longitude coordinates to points on a Mercator projection recently wrote asking for help.  This program was the logical example for him, but it would not compile with Delphi versions after Delphi 7.   Version 3.1 posted this week uses compiler directives to determine Delphi version and generate code which should compile under old or new Delphi versions.  As usual when a program is revisited, text errors were corrected and forms layout and displays improved over the previous version.         

 Running/Exploring the Program 

Suggestions for Further Explorations