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

First, 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 application 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.

• I found an outline map of the US on the web and used that as the base map as file USA.bmp.   I load it into a a separate bitmap control in the program so that it can be used to refresh the image as required.     I should probably have converted the file to a resource in our TSP.res resource file,  but laziness set in.  
• Cities are defined at the nearest 10 pixel boundary.  This makes it  practical to keep the city information in a TStringlist with a string version of the coordinates (8 characters XXXXYYYY)  as the key.  This make it fast and easy to check if the mouse is on a city as it moves over the   image.   One disadvantage: if the image size were to be changed, city coordinates would have to be reentered, or at least rescaled.   Many more cities could be entered.  There is a Define Cities button which will pop up a dialog to enter  a city name when the mouse is clicked.   A simple object, TCoordObj, is used to hold city name, the coordinates in integer form, and a Visited flag used to avoid revisiting cities already in a path.  A list, including a string version of the TCoordObj object, is saved as a stream file named CityList.str,   used at startup time to initialize the list of available cities.  
• Scaling of distances traveled is accomplished by converting pixel distance to miles with a miles per pixel scaling factor, Scale.    Scale is set  by computing the pixel distance between New York City and Los Angeles and assuming the distance is 3000 miles.  (Accuracy is not a big concern here.)   If either city is not found, Scale is set to 6.7335.  
• User define their path by clicking on cities in order to be visited.  OnMouseUp exit detects that we are drawing a path and, if on an unvisited city,  add the city to a ListToShow stringlist. 
• The "Exhaustive search" code here was lifted from my Fences and Traveling Salesmen program.  It uses the Combo unit to generate permutations of N numbers, each representing a potential route.  
• Pascal code for the heuristic methods was downloaded from a page at  the Stony Brook Algorithm Repository    Heuristics used are called "Furthest insertion", "Two level exchange", "Three level exchange" and are posted from the book Discrete Optimization Algorithms with Pascal Programs by Maciej M. Syslo, Narsingh Deo, and Janusz S. Kowalik.   Unfortunately the book is out of print and the only used copy available at Amazon.com has an asking price of $100!  About the heuristics themselves, I know not much more than their names.   I tried one called  "Branch and Bound" which worked for small cases but causes  range check exceptions for larger ones.  The commented code is still in the program for others to work on.  One more note - the heuristics seem to be tailored for closed paths, i.e. unchecking the "Round trip" checkbox  results in paths that are pretty easy to beat. 

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!

 Running/Exploring the Program 

• Browse source extract
• Download source
• Download  executable

Suggestions for Further Explorations

	Allow user to retract selection while drawing the path.;
	I just occurred to me that when doing exhaustive searches for round trip routes, half of the arrangements are reversed versions that needn't be checked.  For example, if we have checked path [1,2,3,4] we don't need to check  path [4,3,2,1] because the distance will be the same.  Come to think of it, we also wouldn't need to check rotations [2,3,4,1],  [3,4,1,2],   [4,1,2,3], [3,2,1,4], [2,1,4,3],  or [1,4,3,2].  Eliminating 7 or every 8 permutations could speed things up considerably.   Hey! Even better - isn't it the case that after we check the permutations that begin with city # 1, we have checked all of the unique routes and can stop.   If the user unchecks that "Roundtrip" box, it's a different story.  June 20, 2002 Addendum - This change was implemented today.  Exhaustive search time for shortest 13 city closed route was reduced from 3 hrs 26 min to less than 12 minutes - just too good to resist.
	Fix "Branch and Bound" heuristic code.
	More sophisticated heuristics.
	Current sophisticated techniques produce solutions that are said to be known to be optimum.  They obviously don't determine this by checking all possible paths. So, as my brother once asked about thermos bottles that  keep hot things hot and cold things cold,  how do they know?