### Traveling Salesman Problem

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 with 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
```

@image{initial-route,3in} @image{final-route,3in}

Initial and final (optimal) route for the 12 southwestern cities Flying Salesman Problem.

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:

@image{12-cities,4.4in}

Example of a simulated annealing run for the 12 southwestern cities Flying Salesman Problem.