| 1 |
%\documentclass[10pt,a4paper,fleqn]{article} |
| 2 |
\documentclass[nojss]{jss} |
| 3 |
|
| 4 |
\usepackage[english]{babel} |
| 5 |
|
| 6 |
%% my packages |
| 7 |
%\usepackage{a4wide} |
| 8 |
%\usepackage[round,longnamesfirst]{natbib} |
| 9 |
%\usepackage{hyperref} |
| 10 |
% |
| 11 |
\usepackage{amsmath} |
| 12 |
\usepackage{amsfonts} |
| 13 |
% |
| 14 |
%\newcommand{\strong}[1]{{\normalfont\fontseries{b}\selectfont #1}} |
| 15 |
\newcommand{\class}[1]{\mbox{\textsf{#1}}} |
| 16 |
\newcommand{\func}[1]{\mbox{\texttt{#1()}}} |
| 17 |
%\newcommand{\code}[1]{\mbox{\texttt{#1}}} |
| 18 |
%\newcommand{\pkg}[1]{\strong{#1}} |
| 19 |
\newcommand{\samp}[1]{`\mbox{\texttt{#1}}'} |
| 20 |
%\newcommand{\proglang}[1]{\textsf{#1}} |
| 21 |
\newcommand{\set}[1]{\mathcal{#1}} |
| 22 |
|
| 23 |
%\usepackage{Sweave} |
| 24 |
%% \VignetteIndexEntry{Introduction to TSP} |
| 25 |
|
| 26 |
\author{Michael Hahsler\\Southern Methodist University \And |
| 27 |
Kurt Hornik\\Wirtschaftsuniversit\"at Wien} |
| 28 |
\title{\pkg{TSP} -- Infrastructure for the Traveling |
| 29 |
Salesperson Problem} |
| 30 |
|
| 31 |
%% for pretty printing and a nice hypersummary also set: |
| 32 |
\Plainauthor{Michael Hahsler, Kurt Hornik} %% comma-separated |
| 33 |
\Plaintitle{TSP -- Infrastructure for the Traveling |
| 34 |
Salesperson Problem} %% without formatting |
| 35 |
\Shorttitle{Infrastructure for the TSP} %% a short title (if necessary) |
| 36 |
|
| 37 |
%% an abstract and keywords |
| 38 |
\Abstract{ The traveling salesperson problem (also known as traveling salesman problem or TSP) is a |
| 39 |
well known and important combinatorial optimization problem. The goal |
| 40 |
is to find the shortest tour that visits each city in a given list |
| 41 |
exactly once and then returns to the starting city. Despite this |
| 42 |
simple problem statement, solving the TSP is difficult since it |
| 43 |
belongs to the class of NP-complete problems. The importance of the |
| 44 |
TSP arises besides from its theoretical appeal from the variety of its |
| 45 |
applications. Typical applications in operations research include |
| 46 |
vehicle routing, computer wiring, cutting wallpaper and job |
| 47 |
sequencing. The main application in statistics is combinatorial data |
| 48 |
analysis, e.g., reordering rows and columns of data matrices or |
| 49 |
identifying clusters. In this paper we introduce the |
| 50 |
\proglang{R}~package \pkg{TSP} which provides a basic infrastructure |
| 51 |
for handling and solving the traveling salesperson problem. The |
| 52 |
package features S3 classes for specifying a TSP and its (possibly |
| 53 |
optimal) solution as well as several heuristics to find good |
| 54 |
solutions. In addition, it provides an interface to \emph{Concorde}, |
| 55 |
one of the best exact TSP solvers currently available. } |
| 56 |
\Keywords{combinatorial optimization, traveling salesman problem, \proglang{R}} |
| 57 |
\Plainkeywords{combinatorial optimization, traveling salesman problem, R} %% without formatting |
| 58 |
%% The address of (at least) one author should be given |
| 59 |
%% in the following format: |
| 60 |
\Address{ |
| 61 |
Michael Hahsler\\ |
| 62 |
Engineering Management, Information, and Systems\\ |
| 63 |
Lyle School of Engineering\\ |
| 64 |
Southern Methodist University\\ |
| 65 |
P.O. Box 750123 \\ |
| 66 |
Dallas, TX 75275-0123\\ |
| 67 |
E-mail: \email{[email protected]}\\ |
| 68 |
|
| 69 |
Kurt Hornik\\ |
| 70 |
Department of Finance, Accounting and Statistics\\ |
| 71 |
Wirtschaftsuniversit\"at Wien\\ |
| 72 |
1090 Wien, Austria\\ |
| 73 |
E-mail: \email{[email protected]} |
| 74 |
} |
| 75 |
|
| 76 |
|
| 77 |
|
| 78 |
\begin{document} |
| 79 |
|
| 80 |
<<echo=FALSE>>= |
| 81 |
options(width = 75, useFancyQuotes=FALSE, prompt="R> ") |
| 82 |
### for sampling |
| 83 |
set.seed(1234) |
| 84 |
@ |
| 85 |
|
| 86 |
%\title{Introduction to \pkg{TSP} -- Infrastructure for the Traveling |
| 87 |
% Salesperson Problem} |
| 88 |
%\author{Michael Hahsler and Kurt Hornik} |
| 89 |
\maketitle |
| 90 |
\sloppy |
| 91 |
|
| 92 |
%\abstract{ |
| 93 |
% The traveling salesperson (or, salesman) problem (TSP) is a |
| 94 |
% well known and important combinatorial optimization problem. The goal |
| 95 |
% is to find the shortest tour that visits each city in a given list |
| 96 |
% exactly once and then returns to the starting city. Despite this |
| 97 |
% simple problem statement, solving the TSP is difficult since it |
| 98 |
% belongs to the class of NP-complete problems. The importance of the |
| 99 |
% TSP arises besides from its theoretical appeal from the variety of its |
| 100 |
% applications. Typical applications in operations research include |
| 101 |
% vehicle routing, computer wiring, cutting wallpaper and job |
| 102 |
% sequencing. The main application in statistics is combinatorial data |
| 103 |
% analysis, e.g., reordering rows and columns of data matrices or |
| 104 |
% identifying clusters. In this paper we introduce the |
| 105 |
% \proglang{R}~package \pkg{TSP} which provides a basic infrastructure |
| 106 |
% for handling and solving the traveling salesperson problem. The |
| 107 |
% package features S3 classes for specifying a TSP and its (possibly |
| 108 |
% optimal) solution as well as several heuristics to find good |
| 109 |
% solutions. In addition, it provides an interface to \emph{Concorde}, |
| 110 |
% one of the best exact TSP solvers currently available. } |
| 111 |
|
| 112 |
\section{Introduction} |
| 113 |
|
| 114 |
The traveling salesperson problem~\citep[TSP;][]{Lawler1985, Gutin2002} |
| 115 |
is a well known and important combinatorial optimization problem. The |
| 116 |
goal is to find the shortest tour that visits each city in a given list |
| 117 |
exactly once and then returns to the starting city. Formally, the TSP |
| 118 |
can be stated as follows. The distances between $n$ cities are stored |
| 119 |
in a distance matrix $\mathbf{D}$ with elements $d_{ij}$ where $i,j = |
| 120 |
1\dots n$ and the diagonal elements $d_{ii}$ are zero. A \emph{tour} |
| 121 |
can be represented by a cyclic permutation $\pi$ of $\{1, 2,\dots, n\}$ |
| 122 |
where $\pi(i)$ represents the city that follows city $i$ on the |
| 123 |
tour. The traveling salesperson problem is then the optimization problem |
| 124 |
to find a permutation $\pi$ that minimizes the \emph{length of the tour} |
| 125 |
denoted by |
| 126 |
|
| 127 |
\begin{equation} |
| 128 |
\sum_{i=1}^n d_{i\pi(i)}. |
| 129 |
\end{equation} |
| 130 |
% see Lenstra & Kan 1975: Some simple Applications to the TSP |
| 131 |
|
| 132 |
For this minimization task, the tour length of $(n-1)!$ permutation |
| 133 |
vectors have to be compared. This results in a problem which is very |
| 134 |
hard to solve and in fact known to be NP-complete~\citep{Johnson1985a}. |
| 135 |
However, solving TSPs is an important part of applications in many areas |
| 136 |
including vehicle routing, computer wiring, machine sequencing and |
| 137 |
scheduling, frequency assignment in communication |
| 138 |
networks~\citep{Lenstra1975, Punnen2002}. |
| 139 |
%and structuring of |
| 140 |
%matrices~\citep{Lenstra1975, Punnen2002}. |
| 141 |
Applications in statistical data analysis include ordering and |
| 142 |
clustering objects. For example, data analysis applications in |
| 143 |
psychology ranging from profile smoothing to finding an order in |
| 144 |
developmental data are presented by~\cite{Hubert1978}. Clustering and |
| 145 |
ordering using TSP solvers is currently becoming popular in |
| 146 |
biostatistics. For example, \cite{Ray2007} describe an application for |
| 147 |
ordering genes and \cite{Johnson2006} use a TSP solver for clustering |
| 148 |
proteins. |
| 149 |
|
| 150 |
In this paper we give a very brief overview of the TSP and introduce the |
| 151 |
\proglang{R}~package \pkg{TSP} which provides an infrastructure for |
| 152 |
handling and solving TSPs. The paper is organized as follows. In |
| 153 |
Section~\ref{sec:TSP} we briefly present important aspects of the TSP |
| 154 |
including different problem formulations and approaches to solve TSPs. |
| 155 |
In Section~\ref{sec:infrastructure} we give an overview of the |
| 156 |
infrastructure implemented in \pkg{TSP} and the basic usage. In |
| 157 |
Section~\ref{sec:examples}, several examples are used to illustrate the |
| 158 |
package's capabilities. Section~\ref{sec:conclusion} concludes the |
| 159 |
paper. |
| 160 |
|
| 161 |
A previous version of this manuscript was published in the \emph{Journal |
| 162 |
of Statistical Software} \citep{Hahsler+Hornik2007}. |
| 163 |
|
| 164 |
\section{Theory} |
| 165 |
\label{sec:TSP} |
| 166 |
|
| 167 |
In this section, we briefly summarize some aspects of the TSP which are |
| 168 |
important for the implementation of the \pkg{TSP} package described in |
| 169 |
this paper. For a complete treatment of all aspects of the TSP, we |
| 170 |
refer the interested reader to the classic book edited by |
| 171 |
\cite{Lawler1985} and the more modern book edited by \cite{Gutin2002}. |
| 172 |
|
| 173 |
It has to be noted that in this paper, following the origin of the TSP, |
| 174 |
the term \emph{distance} is used. Distance is used here interchangeably |
| 175 |
with dissimilarity or cost and, unless explicitly stated, no |
| 176 |
restrictions to measures which obey the triangle inequality are made. |
| 177 |
An important distinction can be made between the symmetric TSP and the |
| 178 |
more general asymmetric TSP. For the symmetric case (normally referred |
| 179 |
to as just \emph{TSP}), for all distances in $\mathbf{D}$ the equality |
| 180 |
$d_{ij} = d_{ji}$ holds, i.e., it does not matter if we travel from $i$ |
| 181 |
to $j$ or the other way round, the distance is the same. In the |
| 182 |
asymmetric case (called \emph{ATSP}), the distances are not equal for |
| 183 |
all pairs of cities. Problems of this kind arise when we do not deal |
| 184 |
with spatial distances between cities but, e.g., with the cost or |
| 185 |
necessary time associated with traveling between locations, where the |
| 186 |
price for the plane ticket between two cities may be different depending |
| 187 |
on which way we go. |
| 188 |
|
| 189 |
\subsection{Different formulations of the TSP} |
| 190 |
\label{sec:formulations} |
| 191 |
|
| 192 |
Other than the permutation problem in the introduction, the TSP can also |
| 193 |
be formulated as a graph theoretic problem. Here the TSP is formulated |
| 194 |
by means of a complete graph $G = (V, E)$, where the cities correspond |
| 195 |
to the node set $V = \{1,2,\ldots,n\}$ and each edge $e_i \in E$ has an |
| 196 |
associated weight $w_i$ representing the distance between the nodes it |
| 197 |
connects. If the graph is not complete, the missing edges can be |
| 198 |
replaced by edges with very large distances. The goal is to find a |
| 199 |
\emph{Hamiltonian cycle}, i.e., a cycle which visits each node in the |
| 200 |
graph exactly once, with the least weight in the |
| 201 |
graph~\citep{Hoffman1985}. This formulation naturally leads to |
| 202 |
procedures involving minimum spanning trees for tour construction or |
| 203 |
edge exchanges to improve existing tours. |
| 204 |
|
| 205 |
TSPs can also be represented as integer and linear programming |
| 206 |
problems~\citep[see, e.g.,][]{Punnen2002}. The \emph{integer programming (IP) |
| 207 |
formulation} is based on the assignment problem with additional |
| 208 |
constraint of no sub-tours: |
| 209 |
|
| 210 |
|
| 211 |
\[ |
| 212 |
\begin{array}{rl} |
| 213 |
\text{Minimize } & \sum_{i=1}^n\sum_{j=1}^n{d_{ij}x_{ij}} |
| 214 |
% = \mathrm{trace}(\mathbf{D}^T\mathbf{X}) |
| 215 |
\\[3mm] |
| 216 |
\text{Subject to } & \sum_{i=1}^n{x_{ij}=1}, \quad j=1,\ldots,n, \\ |
| 217 |
& \sum_{j=1}^n{x_{ij}=1}, \quad i=1,\ldots,n, \\ |
| 218 |
& x_{ij} = 0 \text{ or } 1 \\ |
| 219 |
& \text{no sub-tours allowed} \\ |
| 220 |
\end{array} |
| 221 |
\] |
| 222 |
|
| 223 |
The solution matrix $\mathbf{X} = (x_{ij})$ of the assignment problem |
| 224 |
represents a tour or a collection of sub-tour (several unconnected cycles) where |
| 225 |
only edges which corresponding to elements $x_{ij} = 1$ are on the tour or a |
| 226 |
sub-tour. The additional restriction that no sub-tours are allowed (called |
| 227 |
\emph{sub-tour elimination constraints}) restrict the solution to only proper |
| 228 |
tours. Unfortunately, the number of sub-tour elimination constraints grows |
| 229 |
exponentially with the number of cities which leads to an extremely hard |
| 230 |
problem. |
| 231 |
|
| 232 |
The \emph{linear programming (LP) formulation} of the TSP is given by: |
| 233 |
\[ |
| 234 |
\begin{array}{rl} |
| 235 |
\text{Minimize } & \sum_{i=1}^m{w_ix_i} = \mathbf{w}^T\mathbf{x}\\[3mm] |
| 236 |
\text{Subject to } & \mathbf{x} \in \mathcal{S} \\ |
| 237 |
\end{array} |
| 238 |
\] |
| 239 |
where $m$ is the number of edges $e_i$ in $G$, $w_i \in \mathbf{w}$ is the |
| 240 |
weight of edge $e_i$ and $\mathbf{x}$ is the incidence vector indicating the |
| 241 |
presence or absence of each edge in the tour. Again, the constraints given by |
| 242 |
$\mathbf{x} \in \mathcal{S}$ are problematic since they have to contain the set |
| 243 |
of incidence vectors of all possible Hamiltonian cycles in $G$ which amounts to |
| 244 |
a direct search of all $(n-1)!$ possibilities and thus in general is |
| 245 |
infeasible. However, relaxed versions of the linear programming problem with |
| 246 |
removed integrality and sub-tour elimination constraints are extensively used by |
| 247 |
modern TSP solvers where such a partial description of constraints is used and |
| 248 |
improved iteratively in a branch-and-bound approach. |
| 249 |
|
| 250 |
\subsection{Useful manipulations of the distance matrix} |
| 251 |
\label{sec:manipulations} |
| 252 |
|
| 253 |
Sometimes it is useful to transform the distance matrix $\mathbf{D} = (d_{ij})$ |
| 254 |
of a TSP into a different matrix $\mathbf{D'} = (d'_{ij})$ which has the same |
| 255 |
optimal solution. Such a transformation requires that for any |
| 256 |
Hamiltonian cycle $H$ in a graph represented by its distance matrix $\mathbf{D}$ |
| 257 |
the equality |
| 258 |
\begin{equation*} |
| 259 |
\sum_{i,j \in H}{d_{ij}} = \alpha \sum_{i,j \in H}{d'_{ij}} + \beta |
| 260 |
\end{equation*} |
| 261 |
holds for suitable $\alpha > 0$ and $\beta \in \mathbb{R}$. From the |
| 262 |
equality we see that additive and multiplicative constants leave the |
| 263 |
optimal solution invariant. This property is useful to rescale |
| 264 |
distances, e.g., for many solvers, distances in the interval $[0, 1]$ |
| 265 |
have to be converted into integers from~1 to a maximal value. |
| 266 |
|
| 267 |
A different manipulation is to reformulate an asymmetric TSP as a symmetric TSP. |
| 268 |
This is possible by doubling the number of cities~\citep{Jonker1983}. For each |
| 269 |
city a dummy city is added. Between each city and its corresponding dummy city |
| 270 |
a very small value (e.g., $-\infty$) is used. This makes sure that each |
| 271 |
city always occurs in the solution together with its dummy city. The original |
| 272 |
distances are used between the cities and the dummy cities, where each city is |
| 273 |
responsible for the distance going to the city and the dummy city is |
| 274 |
responsible for the distance coming from the city. The distances between all |
| 275 |
cities and the distances between all dummy cities are set to a very large |
| 276 |
value (e.g., $\infty$) which makes these edges infeasible. An example for |
| 277 |
equivalent formulations as an asymmetric TSP (to the left) and |
| 278 |
a symmetric TSP (to the right) for |
| 279 |
three cities is: |
| 280 |
|
| 281 |
\begin{equation*} |
| 282 |
\begin{pmatrix} |
| 283 |
0 &d_{12} &d_{13} \\ |
| 284 |
d_{21} &0 &d_{23} \\ |
| 285 |
d_{31} &d_{32} &0 \\ |
| 286 |
\end{pmatrix} |
| 287 |
\Longleftrightarrow |
| 288 |
\begin{pmatrix} |
| 289 |
0 &\infty &\infty & -\infty &d_{21} &d_{31} \\ |
| 290 |
\infty &0 &\infty & d_{12} &-\infty &d_{31} \\ |
| 291 |
\infty &\infty &0 & d_{13} &d_{23} &-\infty \\ |
| 292 |
-\infty &d_{12} &d_{13} & 0 &\infty &\infty \\ |
| 293 |
d_{21} &-\infty &d_{23} & \infty &0 &\infty \\ |
| 294 |
d_{31} &d_{32} &-\infty & \infty &\infty &0 \\ |
| 295 |
\end{pmatrix} |
| 296 |
\end{equation*} |
| 297 |
|
| 298 |
Instead of the infinity values suitably large negative and positive values can |
| 299 |
be used. The new symmetric TSP can be solved using techniques for symmetric |
| 300 |
TSPs which are currently far more advanced than techniques for ATSPs. |
| 301 |
Removing the dummy cities from the resulting tour gives the solution for the |
| 302 |
original ATSP. |
| 303 |
|
| 304 |
|
| 305 |
\subsection{Finding exact solutions for the TSP} |
| 306 |
\label{sec:exact} |
| 307 |
|
| 308 |
Finding the exact solution to a TSP with $n$ cities requires to check $(n-1)!$ |
| 309 |
possible tours. To evaluate all possible tours is infeasible for even small TSP |
| 310 |
instances. To find the optimal tour |
| 311 |
\cite{Held1962} presented the following |
| 312 |
\emph{dynamic programming} formulation: Given a subset of city indices |
| 313 |
(excluding the first city) |
| 314 |
$S \subset \{2, 3, \dots, n\}$ and $l \in S$, let $d^*(S, l)$ denote the length of the |
| 315 |
shortest path from city $1$ to city $l$, visiting all cities in $S$ in-between. |
| 316 |
For $S = \{l\}$, $d^*(S,l)$ is defined as $d_{1l}$. The shortest path for |
| 317 |
larger sets with $|S| > 1$ is |
| 318 |
|
| 319 |
\begin{equation} |
| 320 |
d^*(S,l) = \mathrm{min}_{m \in S\setminus\{l\}}\Bigl( d^*(S\setminus\{l\},m) + d_{ml}\Bigl). |
| 321 |
%\text{ for } |S| > 1. |
| 322 |
\end{equation} |
| 323 |
|
| 324 |
Finally, the minimal tour length for a complete tour which includes returning |
| 325 |
to city $1$ is |
| 326 |
|
| 327 |
\begin{equation} |
| 328 |
d^{**} = \mathrm{min}_{l \in \{2,3,\dots,n\}}\Bigl( d^*(\{2,3,\dots,n\}, l) |
| 329 |
+ d_{l1}\Bigl). |
| 330 |
\end{equation} |
| 331 |
|
| 332 |
Using the last two equations, the quantities $d^*(S,l)$ can be computed |
| 333 |
recursively and the minimal tour length $d^{**}$ can be found. In a |
| 334 |
second step, the optimal permutation $\pi = \{1, i_2, i_3,\dots,i_n\}$ |
| 335 |
of city indices $1$ through $n$ can be computed in reverse order, |
| 336 |
starting with $i_n$ and working successively back to $i_2$. The |
| 337 |
procedure exploits the fact that a permutation $\pi$ can only be |
| 338 |
optimal, if |
| 339 |
|
| 340 |
\begin{equation} |
| 341 |
d^{**} = d^*(\{2,3,\dots,n\}, i_n) + d_{i_n1} |
| 342 |
\end{equation} |
| 343 |
and, for $2 \le p \le n-1$, |
| 344 |
\begin{equation} |
| 345 |
d^*(\{i_2, i_3,\dots, i_p, i_{p+1}\}, i_{p+1}) = |
| 346 |
d^*(\{i_2,i_3,\dots,i_p\}, i_p) + d_{i_pi_{p+1}}. |
| 347 |
\end{equation} |
| 348 |
|
| 349 |
The space complexity of storing the values for all $d^*(S,l)$ is |
| 350 |
$(n-1)2^{n-2}$ which severely restricts the dynamic programming |
| 351 |
algorithm to TSP problems of small sizes. However, for very small TSP |
| 352 |
instances this approach is fast and efficient. |
| 353 |
%\marginpar{time complexity if order $n^22^n$. Check!} |
| 354 |
|
| 355 |
A different method, which can deal with larger instances, uses a relaxation of |
| 356 |
the linear programming problem presented in Section~\ref{sec:formulations} and |
| 357 |
iteratively tightens the relaxation till a solution is found. This general |
| 358 |
method for solving linear programming problems with complex and large |
| 359 |
inequality systems is called \emph{cutting plane method} and was introduced by |
| 360 |
\cite{Dantzig1954}. |
| 361 |
|
| 362 |
Each iteration begins with using instead of the original linear |
| 363 |
inequality description $\mathcal{S}$ the relaxation $A\mathbf{x} \le b$, |
| 364 |
where the polyhedron $P$ defined by the relaxation contains |
| 365 |
$\mathcal{S}$ and is bounded. The optimal solution $\mathbf{x}^*$ of |
| 366 |
the relaxed problem can be obtained using standard linear programming |
| 367 |
solvers. If the $\mathbf{x}^*$ found belongs to $\mathcal{S}$, the |
| 368 |
optimal solution of the original problem is obtained, otherwise, a |
| 369 |
linear inequality can be found which is satisfied by all points in |
| 370 |
$\mathcal{S}$ but violated by $\mathbf{x}^*$. Such an inequality is |
| 371 |
called a cutting plane or cut. A family of such cutting planes can be |
| 372 |
added to the inequality system $A\mathbf{x} \le b$ to obtain a tighter |
| 373 |
relaxation for the next iteration. |
| 374 |
|
| 375 |
If no further cutting planes can be found or the improvement in the |
| 376 |
objective function due to adding cuts gets very small, the problem is |
| 377 |
branched into two sub-problems which can be minimized |
| 378 |
separately. Branching is done iteratively which leads to a binary tree |
| 379 |
of sub-problems. Each sub-problem is either solved without further |
| 380 |
branching or is found to be irrelevant because its relaxed version |
| 381 |
already produces a longer path than a solution of another sub-problem. |
| 382 |
This method is called \emph{branch-and-cut}~\citep{Padberg1990} which is |
| 383 |
a variation of the well known \emph{branch-and-bound}~\citep{Land1960} |
| 384 |
procedure. |
| 385 |
|
| 386 |
The initial polyhedron $P$ used by \cite{Dantzig1954} contains all |
| 387 |
vectors $\mathbf{x}$ for which all $x_e \in \mathbf{x}$ satisfy $0 \le |
| 388 |
x_e \le 1$ and in the resulting tour each city is linked to exactly two |
| 389 |
other cities. Various separation algorithms for finding subsequent cuts |
| 390 |
to prevent sub-tours (\emph{sub-tour elimination inequalities}) and to |
| 391 |
ensure an integer solution \citep[\emph{Gomory cuts;}][]{Gomory1963} |
| 392 |
were developed over time. The currently most efficient implementation of |
| 393 |
this method is \emph{Concorde} described in~\cite{Applegate2000}. |
| 394 |
|
| 395 |
\subsection{Heuristics for the TSP} |
| 396 |
\label{sec:heuristics} |
| 397 |
|
| 398 |
The NP-completeness of the TSP already makes it more time efficient for |
| 399 |
small-to-medium size TSP instances to rely on heuristics in case a good |
| 400 |
but not necessarily optimal solution is sufficient. TSP heuristics |
| 401 |
typically fall into two groups, tour construction heuristics which |
| 402 |
create tours from scratch and tour improvement heuristics which use |
| 403 |
simple local search heuristics to improve existing tours. |
| 404 |
|
| 405 |
In the following we will only discuss heuristics available in \pkg{TSP}, for a |
| 406 |
comprehensive overview of the multitude of TSP heuristics including an |
| 407 |
experimental comparison, we refer the reader to the book chapter by |
| 408 |
\cite{Johnson2002}. |
| 409 |
|
| 410 |
\subsubsection{Tour construction heuristics} |
| 411 |
The implemented tour construction heuristics are the nearest neighbor algorithm |
| 412 |
and the insertion algorithms. |
| 413 |
|
| 414 |
\paragraph{Nearest neighbor algorithm.} |
| 415 |
|
| 416 |
The nearest neighbor algorithm~\citep{Rosenkrantz1977} follows a very |
| 417 |
simple greedy procedure: The algorithm starts with a tour containing a |
| 418 |
randomly chosen city and then always adds to the last city in the tour |
| 419 |
the nearest not yet visited city. The algorithm stops when all cities |
| 420 |
are on the tour. |
| 421 |
|
| 422 |
An extension to this algorithm is to repeat it with each city as the |
| 423 |
starting point and then return the best tour found. This heuristic is |
| 424 |
called repetitive nearest neighbor. |
| 425 |
|
| 426 |
\paragraph{Insertion algorithms.} |
| 427 |
|
| 428 |
All insertion algorithms~\citep{Rosenkrantz1977} start with a tour |
| 429 |
consisting of an arbitrary city and then choose in each step a city $k$ |
| 430 |
not yet on the tour. This city is inserted into the existing tour |
| 431 |
between two consecutive cities $i$ and $j$, such that the insertion cost |
| 432 |
(i.e., the increase in the tour's length) |
| 433 |
$$d(i,k) + d(k,j) - d(i,j)$$ |
| 434 |
is minimized. The algorithms stop when all cities are on the tour. |
| 435 |
|
| 436 |
The insertion algorithms differ in the way the city to be inserted next |
| 437 |
is chosen. The following variations are implemented: |
| 438 |
|
| 439 |
\begin{description} |
| 440 |
\item[Nearest insertion] The city $k$ is chosen in each step as |
| 441 |
the city which is nearest to a city on the tour. |
| 442 |
|
| 443 |
\item[Farthest insertion] The city $k$ is chosen in each step as |
| 444 |
the city which is farthest from any of the cities on the tour. |
| 445 |
|
| 446 |
\item[Cheapest insertion] The city $k$ is chosen in each step |
| 447 |
such that the cost of inserting the new city is minimal. |
| 448 |
|
| 449 |
\item[Arbitrary insertion] The city $k$ is chosen randomly from all cities |
| 450 |
not yet on the tour. |
| 451 |
|
| 452 |
\end{description} |
| 453 |
|
| 454 |
|
| 455 |
The nearest and cheapest insertion algorithms correspond to the minimum |
| 456 |
spanning tree algorithm by \cite{Prim1957}. Adding a city to a partial tour |
| 457 |
corresponds to adding an edge to a partial spanning tree. For TSPs with |
| 458 |
distances obeying the triangular inequality, the equality to minimum spanning |
| 459 |
trees provides a theoretical upper bound for the two algorithms of twice the |
| 460 |
optimal tour length. |
| 461 |
|
| 462 |
The idea behind the farthest insertion algorithm is to link cities far |
| 463 |
outside into the tour first to establish an outline of the whole tour |
| 464 |
early. With this change, the algorithm cannot be directly related to |
| 465 |
generating a minimum spanning tree and thus the upper bound stated above |
| 466 |
cannot be guaranteed. However, it can was shown that the algorithm |
| 467 |
generates tours which approach $2/3$ times the optimal tour |
| 468 |
length~\citep{Johnson1985}. |
| 469 |
|
| 470 |
\subsubsection{Tour improvement heuristics} |
| 471 |
|
| 472 |
Tour improvement heuristics are simple local search heuristics which try to |
| 473 |
improve an initial tour. A comprehensive treatment of the topic |
| 474 |
can be found in the book chapter by \cite{Rego2002}. |
| 475 |
|
| 476 |
\paragraph{$k$-Opt heuristics.} The idea is to define a neighborhood structure |
| 477 |
on the set of all admissible tours. Typically, a tour $t'$ is a neighbor of |
| 478 |
another tour $t$ if $t'$ can be obtained from $t$ by deleting $k$ edges |
| 479 |
and replacing them by a set of different feasible edges (a $k$-Opt move). In |
| 480 |
such a structure, the tour can iteratively be improved by always moving from |
| 481 |
one tour to its best neighbor till no further improvement is possible. The |
| 482 |
resulting tour represents a local optimum which is called $k$-optimal. |
| 483 |
|
| 484 |
Typically, $2$-Opt~\citep{Croes1958} and $3$-Opt~\citep{Lin1965} heuristics |
| 485 |
are used in practice. |
| 486 |
|
| 487 |
\paragraph{Lin-Kernighan heuristic.} |
| 488 |
|
| 489 |
This heuristic~\citep{Lin1973} does not use a fixed value for $k$ for |
| 490 |
its $k$-Opt moves, but tries to find the best choice of $k$ for each |
| 491 |
move. The heuristic uses the fact that each $k$-Opt move can be |
| 492 |
represented as a sequence of $2$-Opt moves. It builds up a sequence of |
| 493 |
$2$-Opt moves, checking after each additional move whether a stopping |
| 494 |
rule is met. Then the part of the sequence which gives the best |
| 495 |
improvement is used. This is equivalent to a choice of one $k$-Opt move |
| 496 |
with variable $k$. Such moves are used till a local optimum is reached. |
| 497 |
|
| 498 |
By using full backtracking, the optimal solution can always be found, but the |
| 499 |
running time would be immense. Therefore, only limited backtracking is allowed |
| 500 |
in the procedure, which helps to find better local optima or even the optimal |
| 501 |
solution. Further improvements to the procedure are described |
| 502 |
by \cite{Lin1973}. |
| 503 |
|
| 504 |
|
| 505 |
\section{Computational infrastructure: the TSP package} |
| 506 |
\label{sec:infrastructure} |
| 507 |
|
| 508 |
In package~\pkg{TSP}, a traveling salesperson problem is |
| 509 |
defined by an object of class \class{TSP} (symmetric) or \class{ATSP} |
| 510 |
(asymmetric). \func{solve\_TSP} |
| 511 |
is used to find a solution, which is represented by |
| 512 |
an object of class \class{TOUR}. Figure~\ref{fig:overview} gives an overview |
| 513 |
of this infrastructure. |
| 514 |
|
| 515 |
\begin{figure} |
| 516 |
\centering |
| 517 |
\includegraphics[width=14cm]{overview} |
| 518 |
\caption{An overview of the classes in \pkg{TSP}.} |
| 519 |
\label{fig:overview} |
| 520 |
\end{figure} |
| 521 |
|
| 522 |
|
| 523 |
\class{TSP} objects can be created from a distance matrix (a |
| 524 |
\class{dist} object) or a symmetric matrix using the creator function |
| 525 |
\func{TSP} or coercion with \func{as.TSP}. Similarly, \class{ATSP} |
| 526 |
objects are created by \func{ATSP} or \func{as.ATSP} from square |
| 527 |
matrices representing the distances. In the creation process, labels |
| 528 |
are taken and stored as city names in the object or can be explicitly |
| 529 |
given as arguments to the creator functions. Several methods are |
| 530 |
defined for the classes: |
| 531 |
\begin{itemize} |
| 532 |
\item \func{print} displays basic information about the problem (number |
| 533 |
of cities and the distance measure employed). |
| 534 |
\item \func{n\_of\_cities} returns the number of cities. |
| 535 |
\item \func{labels} returns the city names. |
| 536 |
\item \func{image} produces a shaded matrix plot of the distances |
| 537 |
between cities. The order of the cities can be specified as the |
| 538 |
argument \code{order}. |
| 539 |
\end{itemize} |
| 540 |
|
| 541 |
Internally, an object of class \class{TSP} is a \class{dist} object with |
| 542 |
an additional class attribute and, therefore, if needed, can be coerced |
| 543 |
to \class{dist} or to a matrix. An \class{ATSP} object is represented |
| 544 |
as a square matrix. Obviously, asymmetric TSPs are more general than |
| 545 |
symmetric TSPs, hence, symmetric TSPs can also be represented as |
| 546 |
asymmetric TSPs. To formulate an asymmetric TSP as a symmetric TSP with |
| 547 |
double the number of cities (see Section \ref{sec:manipulations}), |
| 548 |
\func{reformulate\_ATSP\_as\_TSP} is provided. This function creates |
| 549 |
the necessary dummy cities and adapts the distance matrix accordingly. |
| 550 |
|
| 551 |
A popular format to save TSP descriptions to disk which is supported by |
| 552 |
most TSP solvers is the format used by \emph{TSPLIB}, a library of |
| 553 |
sample instances of the TSP maintained by \cite{Reinelt2004}. The |
| 554 |
\pkg{TSP} package provides \func{read\_TSPLIB} and \func{write\_TSPLIB} |
| 555 |
to read and save symmetric and asymmetric TSPs in TSPLIB format. |
| 556 |
|
| 557 |
Class \class{TOUR} represents a solution to a TSP by an integer |
| 558 |
permutation vector containing the ordered indices and labels of the |
| 559 |
cities to visit. In addition, it stores an attribute indicating the |
| 560 |
length of the tour. Again, suitable \func{print} and \func{labels} |
| 561 |
methods are provided. The raw permutation vector (i.e., the order in |
| 562 |
which cities are visited) can be obtained from a tour using |
| 563 |
\func{as.integer}. With \func{cut\_tour}, a circular tour can be split |
| 564 |
at a specified city resulting in a path represented by a vector of city |
| 565 |
indices. |
| 566 |
|
| 567 |
The length of a tour can always be calculated using \func{tour\_length} |
| 568 |
and specifying a TSP and a tour. Instead of the tour, an integer |
| 569 |
permutation vector calculated outside the \pkg{TSP} package can be used |
| 570 |
as long as it has the correct length. |
| 571 |
|
| 572 |
All TSP solvers in \pkg{TSP} can be used with the simple common interface: |
| 573 |
|
| 574 |
\begin{quote} |
| 575 |
\code{solve\_TSP(x, method, control)} |
| 576 |
\end{quote} |
| 577 |
where \code{x} is the TSP to be solved, \code{method} is a character |
| 578 |
string indicating the method used to solve the TSP and \code{control} |
| 579 |
can contain a list with additional information used by the solver. |
| 580 |
The available algorithms are shown in Table~\ref{tab:methods}. |
| 581 |
|
| 582 |
\begin{table} |
| 583 |
\caption{Available algorithms in \pkg{TSP}.} |
| 584 |
\label{tab:methods} |
| 585 |
\centering |
| 586 |
\begin{tabular}{llc} |
| 587 |
\hline |
| 588 |
\textbf{Algorithm} & \textbf{Method argument} & \textbf{Applicable to} \\ |
| 589 |
\hline |
| 590 |
Nearest neighbor algorithm & \code{"nn"} & TSP/ATSP \\ |
| 591 |
Repetitive nearest neighbor algorithm & \code{"repetitive\_nn"} |
| 592 |
& TSP/ATSP \\ |
| 593 |
Nearest insertion & \code{"nearest\_insertion"} & TSP/ATSP \\ |
| 594 |
Farthest insertion & \code{"farthest\_insertion"} & TSP/ATSP \\ |
| 595 |
Cheapest insertion & \code{"cheapest\_insertion"} & TSP/ATSP \\ |
| 596 |
Arbitrary insertion & \code{"arbitrary\_insertion"} & TSP/ATSP \\ |
| 597 |
Concorde TSP solver & \code{"concorde"} & TSP \\ |
| 598 |
2-Opt improvement heuristic & \code{"two\_opt"} & TSP/ATSP \\ |
| 599 |
Chained Lin-Kernighan & \code{"linkern"} & TSP \\ |
| 600 |
\hline |
| 601 |
\end{tabular} |
| 602 |
\end{table} |
| 603 |
|
| 604 |
All algorithms except the Concorde TSP solver and the Chained |
| 605 |
Lin-Kernighan heuristic (a Lin-Kernighan variation described in |
| 606 |
\cite{Applegate2003}) are included in the package and distributed under |
| 607 |
the GNU Public License (GPL). For the Concorde TSP solver and the |
| 608 |
Chained Lin-Kernighan heuristic only a simple interface (using |
| 609 |
\func{write\_TSPLIB}, calling the executable and reading back the |
| 610 |
resulting tour) is included in \pkg{TSP}. The executable itself is part |
| 611 |
of the Concorde distribution, has to be installed separately and is |
| 612 |
governed by a different license which allows only for academic use. The |
| 613 |
interfaces are included since |
| 614 |
Concorde~\citep{Applegate2000,Applegate2006} is currently one of the |
| 615 |
best implementations for solving symmetric TSPs based on the |
| 616 |
branch-and-cut method discussed in section~\ref{sec:exact}. In May |
| 617 |
2004, Concorde was used to find the optimal solution for the TSP of |
| 618 |
visiting all 24,978 cities in Sweden. The computation was carried out |
| 619 |
on a cluster with 96 Xeon 2.8 GHz nodes and took in total almost 100 CPU |
| 620 |
years. |
| 621 |
|
| 622 |
\section{Examples} |
| 623 |
\label{sec:examples} |
| 624 |
|
| 625 |
In this section we provide some examples for the use of |
| 626 |
package~\pkg{TSP}. We start with a simple example of how to use the |
| 627 |
interface of the TSP solver to compare different heuristics. Then we |
| 628 |
show how to solve related tasks, using the Hamiltonian shortest path |
| 629 |
problem as an example. Finally, we give an example of clustering using |
| 630 |
the \pkg{TSP} package. An additional application can be found |
| 631 |
in package \pkg{seriation}~\citep{Hahsler+Buchta+Hornik:2006} which uses |
| 632 |
the TSP solvers from \pkg{TSP} to order (seriate) objects given a proximity |
| 633 |
matrix. |
| 634 |
|
| 635 |
\subsection{Comparing some heuristics} |
| 636 |
|
| 637 |
In the following example, we use several heuristics to find a short path |
| 638 |
in the \code{USCA50} data set which contains the distances between the |
| 639 |
first 50 cities in the \code{USCA312} data set. The \code{USCA312} data |
| 640 |
set contains the distances between 312 cities in the USA and Canada |
| 641 |
coded as a symmetric TSP. The smaller data set is used here, since some |
| 642 |
of the heuristic solvers employed are rather slow. |
| 643 |
|
| 644 |
<<>>= |
| 645 |
library("TSP") |
| 646 |
data("USCA50") |
| 647 |
USCA50 |
| 648 |
@ |
| 649 |
|
| 650 |
|
| 651 |
We calculate tours using different heuristics and store the results in |
| 652 |
the list \code{tours}. As an example, we show the first tour which |
| 653 |
displays the method employed, the number of cities involved and the tour |
| 654 |
length. All tour lengths are compared using the dot chart in |
| 655 |
Figure~\ref{fig:dotchart}. For the chart, we add a point for the |
| 656 |
optimal solution which has a tour length of 14497. The optimal solution |
| 657 |
can be found using Concorde (\code{method = "concorde"}). It is omitted |
| 658 |
here, since Concorde has to be installed separately. |
| 659 |
|
| 660 |
<<echo=FALSE>>= |
| 661 |
set.seed(1234) |
| 662 |
@ |
| 663 |
|
| 664 |
|
| 665 |
<<fig=TRUE, include=FALSE, label=dotchart_USCA50, width=7, height=4>>= |
| 666 |
methods <- c("nearest_insertion", "farthest_insertion", "cheapest_insertion", |
| 667 |
"arbitrary_insertion", "nn", "repetitive_nn", "two_opt") |
| 668 |
|
| 669 |
tours <- sapply(methods, FUN = function(m) solve_TSP(USCA50, method = m), |
| 670 |
simplify = FALSE) |
| 671 |
## tours$concorde <- solve_TSP(tsp, method = "concorde") |
| 672 |
|
| 673 |
tours[[1]] |
| 674 |
|
| 675 |
dotchart(sort(c(sapply(tours, tour_length), optimal = 14497)), |
| 676 |
xlab = "tour length", xlim = c(0, 20000)) |
| 677 |
@ |
| 678 |
|
| 679 |
\begin{figure} |
| 680 |
\centering |
| 681 |
\includegraphics[width=11cm, trim=0 10 0 0]{TSP-dotchart_USCA50} |
| 682 |
\caption{Comparison of the tour lengths for the USCA50 data set.} |
| 683 |
\label{fig:dotchart} |
| 684 |
\end{figure} |
| 685 |
|
| 686 |
|
| 687 |
\subsection{Finding the shortest Hamiltonian path} |
| 688 |
|
| 689 |
The problem of finding the shortest Hamiltonian path through a graph |
| 690 |
(i.e., a path which visits each node in the graph exactly once) can be |
| 691 |
transformed into the TSP with cities and distances representing the |
| 692 |
graphs vertices and edge weights, respectively~\citep{Garfinkel1985}. |
| 693 |
|
| 694 |
Finding the shortest Hamiltonian path through all cities disregarding |
| 695 |
the endpoints can be achieved by inserting a `dummy city' which has a |
| 696 |
distance of zero to all other cities. The position of this city in the |
| 697 |
final tour represents the cutting point for the path. In the following |
| 698 |
we use a heuristic to find a short path in the \code{USCA312} data set. |
| 699 |
Inserting dummy cities is performed in \pkg{TSP} by |
| 700 |
\func{insert\_dummy}. |
| 701 |
|
| 702 |
<<echo=FALSE>>= |
| 703 |
set.seed(1234) |
| 704 |
@ |
| 705 |
|
| 706 |
<<>>= |
| 707 |
library("TSP") |
| 708 |
data("USCA312") |
| 709 |
tsp <- insert_dummy(USCA312, label = "cut") |
| 710 |
tsp |
| 711 |
@ |
| 712 |
|
| 713 |
The TSP now contains an additional dummy city and we can try to solve |
| 714 |
this TSP. |
| 715 |
|
| 716 |
<<>>= |
| 717 |
tour <- solve_TSP(tsp, method="farthest_insertion") |
| 718 |
tour |
| 719 |
@ |
| 720 |
|
| 721 |
Since the dummy city has distance zero to all other cities, the path length is |
| 722 |
equal to the tour length reported above. The path starts with the first city in |
| 723 |
the list after the `dummy' city and ends with the city right before it. |
| 724 |
We use \func{cut\_tour} to create a path and show the |
| 725 |
first and last 6 cities on it. |
| 726 |
|
| 727 |
<<>>= |
| 728 |
path <- cut_tour(tour, "cut") |
| 729 |
head(labels(path)) |
| 730 |
tail(labels(path)) |
| 731 |
@ |
| 732 |
|
| 733 |
The tour found in the example results in a path from Lihue on Hawaii to |
| 734 |
Prince Rupert in British Columbia. Such a tour can also be visualized |
| 735 |
using a scatter plot with a map from package \pkg{maps}. Note that the \code{if} statement and the \code{plot} in the \code{else} part in the following is not needed and only checks if the map package is installed when building this document. |
| 736 |
|
| 737 |
<<fig=TRUE, include=FALSE, label=map1, width=8, height=8>>= |
| 738 |
if(require(maps)) { |
| 739 |
library("maps") |
| 740 |
|
| 741 |
data("USCA312_GPS") |
| 742 |
|
| 743 |
plot_path <- function(path) { |
| 744 |
plot((USCA312_GPS[, c("long", "lat")]), cex = .3, col = "red") |
| 745 |
map("world", col = "gray", add = TRUE) |
| 746 |
lines(USCA312_GPS[, c("long", "lat")][path,], col = "black") |
| 747 |
points(USCA312_GPS[c(head(path, 1), tail(path, 1)), c("long", "lat")], pch = 19, col = "black") |
| 748 |
} |
| 749 |
|
| 750 |
plot_path(path) |
| 751 |
|
| 752 |
} else { |
| 753 |
plot(NA, xlim= c(0,1), ylim = c(0,1)) |
| 754 |
text(.5, .5, "Suggested packages not available") |
| 755 |
} |
| 756 |
@ |
| 757 |
|
| 758 |
\begin{figure} |
| 759 |
\centering |
| 760 |
\includegraphics[width=10cm, trim=0 30 0 0]{TSP-map1} |
| 761 |
\caption{A ``short'' Hamiltonian path for the USCA312 dataset.} |
| 762 |
\label{fig:map1} |
| 763 |
\end{figure} |
| 764 |
|
| 765 |
The map containing the path is presented in Figure~\ref{fig:map1}. It |
| 766 |
has to be mentioned that the path found by the used heuristic is |
| 767 |
considerable longer than the optimal path found by Concorde with a |
| 768 |
length of $34928$, illustrating the power of modern TSP algorithms. |
| 769 |
|
| 770 |
For the following two examples, we indicate how the distance matrix |
| 771 |
between cities can be modified to solve related shortest Hamiltonian |
| 772 |
path problems. These examples serve as illustrations of how |
| 773 |
modifications can be made to transform different problems into a TSP. |
| 774 |
|
| 775 |
The first problem is to find the shortest Hamiltonian path starting with |
| 776 |
a given city. In this case, all distances to the selected city are set |
| 777 |
to zero, forcing the evaluation of all possible paths starting with this |
| 778 |
city and disregarding the way back from the final city in the tour. By |
| 779 |
modifying the distances the symmetric TSP is changed into an asymmetric |
| 780 |
TSP (ATSP) since the distances between the starting city and all other |
| 781 |
cities are no longer symmetric. |
| 782 |
|
| 783 |
As an example, we choose New York as the starting city. We transform |
| 784 |
the data set into an ATSP and set the column corresponding to New York |
| 785 |
to zero before solving it. Thus, the distance to return from the last |
| 786 |
city in the path to New York does not contribute to the path length. We |
| 787 |
use the nearest neighbor heuristic to calculate an initial tour which is |
| 788 |
then improved using $2$-Opt moves and cut at New York to create a path. |
| 789 |
|
| 790 |
|
| 791 |
<<echo=FALSE>>= |
| 792 |
set.seed(1234) |
| 793 |
@ |
| 794 |
|
| 795 |
<<>>= |
| 796 |
atsp <- as.ATSP(USCA312) |
| 797 |
ny <- which(labels(USCA312) == "New York, NY") |
| 798 |
atsp[, ny] <- 0 |
| 799 |
initial_tour <- solve_TSP(atsp, method="nn") |
| 800 |
initial_tour |
| 801 |
tour <- solve_TSP(atsp, method ="two_opt", control = list(tour = initial_tour)) |
| 802 |
tour |
| 803 |
path <- cut_tour(tour, ny, exclude_cut = FALSE) |
| 804 |
|
| 805 |
head(labels(path)) |
| 806 |
tail(labels(path)) |
| 807 |
@ |
| 808 |
<<fig=TRUE, include=FALSE, label=map2, width=8, height=8>>= |
| 809 |
plot_path(path) |
| 810 |
@ |
| 811 |
|
| 812 |
\begin{figure} |
| 813 |
\centering |
| 814 |
\includegraphics[width=10cm, trim=0 30 0 0]{TSP-map2} |
| 815 |
\caption{A Hamiltonian path for the USCA312 dataset starting in New York.} |
| 816 |
\label{fig:map2} |
| 817 |
\end{figure} |
| 818 |
|
| 819 |
The found path is presented in Figure~\ref{fig:map2}. It begins with New |
| 820 |
York and cities in New Jersey and ends in a city in Manitoba, Canada. |
| 821 |
%The path shows the typical behavior |
| 822 |
%of the nearest neighbor heuristic with first connecting the cities close by and |
| 823 |
%then making rather big ``jumps'' for the final cities. |
| 824 |
|
| 825 |
Concorde and many advanced TSP solvers can only solve symmetric TSPs. To |
| 826 |
use these solvers, we can formulate the ATSP as a TSP using |
| 827 |
\func{reformulate\_ATSP\_as\_TSP} which introduces a dummy city for each |
| 828 |
city (see Section~\ref{sec:manipulations}). |
| 829 |
|
| 830 |
<<>>= |
| 831 |
tsp <- reformulate_ATSP_as_TSP(atsp) |
| 832 |
tsp |
| 833 |
@ |
| 834 |
|
| 835 |
After finding a tour for the TSP, the dummy cities are removed again giving the |
| 836 |
tour for the original ATSP. |
| 837 |
Note that the tour needs to be reversed if the |
| 838 |
dummy cities appear before and not after the original cities in the solution of |
| 839 |
the TSP. The following code is not executed here, since it takes several |
| 840 |
minutes to execute and Concorde has to be installed separately. Concorde finds |
| 841 |
the optimal solution with a length of $36091$. |
| 842 |
|
| 843 |
|
| 844 |
<<eval=FALSE>>= |
| 845 |
tour <- solve_TSP(tsp, method = "concorde") |
| 846 |
tour <- as.TOUR(tour[tour <= n_of_cities(atsp)]) |
| 847 |
@ |
| 848 |
|
| 849 |
|
| 850 |
Finding the shortest Hamiltonian path which ends in a given city can be |
| 851 |
achieved likewise by setting the row in the distance matrix which |
| 852 |
corresponds to this city to zero. |
| 853 |
|
| 854 |
For finding the shortest Hamiltonian path we can also restrict both end |
| 855 |
points. This problem can be transformed to a TSP by replacing the two |
| 856 |
cities by a single city which contains the distances from the start |
| 857 |
point in the columns and the distances to the end point in the |
| 858 |
rows. Obviously this is again an asymmetric TSP. |
| 859 |
|
| 860 |
For the following example, we are only interested in paths starting in |
| 861 |
New York and ending in Los Angeles. Therefore, we remove the two cities |
| 862 |
from the distance matrix, create an asymmetric TSP and insert a dummy |
| 863 |
city called \code{"LA/NY"}. The distances from this dummy city are |
| 864 |
replaced by the distances from New York and the distances towards are |
| 865 |
replaced by the distances towards Los Angeles. |
| 866 |
|
| 867 |
|
| 868 |
<<echo=FALSE>>= |
| 869 |
set.seed(1234) |
| 870 |
@ |
| 871 |
|
| 872 |
<<>>= |
| 873 |
m <- as.matrix(USCA312) |
| 874 |
ny <- which(labels(USCA312) == "New York, NY") |
| 875 |
la <- which(labels(USCA312) == "Los Angeles, CA") |
| 876 |
|
| 877 |
atsp <- ATSP(m[-c(ny,la), -c(ny,la)]) |
| 878 |
atsp <- insert_dummy(atsp, label = "LA/NY") |
| 879 |
|
| 880 |
la_ny <- which(labels(atsp) == "LA/NY") |
| 881 |
atsp[la_ny, ] <- c(m[-c(ny,la), ny], 0) |
| 882 |
atsp[, la_ny] <- c(m[la, -c(ny,la)], 0) |
| 883 |
@ |
| 884 |
|
| 885 |
|
| 886 |
We use the nearest insertion heuristic. |
| 887 |
<<>>= |
| 888 |
tour <- solve_TSP(atsp, method ="nearest_insertion") |
| 889 |
tour |
| 890 |
|
| 891 |
path_labels <- c("New York, NY", |
| 892 |
labels(cut_tour(tour, la_ny)), "Los Angeles, CA") |
| 893 |
path_ids <- match(path_labels, labels(USCA312)) |
| 894 |
|
| 895 |
head(path_labels) |
| 896 |
tail(path_labels) |
| 897 |
@ |
| 898 |
<<fig=TRUE, include=FALSE, label=map3, width=8, height=8>>= |
| 899 |
plot_path(path_ids) |
| 900 |
@ |
| 901 |
|
| 902 |
|
| 903 |
The path jumps from New York to cities in Ontario and it passes through |
| 904 |
cities in California and Nevada before ending in Los Angeles. The path |
| 905 |
displayed in Figure~\ref{fig:map3} contains multiple crossings which |
| 906 |
indicate that the solution is suboptimal. The optimal solution generated |
| 907 |
by reformulating the problem as a TSP and using Concorde has only a tour |
| 908 |
length of $38489$. |
| 909 |
|
| 910 |
\begin{figure} |
| 911 |
\centering |
| 912 |
\includegraphics[width=10cm, trim=0 30 0 0]{TSP-map3} |
| 913 |
\caption{A Hamiltonian path for the USCA312 dataset starting in New York |
| 914 |
and ending in Los Angles.} |
| 915 |
\label{fig:map3} |
| 916 |
\end{figure} |
| 917 |
|
| 918 |
|
| 919 |
\subsection{Rearrangement clustering} |
| 920 |
Solving a TSP to obtain a clustering was suggested several times in the |
| 921 |
literature \citep[see, e.g.,][]{Lenstra1974, Alpert1997, Johnson2004}. The idea |
| 922 |
is that objects in clusters are visited in consecutive order and from one |
| 923 |
cluster to the next larger ``jumps'' are necessary. \cite{Climer2006} call |
| 924 |
this type of clustering \emph{rearrangement clustering} and suggest to |
| 925 |
automatically find the cluster boundaries of $k$ clusters by adding $k$ |
| 926 |
\emph{dummy cities} which have constant distance $c$ to all other cities and |
| 927 |
are infinitely far from each other. In the optimal |
| 928 |
solution of the TSP, the dummy cities must separate the most distant cities and |
| 929 |
thus represent optimal boundaries for $k$ clusters. |
| 930 |
|
| 931 |
For the following example, we use the well known iris data set. Since we |
| 932 |
know that the dataset contains three classes denoted by the variable |
| 933 |
\code{Species}, we insert three dummy cities into the TSP for the iris |
| 934 |
data set and perform rearrangement clustering using the default method |
| 935 |
(nearest insertion algorithm). Note that this algorithm does not find |
| 936 |
the optimal solution and it is not guaranteed that the dummy cities will |
| 937 |
present the best cluster boundaries. |
| 938 |
%\marginpar{FIXME: Was sagt Concorde dazu?} |
| 939 |
|
| 940 |
<<echo=FALSE>>= |
| 941 |
set.seed(4444) |
| 942 |
@ |
| 943 |
<<>>= |
| 944 |
data("iris") |
| 945 |
tsp <- TSP(dist(iris[-5]), labels = iris[, "Species"]) |
| 946 |
tsp_dummy <- insert_dummy(tsp, n = 3, label = "boundary") |
| 947 |
tour <- solve_TSP(tsp_dummy) |
| 948 |
@ |
| 949 |
|
| 950 |
Next, we plot the TSP's permuted distance matrix using shading to |
| 951 |
represent distances. The result is displayed as |
| 952 |
Figure~\ref{fig:clustering}. Lighter areas represent larger |
| 953 |
distances. The additional red lines represent the positions of the dummy |
| 954 |
cities in the tour, which mark the cluster boundaries obtained. |
| 955 |
|
| 956 |
|
| 957 |
<<fig=TRUE, include=FALSE, label=clustering>>= |
| 958 |
## plot the distance matrix |
| 959 |
image(tsp_dummy, tour, xlab = "objects", ylab ="objects") |
| 960 |
|
| 961 |
## draw lines where the dummy cities are located |
| 962 |
abline(h = which(labels(tour)=="boundary"), col = "red") |
| 963 |
abline(v = which(labels(tour)=="boundary"), col = "red") |
| 964 |
@ |
| 965 |
|
| 966 |
|
| 967 |
\begin{figure} |
| 968 |
\centering |
| 969 |
\includegraphics[width=9cm, height=9cm, trim=0 20 0 0]{TSP-clustering} |
| 970 |
\caption{Result of rearrangement clustering using three dummy cities and the |
| 971 |
nearest insertion algorithm on the iris data set.} |
| 972 |
\label{fig:clustering} |
| 973 |
\end{figure} |
| 974 |
|
| 975 |
|
| 976 |
One pair of red horizontal and vertical lines exactly separates the |
| 977 |
darker from lighter areas. The second pair occurs inside the larger |
| 978 |
dark block. We can look at how well the partitioning obtained fits the |
| 979 |
structure in the data given by the species field in the data set. Since |
| 980 |
we used the species as the city labels in the TSP, the labels in the |
| 981 |
tour represent the partitioning with the dummy cities named `boundary' |
| 982 |
separating groups. The result can be summarized based on the run length |
| 983 |
encoding of the obtained tour labels: |
| 984 |
|
| 985 |
<<>>= |
| 986 |
out <- rle(labels(tour)) |
| 987 |
data.frame(Species = out$values, |
| 988 |
Lenghts = out$lengths, |
| 989 |
Pos = cumsum(out$lengths)) |
| 990 |
@ |
| 991 |
|
| 992 |
|
| 993 |
One boundary perfectly splits the iris data set into a group containing |
| 994 |
only examples of species `Setosa' and a second group containing examples |
| 995 |
for `Virginica' and `Versicolor'. However, the second boundary only |
| 996 |
separates several examples of species `Virginica' from other examples of |
| 997 |
the same species. Even in the optimal tour found by Concorde, this |
| 998 |
problem occurs. The reason why the rearrangement clustering fails to |
| 999 |
split the data into three groups is the closeness between the groups |
| 1000 |
`Virginica' and `Versicolor'. To inspect this problem further, we can |
| 1001 |
project the data points on the first two principal components of the |
| 1002 |
data set and add the path segments which resulted from solving the TSP. |
| 1003 |
|
| 1004 |
<<fig=TRUE, include=FALSE, label=clustering2>>= |
| 1005 |
prc <- prcomp(iris[1:4]) |
| 1006 |
plot(prc$x, pch = as.numeric(iris[,5]), col = as.numeric(iris[,5])) |
| 1007 |
|
| 1008 |
paths <- cut_tour(tour, cut = "boundary") |
| 1009 |
for(p in paths) lines(prc$x[p, ]) |
| 1010 |
@ |
| 1011 |
|
| 1012 |
\begin{figure} |
| 1013 |
\centering |
| 1014 |
\includegraphics[width=10cm, trim=0 20 0 0]{TSP-clustering2} |
| 1015 |
\caption{The 3 path segments representing a rearrangement clustering of the |
| 1016 |
iris data set. The data points are projected on the set's first two principal |
| 1017 |
components. The three species are represented by different markers and |
| 1018 |
colors.} |
| 1019 |
\label{fig:clustering2} |
| 1020 |
\end{figure} |
| 1021 |
|
| 1022 |
The result in shown in Figure~\ref{fig:clustering2}. The three species |
| 1023 |
are identified by different markers and all points connected by a single |
| 1024 |
path represent a cluster found. Clearly, the two groups to the right |
| 1025 |
side of the plot are too close to be separated correctly by using just |
| 1026 |
the distances between individual points. This problem is similar to the |
| 1027 |
\emph{chaining effect} known from hierarchical clustering using the |
| 1028 |
single-linkage method. |
| 1029 |
|
| 1030 |
\section{Conclusion} |
| 1031 |
\label{sec:conclusion} |
| 1032 |
|
| 1033 |
In this paper we presented the R extension package \pkg{TSP} which |
| 1034 |
implements an infrastructure to handle and solve TSPs. The package |
| 1035 |
introduces classes for problem descriptions (\class{TSP} and |
| 1036 |
\class{ATSP}) and for the solution (\class{TOUR}). Together with a |
| 1037 |
simple interface for solving TSPs, it allows for an easy and transparent |
| 1038 |
usage of the package. |
| 1039 |
|
| 1040 |
With the interface to Concorde, \pkg{TSP} also can use a state of the |
| 1041 |
art implementation which efficiently computes exact solutions using |
| 1042 |
branch-and-cut. |
| 1043 |
|
| 1044 |
\section*{Acknowledgments} |
| 1045 |
|
| 1046 |
The authors of this paper want to thank Roger Bivand for providing the |
| 1047 |
code to correctly draw tours and paths on a projected map. |
| 1048 |
|
| 1049 |
|
| 1050 |
% |
| 1051 |
%\bibliographystyle{abbrvnat} |
| 1052 |
\bibliography{TSP} |
| 1053 |
% |
| 1054 |
\end{document} |
| 1055 |
|