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 157 158 159 160 161 162
|
<!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, 2014, 2015, 2016 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 the
Invariant Sections being "GNU General Public License" and "Free Software
Needs Free Documentation", the Front-Cover text being "A GNU Manual",
and with the Back-Cover Text being (a) (see below). A copy of the
license is included in the section entitled "GNU Free Documentation
License".
(a) The Back-Cover Text is: "You have the freedom to copy and modify this
GNU Manual." -->
<!-- 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">26.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>
|