Debian Codegraph @

inst/doc/TSP.Rnw

raw
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