1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
|
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<!-- Copyright (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013 The GSL Team.
Permission is granted to copy, distribute and/or modify this document
under the terms of the GNU Free Documentation License, Version 1.3 or
any later version published by the Free Software Foundation; with no
Invariant Sections and no cover texts. A copy of the license is
included in the section entitled "GNU Free Documentation License". -->
<!-- Created by GNU Texinfo 5.1, http://www.gnu.org/software/texinfo/ -->
<head>
<title>GNU Scientific Library – Reference Manual: Traveling Salesman Problem</title>
<meta name="description" content="GNU Scientific Library – Reference Manual: Traveling Salesman Problem">
<meta name="keywords" content="GNU Scientific Library – Reference Manual: Traveling Salesman Problem">
<meta name="resource-type" content="document">
<meta name="distribution" content="global">
<meta name="Generator" content="makeinfo">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<link href="index.html#Top" rel="start" title="Top">
<link href="Function-Index.html#Function-Index" rel="index" title="Function Index">
<link href="Examples-with-Simulated-Annealing.html#Examples-with-Simulated-Annealing" rel="up" title="Examples with Simulated Annealing">
<link href="Simulated-Annealing-References-and-Further-Reading.html#Simulated-Annealing-References-and-Further-Reading" rel="next" title="Simulated Annealing References and Further Reading">
<link href="Trivial-example.html#Trivial-example" rel="previous" title="Trivial example">
<style type="text/css">
<!--
a.summary-letter {text-decoration: none}
blockquote.smallquotation {font-size: smaller}
div.display {margin-left: 3.2em}
div.example {margin-left: 3.2em}
div.indentedblock {margin-left: 3.2em}
div.lisp {margin-left: 3.2em}
div.smalldisplay {margin-left: 3.2em}
div.smallexample {margin-left: 3.2em}
div.smallindentedblock {margin-left: 3.2em; font-size: smaller}
div.smalllisp {margin-left: 3.2em}
kbd {font-style:oblique}
pre.display {font-family: inherit}
pre.format {font-family: inherit}
pre.menu-comment {font-family: serif}
pre.menu-preformatted {font-family: serif}
pre.smalldisplay {font-family: inherit; font-size: smaller}
pre.smallexample {font-size: smaller}
pre.smallformat {font-family: inherit; font-size: smaller}
pre.smalllisp {font-size: smaller}
span.nocodebreak {white-space:nowrap}
span.nolinebreak {white-space:nowrap}
span.roman {font-family:serif; font-weight:normal}
span.sansserif {font-family:sans-serif; font-weight:normal}
ul.no-bullet {list-style: none}
-->
</style>
</head>
<body lang="en" bgcolor="#FFFFFF" text="#000000" link="#0000FF" vlink="#800080" alink="#FF0000">
<a name="Traveling-Salesman-Problem"></a>
<div class="header">
<p>
Previous: <a href="Trivial-example.html#Trivial-example" accesskey="p" rel="previous">Trivial example</a>, Up: <a href="Examples-with-Simulated-Annealing.html#Examples-with-Simulated-Annealing" accesskey="u" rel="up">Examples with Simulated Annealing</a> [<a href="Function-Index.html#Function-Index" title="Index" rel="index">Index</a>]</p>
</div>
<hr>
<a name="Traveling-Salesman-Problem-1"></a>
<h4 class="subsection">25.3.2 Traveling Salesman Problem</h4>
<a name="index-TSP"></a>
<a name="index-traveling-salesman-problem"></a>
<p>The TSP (<em>Traveling Salesman Problem</em>) 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 <em>Flying Salesman Problem</em>,
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.
</p>
<p>The <code>gsl_siman_solve</code> 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.
</p>
<p>The full code can be found in <samp>siman/siman_tsp.c</samp>, but I include
here some plots generated in the following way:
</p>
<div class="smallexample">
<pre class="smallexample">$ ./siman_tsp > tsp.output
$ grep -v "^#" tsp.output
| awk '{print $1, $NF}'
| graph -y 3300 6500 -W0 -X generation -Y distance
-L "TSP - 12 southwest cities"
| plot -Tps > 12-cities.eps
$ grep initial_city_coord tsp.output
| awk '{print $2, $3}'
| graph -X "longitude (- means west)" -Y "latitude"
-L "TSP - initial-order" -f 0.03 -S 1 0.1
| plot -Tps > initial-route.eps
$ grep final_city_coord tsp.output
| awk '{print $2, $3}'
| graph -X "longitude (- means west)" -Y "latitude"
-L "TSP - final-order" -f 0.03 -S 1 0.1
| plot -Tps > final-route.eps
</pre></div>
<p>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.
</p>
<div class="smallexample">
<pre class="smallexample"># 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
</pre></div>
<p>The optimal route turns out to be:
</p>
<div class="smallexample">
<pre class="smallexample"># final coordinates of cities (longitude and latitude)
###final_city_coord: -105.95 35.68 Santa Fe
###final_city_coord: -103.2 34.41 Clovis
###final_city_coord: -96.77 32.79 Dallas
###final_city_coord: -106.76 32.34 Las Cruces
###final_city_coord: -112.07 33.54 Phoenix
###final_city_coord: -108.74 35.52 Gallup
###final_city_coord: -108.58 37.35 Cortez
###final_city_coord: -107.87 37.29 Durango
###final_city_coord: -107.84 35.15 Grants
###final_city_coord: -106.62 35.12 Albuquerque
###final_city_coord: -106.28 35.89 Los Alamos
###final_city_coord: -105.92 35.77 Tesuque
###final_city_coord: -105.95 35.68 Santa Fe
</pre></div>
<p>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:
</p>
<hr>
<div class="header">
<p>
Previous: <a href="Trivial-example.html#Trivial-example" accesskey="p" rel="previous">Trivial example</a>, Up: <a href="Examples-with-Simulated-Annealing.html#Examples-with-Simulated-Annealing" accesskey="u" rel="up">Examples with Simulated Annealing</a> [<a href="Function-Index.html#Function-Index" title="Index" rel="index">Index</a>]</p>
</div>
</body>
</html>
|
