3
<title>Traveling Salesman Problem - GNU Scientific Library -- Reference Manual</title>
4
<meta http-equiv="Content-Type" content="text/html">
5
<meta name="description" content="GNU Scientific Library -- Reference Manual">
6
<meta name="generator" content="makeinfo 4.8">
7
<link title="Top" rel="start" href="index.html#Top">
8
<link rel="up" href="Examples-with-Simulated-Annealing.html#Examples-with-Simulated-Annealing" title="Examples with Simulated Annealing">
9
<link rel="prev" href="Trivial-example.html#Trivial-example" title="Trivial example">
10
<link href="http://www.gnu.org/software/texinfo/" rel="generator-home" title="Texinfo Homepage">
12
Copyright (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006 The GSL Team.
14
Permission is granted to copy, distribute and/or modify this document
15
under the terms of the GNU Free Documentation License, Version 1.2 or
16
any later version published by the Free Software Foundation; with the
17
Invariant Sections being ``GNU General Public License'' and ``Free Software
18
Needs Free Documentation'', the Front-Cover text being ``A GNU Manual'',
19
and with the Back-Cover Text being (a) (see below). A copy of the
20
license is included in the section entitled ``GNU Free Documentation
23
(a) The Back-Cover Text is: ``You have freedom to copy and modify this
24
GNU Manual, like GNU software.''-->
25
<meta http-equiv="Content-Style-Type" content="text/css">
26
<style type="text/css"><!--
27
pre.display { font-family:inherit }
28
pre.format { font-family:inherit }
29
pre.smalldisplay { font-family:inherit; font-size:smaller }
30
pre.smallformat { font-family:inherit; font-size:smaller }
31
pre.smallexample { font-size:smaller }
32
pre.smalllisp { font-size:smaller }
33
span.sc { font-variant:small-caps }
34
span.roman { font-family:serif; font-weight:normal; }
35
span.sansserif { font-family:sans-serif; font-weight:normal; }
41
<a name="Traveling-Salesman-Problem"></a>
42
Previous: <a rel="previous" accesskey="p" href="Trivial-example.html#Trivial-example">Trivial example</a>,
43
Up: <a rel="up" accesskey="u" href="Examples-with-Simulated-Annealing.html#Examples-with-Simulated-Annealing">Examples with Simulated Annealing</a>
47
<h4 class="subsection">24.3.2 Traveling Salesman Problem</h4>
49
<p><a name="index-TSP-1918"></a><a name="index-traveling-salesman-problem-1919"></a>
50
The TSP (<dfn>Traveling Salesman Problem</dfn>) is the classic combinatorial
51
optimization problem. I have provided a very simple version of it,
52
based on the coordinates of twelve cities in the southwestern United
53
States. This should maybe be called the <dfn>Flying Salesman Problem</dfn>,
54
since I am using the great-circle distance between cities, rather than
55
the driving distance. Also: I assume the earth is a sphere, so I don't
58
<p>The <code>gsl_siman_solve()</code> routine finds a route which is 3490.62
59
Kilometers long; this is confirmed by an exhaustive search of all
60
possible routes with the same initial city.
62
<p>The full code can be found in <samp><span class="file">siman/siman_tsp.c</span></samp>, but I include
63
here some plots generated in the following way:
65
<pre class="smallexample"> $ ./siman_tsp > tsp.output
66
$ grep -v "^#" tsp.output
67
| xyplot -xyil -d "x................y"
68
-lx "generation" -ly "distance"
69
-lt "TSP -- 12 southwest cities"
70
| xyps -d > 12-cities.eps
71
$ grep initial_city_coord tsp.output
72
| awk '{print $2, $3, $4, $5}'
73
| xyplot -xyil -lb0 -cs 0.8
74
-lx "longitude (- means west)" -ly "latitude"
75
-lt "TSP -- initial-order"
76
| xyps -d > initial-route.eps
77
$ grep final_city_coord tsp.output
78
| awk '{print $2, $3, $4, $5}'
79
| xyplot -xyil -lb0 -cs 0.8
80
-lx "longitude (- means west)" -ly "latitude"
81
-lt "TSP -- final-order"
82
| xyps -d > final-route.eps
84
<p class="noindent">This is the output showing the initial order of the cities; longitude is
85
negative, since it is west and I want the plot to look like a map.
87
<pre class="smallexample"> # initial coordinates of cities (longitude and latitude)
88
###initial_city_coord: -105.95 35.68 Santa Fe
89
###initial_city_coord: -112.07 33.54 Phoenix
90
###initial_city_coord: -106.62 35.12 Albuquerque
91
###initial_city_coord: -103.2 34.41 Clovis
92
###initial_city_coord: -107.87 37.29 Durango
93
###initial_city_coord: -96.77 32.79 Dallas
94
###initial_city_coord: -105.92 35.77 Tesuque
95
###initial_city_coord: -107.84 35.15 Grants
96
###initial_city_coord: -106.28 35.89 Los Alamos
97
###initial_city_coord: -106.76 32.34 Las Cruces
98
###initial_city_coord: -108.58 37.35 Cortez
99
###initial_city_coord: -108.74 35.52 Gallup
100
###initial_city_coord: -105.95 35.68 Santa Fe
102
<p>The optimal route turns out to be:
104
<pre class="smallexample"> # final coordinates of cities (longitude and latitude)
105
###final_city_coord: -105.95 35.68 Santa Fe
106
###final_city_coord: -106.28 35.89 Los Alamos
107
###final_city_coord: -106.62 35.12 Albuquerque
108
###final_city_coord: -107.84 35.15 Grants
109
###final_city_coord: -107.87 37.29 Durango
110
###final_city_coord: -108.58 37.35 Cortez
111
###final_city_coord: -108.74 35.52 Gallup
112
###final_city_coord: -112.07 33.54 Phoenix
113
###final_city_coord: -106.76 32.34 Las Cruces
114
###final_city_coord: -96.77 32.79 Dallas
115
###final_city_coord: -103.2 34.41 Clovis
116
###final_city_coord: -105.92 35.77 Tesuque
117
###final_city_coord: -105.95 35.68 Santa Fe
119
<p class="noindent">Here's a plot of the cost function (energy) versus generation (point in
120
the calculation at which a new temperature is set) for this problem:
added
removed
Traveling-Salesman-Problem.html
