The TSP (Traveling Salesman Problem) is the classic combinatorial optimization problem. I have provided a very simple version of it, based on the coordinates of twelve cities in the southwestern United States. This should maybe be called the Flying Salesman Problem, since I am using the great-circle distance between cities, rather than the driving distance. Also: I assume the earth is a sphere, so I don't use geoid distances.

The `gsl_siman_solve()`

routine finds a route which is 3490.62
Kilometers long; this is confirmed by an exhaustive search of all
possible routes with the same initial city.

The full code can be found in `siman/siman_tsp.c`

, but I include
here some plots generated in the following way:

$ ./siman_tsp > tsp.output $ grep -v "^#" tsp.output | xyplot -xyil -d "x................y" -lx "generation" -ly "distance" -lt "TSP -- 12 southwest cities" | xyps -d > 12-cities.eps $ grep initial_city_coord tsp.output | awk '{print $2, $3, $4, $5}' | xyplot -xyil -lb0 -cs 0.8 -lx "longitude (- means west)" -ly "latitude" -lt "TSP -- initial-order" | xyps -d > initial-route.eps $ grep final_city_coord tsp.output | awk '{print $2, $3, $4, $5}' | xyplot -xyil -lb0 -cs 0.8 -lx "longitude (- means west)" -ly "latitude" -lt "TSP -- final-order" | xyps -d > final-route.eps

This is the output showing the initial order of the cities; longitude is negative, since it is west and I want the plot to look like a map.

# initial coordinates of cities (longitude and latitude) ###initial_city_coord: -105.95 35.68 Santa Fe ###initial_city_coord: -112.07 33.54 Phoenix ###initial_city_coord: -106.62 35.12 Albuquerque ###initial_city_coord: -103.2 34.41 Clovis ###initial_city_coord: -107.87 37.29 Durango ###initial_city_coord: -96.77 32.79 Dallas ###initial_city_coord: -105.92 35.77 Tesuque ###initial_city_coord: -107.84 35.15 Grants ###initial_city_coord: -106.28 35.89 Los Alamos ###initial_city_coord: -106.76 32.34 Las Cruces ###initial_city_coord: -108.58 37.35 Cortez ###initial_city_coord: -108.74 35.52 Gallup ###initial_city_coord: -105.95 35.68 Santa Fe

The optimal route turns out to be:

# final coordinates of cities (longitude and latitude) ###final_city_coord: -105.95 35.68 Santa Fe ###final_city_coord: -106.28 35.89 Los Alamos ###final_city_coord: -106.62 35.12 Albuquerque ###final_city_coord: -107.84 35.15 Grants ###final_city_coord: -107.87 37.29 Durango ###final_city_coord: -108.58 37.35 Cortez ###final_city_coord: -108.74 35.52 Gallup ###final_city_coord: -112.07 33.54 Phoenix ###final_city_coord: -106.76 32.34 Las Cruces ###final_city_coord: -96.77 32.79 Dallas ###final_city_coord: -103.2 34.41 Clovis ###final_city_coord: -105.92 35.77 Tesuque ###final_city_coord: -105.95 35.68 Santa Fe

Here's a plot of the cost function (energy) versus generation (point in the calculation at which a new temperature is set) for this problem:

Further information is available in the following book,

- Modern Heuristic Techniques for Combinatorial Problems, Colin R. Reeves (ed.), McGraw-Hill, 1995 (ISBN 0-07-709239-2).