Title:  Infrastructure for the Traveling Salesperson Problem 

Description:  Basic infrastructure and some algorithms for the traveling salesperson problem (also traveling salesman problem; TSP). The package provides some simple algorithms and an interface to the Concorde TSP solver and its implementation of the ChainedLinKernighan heuristic. The code for Concorde itself is not included in the package and has to be obtained separately. Hahsler and Hornik (2007) <doi:10.18637/jss.v023.i02>. 
Authors:  Michael Hahsler [aut, cre, cph] , Kurt Hornik [aut, cph] 
Maintainer:  Michael Hahsler <[email protected]> 
License:  GPL3 
Version:  1.24.1 
Built:  20241027 06:20:21 UTC 
Source:  https://github.com/mhahsler/TSP 
Constructor to create an instance of the asymmetric traveling salesperson problem (ATSP) and some auxiliary methods.
ATSP(x, labels = NULL, method = NULL) as.ATSP(x) ## S3 method for class 'matrix' as.ATSP(x) ## S3 method for class 'dist' as.ATSP(x) ## S3 method for class 'ATSP' print(x, ...) ## S3 method for class 'ATSP' n_of_cities(x) ## S3 method for class 'ATSP' labels(object, ...) ## S3 method for class 'ATSP' image(x, order, col = gray.colors(64), ...) ## S3 method for class 'ATSP' as.matrix(x, ...)
ATSP(x, labels = NULL, method = NULL) as.ATSP(x) ## S3 method for class 'matrix' as.ATSP(x) ## S3 method for class 'dist' as.ATSP(x) ## S3 method for class 'ATSP' print(x, ...) ## S3 method for class 'ATSP' n_of_cities(x) ## S3 method for class 'ATSP' labels(object, ...) ## S3 method for class 'ATSP' image(x, order, col = gray.colors(64), ...) ## S3 method for class 'ATSP' as.matrix(x, ...)
x , object

an object (a square matrix) to be converted into an

labels 
optional city labels. If not given, labels are taken from

method 
optional name of the distance metric. 
... 
further arguments are passed on. 
order 
order of cities as an integer vector or an object of class

col 
color scheme for image. 
Objects of class ATSP
are internally represented by a matrix (use
as.matrix()
to get just the matrix).
ATSPs can be transformed into (larger) symmetric TSPs using
reformulate_ATSP_as_TSP()
.
ATSP()
returns x
as an object of class ATSP
.
n_of_cities()
returns the number of cities in x
.
labels()
returns a vector with the names of the cities in x
.
Michael Hahsler
Other TSP:
Concorde
,
ETSP()
,
TSP()
,
TSPLIB
,
insert_dummy()
,
reformulate_ATSP_as_TSP()
,
solve_TSP()
data < matrix(runif(10^2), ncol = 10, dimnames = list(1:10, 1:10)) atsp < ATSP(data) atsp ## use some methods n_of_cities(atsp) labels(atsp) ## calculate a tour tour < solve_TSP(atsp, method = "nn") tour tour_length(tour) image(atsp, tour)
data < matrix(runif(10^2), ncol = 10, dimnames = list(1:10, 1:10)) atsp < ATSP(data) atsp ## use some methods n_of_cities(atsp) labels(atsp) ## calculate a tour tour < solve_TSP(atsp, method = "nn") tour tour_length(tour) image(atsp, tour)
The Concorde TSP Solver package contains several solvers. Currently, interfaces to the Concorde solver (Applegate et al. 2001), one of the most advanced and fastest TSP solvers using branchandcut, and the Chained LinKernighan (Applegate et al. 2003) implementation are provided in TSP. Concorde can solve TSPs and ETSPs directly. ATSPs are reformulated as larger TSP's and then solved.
concorde_path(path) concorde_help() linkern_help()
concorde_path(path) concorde_help() linkern_help()
path 
a character string with the path to the directory where the executables are installed. 
Installation of Concorde
The Concorde TSP Solver is freely available for academic research. It is not included in the TSP R package and has to be obtained separately from the Concorde download page. Either download the precompiled executables and place them in a suitable directory (make sure they are executable), or you can get the source code and compile the program on your own. TSP needs to know where the executables are. There are two options:
use concorde_path()
to set the path to the
directory containing the executables for concorde and linkern, or
make
sure that the executables are in the search path stored in the PATH
environment variable (see Sys.setenv()
).
Using Concorde for solve_TSP()
solve_TSP()
uses write_TSPLIB()
to write the TSP for
Concorde and tries to find the appropriate precision
value (digits
after the decimal point) to convert the provided distances into the needed
integer value range. The precision
value can also be specified in
control
in solve_TSP()
with method Concorde. Warning
messages will alert the user if the conversion to integer values results
into rounding errors that are worse then what is specified in the
precision
control parameter.
To get a list of all available command line options which can be used via
the clo
option for solve_TSP
use concorde_help()
and
linkern_help()
. Several options (x, o,
N, Q) are not available via solve_TSP()
since they
are used by the interface.
If Concorde takes too long, then you can kill the 'concorde' process via your operating system and you can continue with R.
Nothing.
Michael Hahsler
Concorde home page, http://www.math.uwaterloo.ca/tsp/concorde/
David Applegate, Robert Bixby, Vasek Chvatal, William Cook (2001): TSP cuts which do not conform to the template paradigm, Computational Combinatorial Optimization, M. Junger and D. Naddef (editors), SpringerVerlag.
David Applegate and William Cook and Andre Rohe (2003): Chained LinKernighan for Large Traveling Salesman Problems, INFORMS Journal on Computing, 15, 82–92.
Other TSP:
ATSP()
,
ETSP()
,
TSP()
,
TSPLIB
,
insert_dummy()
,
reformulate_ATSP_as_TSP()
,
solve_TSP()
## Not run: ## see if Concorde is correctly installed concorde_path() ## set path to the Concorde executible if it is not in the search PATH ## Example: ## concorde_path("~/concorde/") concorde_help() data("USCA312") ## run concorde in verbose mode (v) with fast cuts only (V) solve_TSP(USCA312, method = "concorde", control = list(clo = "v V")) ## End(Not run)
## Not run: ## see if Concorde is correctly installed concorde_path() ## set path to the Concorde executible if it is not in the search PATH ## Example: ## concorde_path("~/concorde/") concorde_help() data("USCA312") ## run concorde in verbose mode (v) with fast cuts only (V) solve_TSP(USCA312, method = "concorde", control = list(clo = "v V")) ## End(Not run)
Cuts a tour at a specified city to form a path.
cut_tour(x, cut, exclude_cut = TRUE) ## S3 method for class 'TOUR' cut_tour(x, cut, exclude_cut = TRUE)
cut_tour(x, cut, exclude_cut = TRUE) ## S3 method for class 'TOUR' cut_tour(x, cut, exclude_cut = TRUE)
x 
an object of class TOUR. 
cut 
the index or label of the city/cities to cut the tour. 
exclude_cut 
exclude the city where we cut? If 
Returns a named vector with city ids forming the path. If multiple cuts are used then a list with paths is returned.
Michael Hahsler
Other TOUR:
TOUR()
,
solve_TSP()
,
tour_length()
data("USCA50") ## find a path starting at Austin, TX tour < solve_TSP(USCA50) path < cut_tour(tour, cut = "Austin, TX", exclude_cut = FALSE) path ## cut the tours at two cities tour < solve_TSP(USCA50) path < cut_tour(tour, cut = c("Austin, TX", "Cambridge, MA"), exclude_cut = FALSE) path ## cut a tour at the largest gap using a dummy city tsp < insert_dummy(USCA50, label = "cut") tour < solve_TSP(tsp) ## cut tour into path at the dummy city path < cut_tour(tour, "cut") path
data("USCA50") ## find a path starting at Austin, TX tour < solve_TSP(USCA50) path < cut_tour(tour, cut = "Austin, TX", exclude_cut = FALSE) path ## cut the tours at two cities tour < solve_TSP(USCA50) path < cut_tour(tour, cut = c("Austin, TX", "Cambridge, MA"), exclude_cut = FALSE) path ## cut a tour at the largest gap using a dummy city tsp < insert_dummy(USCA50, label = "cut") tour < solve_TSP(tsp) ## cut tour into path at the dummy city path < cut_tour(tour, "cut") path
Constructor to create an instance of a Euclidean traveling salesperson problem (TSP) represented by city coordinates and some auxiliary methods.
ETSP(x, labels = NULL) as.ETSP(x) ## S3 method for class 'matrix' as.ETSP(x) ## S3 method for class 'data.frame' as.ETSP(x) ## S3 method for class 'ETSP' as.TSP(x) ## S3 method for class 'ETSP' as.matrix(x, ...) ## S3 method for class 'ETSP' print(x, ...) ## S3 method for class 'ETSP' n_of_cities(x) ## S3 method for class 'ETSP' labels(object, ...) ## S3 method for class 'ETSP' image(x, order, col = gray.colors(64), ...) ## S3 method for class 'ETSP' plot(x, y = NULL, tour = NULL, tour_lty = 2, tour_col = 2, labels = TRUE, ...)
ETSP(x, labels = NULL) as.ETSP(x) ## S3 method for class 'matrix' as.ETSP(x) ## S3 method for class 'data.frame' as.ETSP(x) ## S3 method for class 'ETSP' as.TSP(x) ## S3 method for class 'ETSP' as.matrix(x, ...) ## S3 method for class 'ETSP' print(x, ...) ## S3 method for class 'ETSP' n_of_cities(x) ## S3 method for class 'ETSP' labels(object, ...) ## S3 method for class 'ETSP' image(x, order, col = gray.colors(64), ...) ## S3 method for class 'ETSP' plot(x, y = NULL, tour = NULL, tour_lty = 2, tour_col = 2, labels = TRUE, ...)
x , object

an object (data.frame or matrix) to be converted into a

labels 
logical; plot city labels. 
... 
further arguments are passed on. 
order 
order of cities for the image as an integer vector or an object of class TOUR. 
col 
color scheme for image. 
tour , y

a tour to be visualized. 
tour_lty , tour_col

line type and color for tour. 
Objects of class ETSP
are internally represented as a matrix
objects (use as.matrix()
to get the matrix
object).
ETSP()
returns x
as an object of class ETSP
.
n_of_cities()
returns the number of cities in x
.
labels()
returns a vector with the names of the cities in x
.
Michael Hahsler
Other TSP:
ATSP()
,
Concorde
,
TSP()
,
TSPLIB
,
insert_dummy()
,
reformulate_ATSP_as_TSP()
,
solve_TSP()
## create a random ETSP n < 20 x < data.frame(x = runif(n), y = runif(n), row.names = LETTERS[1:n]) etsp < ETSP(x) etsp ## use some methods n_of_cities(etsp) labels(etsp) ## plot ETSP and solution tour < solve_TSP(etsp) tour plot(etsp, tour, tour_col = "red") # plot with custom labels plot(etsp, tour, tour_col = "red", labels = FALSE) text(etsp, paste("City", rownames(etsp)), pos = 1)
## create a random ETSP n < 20 x < data.frame(x = runif(n), y = runif(n), row.names = LETTERS[1:n]) etsp < ETSP(x) etsp ## use some methods n_of_cities(etsp) labels(etsp) ## plot ETSP and solution tour < solve_TSP(etsp) tour plot(etsp, tour, tour_col = "red") # plot with custom labels plot(etsp, tour, tour_col = "red", labels = FALSE) text(etsp, paste("City", rownames(etsp)), pos = 1)
Inserts dummy cities into a TSP problem. A dummy city has the same, constant distance (0) to all other cities and is infinitely far from other dummy cities. A dummy city can be used to transform a shortest Hamiltonian path problem (i.e., finding an optimal linear order) into a shortest Hamiltonian cycle problem which can be solved by a TSP solvers (Garfinkel 1985).
insert_dummy(x, n = 1, const = 0, inf = Inf, label = "dummy") ## S3 method for class 'TSP' insert_dummy(x, n = 1, const = 0, inf = Inf, label = "dummy") ## S3 method for class 'ATSP' insert_dummy(x, n = 1, const = 0, inf = Inf, label = "dummy") ## S3 method for class 'ETSP' insert_dummy(x, n = 1, const = 0, inf = Inf, label = "dummy")
insert_dummy(x, n = 1, const = 0, inf = Inf, label = "dummy") ## S3 method for class 'TSP' insert_dummy(x, n = 1, const = 0, inf = Inf, label = "dummy") ## S3 method for class 'ATSP' insert_dummy(x, n = 1, const = 0, inf = Inf, label = "dummy") ## S3 method for class 'ETSP' insert_dummy(x, n = 1, const = 0, inf = Inf, label = "dummy")
x 
an object with a TSP problem. 
n 
number of dummy cities. 
const 
distance of the dummy cities to all other cities. 
inf 
distance between dummy cities. 
label 
labels for the dummy cities. If only one label is given, it is reused for all dummy cities. 
Several dummy cities can be used together with a TSP solvers to perform rearrangement clustering (Climer and Zhang 2006).
The dummy cities are inserted after the other cities in x
.
A const
of 0 is guaranteed to work if the TSP finds the optimal
solution. For heuristics returning suboptimal solutions, a higher
const
(e.g., 2 * max(x)
) might provide better results.
returns an object of the same class as x
.
Michael Hahsler
Sharlee Climer, Weixiong Zhang (2006): Rearrangement Clustering: Pitfalls, Remedies, and Applications, Journal of Machine Learning Research 7(Jun), pp. 919–943.
R.S. Garfinkel (1985): Motivation and modelling (chapter 2). In: E. L. Lawler, J. K. Lenstra, A.H.G. Rinnooy Kan, D. B. Shmoys (eds.) The traveling salesman problem  A guided tour of combinatorial optimization, Wiley & Sons.
Other TSP:
ATSP()
,
Concorde
,
ETSP()
,
TSP()
,
TSPLIB
,
reformulate_ATSP_as_TSP()
,
solve_TSP()
## Example 1: Find a short Hamiltonian path set.seed(1000) x < data.frame(x = runif(20), y = runif(20), row.names = LETTERS[1:20]) tsp < TSP(dist(x)) ## add a dummy city to cut the tour into a path tsp < insert_dummy(tsp, label = "cut") tour < solve_TSP(tsp) tour plot(x) lines(x[cut_tour(tour, cut = "cut"),]) ## Example 2: Rearrangement clustering of the iris dataset set.seed(1000) data("iris") tsp < TSP(dist(iris[5])) ## insert 2 dummy cities to creates 2 clusters tsp_dummy < insert_dummy(tsp, n = 3, label = "boundary") ## get a solution for the TSP tour < solve_TSP(tsp_dummy) ## plot the reordered distance matrix with the dummy cities as lines separating ## the clusters image(tsp_dummy, tour) abline(h = which(labels(tour)=="boundary"), col = "red") abline(v = which(labels(tour)=="boundary"), col = "red") ## plot the original data with paths connecting the points in each cluster plot(iris[,c(2,3)], col = iris[,5]) paths < cut_tour(tour, cut = "boundary") for(p in paths) lines(iris[p, c(2,3)]) ## Note: The clustering is not perfect!
## Example 1: Find a short Hamiltonian path set.seed(1000) x < data.frame(x = runif(20), y = runif(20), row.names = LETTERS[1:20]) tsp < TSP(dist(x)) ## add a dummy city to cut the tour into a path tsp < insert_dummy(tsp, label = "cut") tour < solve_TSP(tsp) tour plot(x) lines(x[cut_tour(tour, cut = "cut"),]) ## Example 2: Rearrangement clustering of the iris dataset set.seed(1000) data("iris") tsp < TSP(dist(iris[5])) ## insert 2 dummy cities to creates 2 clusters tsp_dummy < insert_dummy(tsp, n = 3, label = "boundary") ## get a solution for the TSP tour < solve_TSP(tsp_dummy) ## plot the reordered distance matrix with the dummy cities as lines separating ## the clusters image(tsp_dummy, tour) abline(h = which(labels(tour)=="boundary"), col = "red") abline(v = which(labels(tour)=="boundary"), col = "red") ## plot the original data with paths connecting the points in each cluster plot(iris[,c(2,3)], col = iris[,5]) paths < cut_tour(tour, cut = "boundary") for(p in paths) lines(iris[p, c(2,3)]) ## Note: The clustering is not perfect!
A ATSP can be formulated as a symmetric TSP by doubling the number of cities (Jonker and Volgenant 1983). The solution of the TSP also represents the solution of the original ATSP.
reformulate_ATSP_as_TSP(x, infeasible = Inf, cheap = Inf) filter_ATSP_as_TSP_dummies(tour, atsp)
reformulate_ATSP_as_TSP(x, infeasible = Inf, cheap = Inf) filter_ATSP_as_TSP_dummies(tour, atsp)
x 
an ATSP. 
infeasible 
value for infeasible connections. 
cheap 
value for distance between a city and its corresponding dummy city. 
tour 
a TOUR created for a ATSP reformulated as a TSP. 
atsp 
the original ATSP. 
To reformulate a ATSP as a TSP, for each city a dummy city (e.g, for 'New
York' a dummy city 'New York*') is added. Between each city and its
corresponding dummy city a very small (or negative) distance with value
cheap
is used.
To ensure that the solver places each cities always occurs in the
solution together with its dummy city, this cost has to be much smaller than
the distances in the TSP.
The original distances are used
between the cities and the dummy cities, where each city is responsible for
the distance going to the city and the dummy city is responsible for the
distance coming from the city. The distances between all cities and the
distances between all dummy cities are set to infeasible
, a very
large value which prevents the solver from using these links.
We use infinite values here and solve_TSP()
treats them appropriately.
filter_ATSP_as_TSP_dummies()
can be used to extract the solution for the original
ATSP from the tour found for an ATSP reformulated as a TSP. Note that the symmetric TSP
tour does not reveal the direction for the ATSP. The filter function computed the
tour length for both directions and returns the shorter tour.
solve_TSP()
has a parameter as_TSP
which preforms the reformulation and
filtering the dummy cities automatically.
Note on performance: Doubling the problem size is a performance issue especially has a negative impact on solution quality for heuristics. It should only be used together with Concorde when the optimal solution is required. Most heuristics can solve ATSPs directly with good solution quality.
reformulate_ATSP_as_TSP()
returns a TSP object.
filter_ATSP_as_TSP_dummies()
returns a TOUR object.
Michael Hahsler
Jonker, R. and Volgenant, T. (1983): Transforming asymmetric into symmetric traveling salesman problems, Operations Research Letters, 2, 161–163.
Other TSP:
ATSP()
,
Concorde
,
ETSP()
,
TSP()
,
TSPLIB
,
insert_dummy()
,
solve_TSP()
data("USCA50") ## set the distances from anywhere to Austin to zero which makes it an ATSP austin < which(labels(USCA50) == "Austin, TX") atsp < as.ATSP(USCA50) atsp[, austin] < 0 atsp ## reformulate as a TSP (by doubling the number of cities with dummy cities marked with *) tsp < reformulate_ATSP_as_TSP(atsp) tsp ## create tour for the TSP. You should use Concorde to find the optimal solution. # tour_tsp < solve_TSP(tsp, method = "concorde") # The standard heuristic is bad for this problem. We use it here because # Concord may not be installed. tour_tsp < solve_TSP(tsp) head(labels(tour_tsp), n = 10) tour_tsp # The tour length is Inf since it includes cheap links # from a city to its dummy city. ## get the solution for the original ATSP by filtering out the dummy cities. tour_atsp < filter_ATSP_as_TSP_dummies(tour_tsp, atsp = atsp) tour_atsp head(labels(tour_atsp), n = 10) ## This process can also be done automatically by using as_TSP = TRUE: # solve_TSP(atsp, method = "concorde", as_TSP = TRUE) ## The default heuristic can directly solve ATSPs with results close to the # optimal solution of 12715. solve_TSP(atsp, control = list(rep = 10))
data("USCA50") ## set the distances from anywhere to Austin to zero which makes it an ATSP austin < which(labels(USCA50) == "Austin, TX") atsp < as.ATSP(USCA50) atsp[, austin] < 0 atsp ## reformulate as a TSP (by doubling the number of cities with dummy cities marked with *) tsp < reformulate_ATSP_as_TSP(atsp) tsp ## create tour for the TSP. You should use Concorde to find the optimal solution. # tour_tsp < solve_TSP(tsp, method = "concorde") # The standard heuristic is bad for this problem. We use it here because # Concord may not be installed. tour_tsp < solve_TSP(tsp) head(labels(tour_tsp), n = 10) tour_tsp # The tour length is Inf since it includes cheap links # from a city to its dummy city. ## get the solution for the original ATSP by filtering out the dummy cities. tour_atsp < filter_ATSP_as_TSP_dummies(tour_tsp, atsp = atsp) tour_atsp head(labels(tour_atsp), n = 10) ## This process can also be done automatically by using as_TSP = TRUE: # solve_TSP(atsp, method = "concorde", as_TSP = TRUE) ## The default heuristic can directly solve ATSPs with results close to the # optimal solution of 12715. solve_TSP(atsp, control = list(rep = 10))
Common interface to all TSP solvers in this package.
solve_TSP(x, method = NULL, control = NULL, ...) ## S3 method for class 'TSP' solve_TSP(x, method = NULL, control = NULL, ...) ## S3 method for class 'ATSP' solve_TSP(x, method = NULL, control = NULL, as_TSP = FALSE, ...) ## S3 method for class 'ETSP' solve_TSP(x, method = NULL, control = NULL, ...)
solve_TSP(x, method = NULL, control = NULL, ...) ## S3 method for class 'TSP' solve_TSP(x, method = NULL, control = NULL, ...) ## S3 method for class 'ATSP' solve_TSP(x, method = NULL, control = NULL, as_TSP = FALSE, ...) ## S3 method for class 'ETSP' solve_TSP(x, method = NULL, control = NULL, ...)
x 
a TSP problem. 
method 
method to solve the TSP (default: "arbitrary insertion" algorithm with two_opt refinement. 
control 
a list of arguments passed on to the TSP solver selected by

... 
additional arguments are added to 
as_TSP 
should the ATSP reformulated as a TSP for the solver? 
TSP Methods
Currently the following methods are available:
"identity", "random" return a tour representing the order in the data (identity order) or a random order. [TSP, ATSP]
"nearest_insertion", "farthest_insertion", "cheapest_insertion", "arbitrary_insertion" Nearest, farthest, cheapest and arbitrary insertion algorithms for a symmetric and asymmetric TSP (Rosenkrantz et al. 1977). [TSP, ATSP]
The distances between cities are stored in a distance matrix $D$
with
elements $d(i,j)$
. All insertion algorithms start with a tour
consisting of an arbitrary city and choose in each step a city $k$
not
yet on the tour. This city is inserted into the existing tour between two
consecutive cities $i$
and $j$
, such that
$d(i,k) + d(k,j) 
d(i,j)$
is minimized. The algorithms stops when all cities are on the tour.
The nearest insertion algorithm chooses city $k$
in each step as the
city which is nearest to a city on the tour.
For farthest insertion, the city $k$
is chosen in each step as the city
which is farthest to any city on the tour.
Cheapest insertion chooses the city $k$
such that the cost of inserting
the new city (i.e., the increase in the tour's length) is minimal.
Arbitrary insertion chooses the city $k$
randomly from all cities not
yet on the tour.
Nearest and cheapest insertion tries to build the tour using cities which fit well into the partial tour constructed so far. The idea behind behind farthest insertion is to link cities far away into the tour fist to establish an outline of the whole tour early.
Additional control options:
"start" index of the first city (default: a random city).
"nn", "repetitive_nn" Nearest neighbor and repetitive nearest neighbor algorithms for symmetric and asymmetric TSPs (Rosenkrantz et al. 1977). [TSP, ATSP]
The algorithm starts with a tour containing a random city. Then the algorithm always adds to the last city on the tour the nearest not yet visited city. The algorithm stops when all cities are on the tour.
Repetitive nearest neighbor constructs a nearest neighbor tour for each city as the starting point and returns the shortest tour found.
Additional control options:
"start" index of the first city (default: a random city).
"two_opt" Two edge exchange improvement procedure (Croes 1958). [TSP, ATSP]
This is a tour refinement procedure which systematically exchanges two edges in the graph represented by the distance matrix till no improvements are possible. Exchanging two edges is equal to reversing part of the tour. The resulting tour is called 2optimal.
This method can be applied to tours created by other methods or used as its own method. In this case improvement starts with a random tour.
Additional control options:
"tour" an existing tour which should be improved. If no tour is given, a random tour is used.
"two_opt_repetitions" number of times to try two_opt with a different initial random tour (default: 1).
"concorde" Concorde algorithm (Applegate et al. 2001). [TSP, ETSP]
Concorde is an advanced exact TSP solver for symmetric TSPs
based on branchandcut.
ATSPs can be solved using reformulate_ATSP_as_TSP()
done automatically
with as_TSP = TRUE
.
The program is not included in this package and
has to be obtained and installed separately.
Additional control options:
"exe" a character string containing the path to the executable (see Concorde).
"clo" a character string containing command line options for
Concorde, e.g., control = list(clo = "B v")
. See
concorde_help()
on how to obtain a complete list of available command
line options.
"precision" an integer which controls the number of decimal
places used for the internal representation of distances in Concorde. The
values given in x
are multiplied by $10^{precision}$
before being
passed on to Concorde. Note that therefore the results produced by Concorde
(especially lower and upper bounds) need to be divided by
$10^{precision}$
(i.e., the decimal point has to be shifted
precision
placed to the left). The interface to Concorde uses
write_TSPLIB()
.
"linkern" Concorde's Chained LinKernighan heuristic (Applegate et al. 2003). [TSP, ETSP]
The LinKernighan (Lin and Kernighan 1973) heuristic uses variable $k$
edge exchanges to improve an initial tour. The program is not included in
this package and has to be obtained and installed separately (see Concorde).
Additional control options: see Concorde above.
Treatment of NA
s and infinite values in x
TSP and ATSP need to contain valid distances. NA
s are not allowed. Inf
is
allowed and can be used to model the missing edges in incomplete graphs
(i.e., the distance between the two objects is infinite) or infeasible connections.
Internally, Inf
is replaced by a large value given by $max(x) + 2 range(x)$
.
Note that the solution might still place the two objects next to each other
(e.g., if x
contains several unconnected subgraphs) which results in
a path length of Inf
. Inf
is replaced by $min(x)  2 range(x)$
and
can be used to encourage the solver to place two objects next to each other.
Parallel execution support
All heuristics can be used with the control arguments repetitions
(uses the best from that many repetitions with random starts) and
two_opt
(a logical indicating if two_opt refinement should be
performed). If several repetitions are done (this includes method
"repetitive_nn"
) then foreach is used so they can be performed
in parallel on multiple cores/machines. To enable parallel execution an
appropriate parallel backend needs to be registered (e.g., load
doParallel and register it with doParallel::registerDoParallel()
).
Solving ATSP and ETSP
Some solvers (including Concorde) cannot directly solve ATSP
directly. ATSP
can be reformulated as larger TSP
and solved
this way. For convenience, solve_TSP()
has an extra argument
as_TSP
which can be set to TRUE
to automatically solve the
ATSP
reformulated as a TSP
(see reformulate_ATSP_as_TSP()
).
Only methods "concorde" and "linkern" can solve ETSPs directly. For all other methods, ETSPs are currently converted into TSPs by creating a distance matrix and then solved.
An object of class TOUR.
Michael Hahsler
David Applegate, Robert Bixby, Vasek Chvatal, William Cook (2001): TSP cuts which do not conform to the template paradigm, Computational Combinatorial Optimization, M. Junger and D. Naddef (editors), Springer.
D. Applegate, W. Cook and A. Rohe (2003): Chained LinKernighan for Large Traveling Salesman Problems. INFORMS Journal on Computing, 15(1):82–92.
G.A. Croes (1958): A method for solving travelingsalesman problems. Operations Research, 6(6):791–812.
S. Lin and B. Kernighan (1973): An effective heuristic algorithm for the travelingsalesman problem. Operations Research, 21(2): 498–516.
D.J. Rosenkrantz, R. E. Stearns, and Philip M. Lewis II (1977): An analysis of several heuristics for the traveling salesman problem. SIAM Journal on Computing, 6(3):563–581.
Other TSP:
ATSP()
,
Concorde
,
ETSP()
,
TSP()
,
TSPLIB
,
insert_dummy()
,
reformulate_ATSP_as_TSP()
Other TOUR:
TOUR()
,
cut_tour()
,
tour_length()
## solve a simple Euclidean TSP (using the default method) etsp < ETSP(data.frame(x = runif(20), y = runif(20))) tour < solve_TSP(etsp) tour tour_length(tour) plot(etsp, tour) ## compare methods data("USCA50") USCA50 methods < c("identity", "random", "nearest_insertion", "cheapest_insertion", "farthest_insertion", "arbitrary_insertion", "nn", "repetitive_nn", "two_opt") ## calculate tours tours < lapply(methods, FUN = function(m) solve_TSP(USCA50, method = m)) names(tours) < methods ## use the external solver which has to be installed separately ## Not run: tours$concorde < solve_TSP(USCA50, method = "concorde") tours$linkern < solve_TSP(USCA50, method = "linkern") ## End(Not run) ## register a parallel backend to perform repetitions in parallel ## Not run: library(doParallel) registerDoParallel() ## End(Not run) ## add some tours using repetition and two_opt refinements tours$'nn+two_opt' < solve_TSP(USCA50, method = "nn", two_opt = TRUE) tours$'nn+rep_10' < solve_TSP(USCA50, method = "nn", rep = 10) tours$'nn+two_opt+rep_10' < solve_TSP(USCA50, method = "nn", two_opt = TRUE, rep = 10) tours$'arbitrary_insertion+two_opt' < solve_TSP(USCA50) ## show first tour tours[[1]] ## compare tour lengths opt < 14497 # obtained by Concorde tour_lengths < c(sort(sapply(tours, tour_length), decreasing = TRUE), optimal = opt) dotchart(tour_lengths / opt * 100  100, xlab = "percent excess over optimum")
## solve a simple Euclidean TSP (using the default method) etsp < ETSP(data.frame(x = runif(20), y = runif(20))) tour < solve_TSP(etsp) tour tour_length(tour) plot(etsp, tour) ## compare methods data("USCA50") USCA50 methods < c("identity", "random", "nearest_insertion", "cheapest_insertion", "farthest_insertion", "arbitrary_insertion", "nn", "repetitive_nn", "two_opt") ## calculate tours tours < lapply(methods, FUN = function(m) solve_TSP(USCA50, method = m)) names(tours) < methods ## use the external solver which has to be installed separately ## Not run: tours$concorde < solve_TSP(USCA50, method = "concorde") tours$linkern < solve_TSP(USCA50, method = "linkern") ## End(Not run) ## register a parallel backend to perform repetitions in parallel ## Not run: library(doParallel) registerDoParallel() ## End(Not run) ## add some tours using repetition and two_opt refinements tours$'nn+two_opt' < solve_TSP(USCA50, method = "nn", two_opt = TRUE) tours$'nn+rep_10' < solve_TSP(USCA50, method = "nn", rep = 10) tours$'nn+two_opt+rep_10' < solve_TSP(USCA50, method = "nn", two_opt = TRUE, rep = 10) tours$'arbitrary_insertion+two_opt' < solve_TSP(USCA50) ## show first tour tours[[1]] ## compare tour lengths opt < 14497 # obtained by Concorde tour_lengths < c(sort(sapply(tours, tour_length), decreasing = TRUE), optimal = opt) dotchart(tour_lengths / opt * 100  100, xlab = "percent excess over optimum")
Class to store the solution of a TSP. Objects of this class are returned by
TSP solvers in this package. Essentially, an object of class TOUR
is
a permutation vector containing the order of cities to visit.
TOUR(x, method = NA, tsp = NULL) as.TOUR(object) ## S3 method for class 'numeric' as.TOUR(object) ## S3 method for class 'integer' as.TOUR(object) ## S3 method for class 'TOUR' print(x, ...)
TOUR(x, method = NA, tsp = NULL) as.TOUR(object) ## S3 method for class 'numeric' as.TOUR(object) ## S3 method for class 'integer' as.TOUR(object) ## S3 method for class 'TOUR' print(x, ...)
x 
an integer permutation vector or, for the methods an object of class TOUR. 
method 
character string; method used to create the tour. 
tsp 

object 
data (an integer vector) which can be coerced to 
... 
further arguments are passed on. 
Since an object of class TOUR
is an integer vector, it can be
subsetted as an ordinary vector or coerced to an integer vector using
as.integer()
. It also contains the names of the objects as labels.
Additionally, TOUR
has the following attributes: "method"
,
"tour_length"
.
For most functions, e.g., tour_length()
or image.TSP()
, the
TSP/ATSP
object used to find the tour is still needed, since the tour
does not contain the distance information.
Michael Hahsler
Other TOUR:
cut_tour()
,
solve_TSP()
,
tour_length()
TOUR(1:10) ## calculate a tour data("USCA50") tour < solve_TSP(USCA50) tour ## get tour length directly from tour tour_length(tour) ## get permutation vector as.integer(tour) ## show labels labels(tour)
TOUR(1:10) ## calculate a tour data("USCA50") tour < solve_TSP(USCA50) tour ## get tour length directly from tour tour_length(tour) ## get permutation vector as.integer(tour) ## show labels labels(tour)
Calculate the length of a TOUR for a TSP.
tour_length(x, ...) ## S3 method for class 'TSP' tour_length(x, order, ...) ## S3 method for class 'ATSP' tour_length(x, order, ...) ## S3 method for class 'ETSP' tour_length(x, order, ...) ## S3 method for class 'TOUR' tour_length(x, tsp = NULL, ...) ## S3 method for class 'integer' tour_length(x, tsp = NULL, ...)
tour_length(x, ...) ## S3 method for class 'TSP' tour_length(x, order, ...) ## S3 method for class 'ATSP' tour_length(x, order, ...) ## S3 method for class 'ETSP' tour_length(x, order, ...) ## S3 method for class 'TOUR' tour_length(x, tsp = NULL, ...) ## S3 method for class 'integer' tour_length(x, tsp = NULL, ...)
x 
a TSP problem or a TOUR. 
... 
further arguments are currently unused. 
order 
an object of class 
tsp 
as TSP object. 
If no tsp
is specified, then the tour length stored in x
as
attribute "tour_length"
is returned. If tsp
is given then the
tour length is recalculated using the specified TSP problem.
If a distance in the tour is infinite, the result is also infinite. If the
tour contains positive and negative infinite distances then the method
returns NA
.
Michael Hahsler
Other TOUR:
TOUR()
,
cut_tour()
,
solve_TSP()
data("USCA50") ## original order tour_length(solve_TSP(USCA50, method="identity")) ## length of a manually created (random) tour tour < TOUR(sample(seq(n_of_cities(USCA50)))) tour tour_length(tour) tour_length(tour, USCA50)
data("USCA50") ## original order tour_length(solve_TSP(USCA50, method="identity")) ## length of a manually created (random) tour tour < TOUR(sample(seq(n_of_cities(USCA50)))) tour tour_length(tour) tour_length(tour, USCA50)
Constructor to create an instance of a symmetric traveling salesperson problem (TSP) and some auxiliary methods.
TSP(x, labels = NULL, method = NULL) as.TSP(x) ## S3 method for class 'dist' as.TSP(x) ## S3 method for class 'matrix' as.TSP(x) ## S3 method for class 'TSP' as.dist(m, ...) ## S3 method for class 'TSP' print(x, ...) n_of_cities(x) ## S3 method for class 'TSP' n_of_cities(x) ## S3 method for class 'TSP' labels(object, ...) ## S3 method for class 'TSP' image(x, order, col = gray.colors(64), ...)
TSP(x, labels = NULL, method = NULL) as.TSP(x) ## S3 method for class 'dist' as.TSP(x) ## S3 method for class 'matrix' as.TSP(x) ## S3 method for class 'TSP' as.dist(m, ...) ## S3 method for class 'TSP' print(x, ...) n_of_cities(x) ## S3 method for class 'TSP' n_of_cities(x) ## S3 method for class 'TSP' labels(object, ...) ## S3 method for class 'TSP' image(x, order, col = gray.colors(64), ...)
x , object

an object (currently 
labels 
optional city labels. If not given, labels are taken from

method 
optional name of the distance metric. If 
m 
a TSP object to be converted to a dist object. 
... 
further arguments are passed on. 
order 
order of cities for the image as an integer vector or an object of class TOUR. 
col 
color scheme for image. 
Objects of class TSP
are internally represented as dist
objects (use as.dist()
to get the dist
object).
Not permissible paths can be set to a distance of +Inf
. NA
s are not allowed and Inf
will lead
to the algorithm only being able to find an admissible tour, but not the best one.
TSP()
returns x
as an object of class TSP
.
n_of_cities()
returns the number of cities in x
.
labels()
returns a vector with the names of the cities in x
.
Michael Hahsler
Other TSP:
ATSP()
,
Concorde
,
ETSP()
,
TSPLIB
,
insert_dummy()
,
reformulate_ATSP_as_TSP()
,
solve_TSP()
data("iris") d < dist(iris[5]) ## create a TSP tsp < TSP(d) tsp ## use some methods n_of_cities(tsp) labels(tsp) image(tsp)
data("iris") d < dist(iris[5]) ## create a TSP tsp < TSP(d) tsp ## use some methods n_of_cities(tsp) labels(tsp) image(tsp)
Reads and writes TSPLIB format files. TSPLIB files can be used by most TSP solvers. Sample instances for the TSP in TSPLIB format are available on the TSPLIB homepage (see references).
read_TSPLIB(file, precision = 0) write_TSPLIB(x, file, precision = 6, inf = NULL, neg_inf = NULL) ## S3 method for class 'TSP' write_TSPLIB(x, file, precision = 6, inf = NULL, neg_inf = NULL) ## S3 method for class 'ATSP' write_TSPLIB(x, file, precision = 6, inf = NULL, neg_inf = NULL) ## S3 method for class 'ETSP' write_TSPLIB(x, file, precision = 6, inf = NULL, neg_inf = NULL)
read_TSPLIB(file, precision = 0) write_TSPLIB(x, file, precision = 6, inf = NULL, neg_inf = NULL) ## S3 method for class 'TSP' write_TSPLIB(x, file, precision = 6, inf = NULL, neg_inf = NULL) ## S3 method for class 'ATSP' write_TSPLIB(x, file, precision = 6, inf = NULL, neg_inf = NULL) ## S3 method for class 'ETSP' write_TSPLIB(x, file, precision = 6, inf = NULL, neg_inf = NULL)
file 
file name or a connection. 
precision 
controls the number of decimal places used to represent
distances (see details). If 
x 
an object with a TSP problem.

inf 
replacement value for 
neg_inf 
replacement value for 
In the TSPLIB format distances are represented by integer values. Therefore,
if x
contains double
values (which is normal in R) the values
given in x
are multiplied by $10^{precision}$
before coercion to
integer
. Note that therefore all results produced by programs using
the TSPLIB file as input need to be divided by $10^{precision}$
(i.e.,
the decimal point has to be shifted precision
placed to the left).
Currently only the following EDGE_WEIGHT_TYPE
s are implemented:
EXPLICIT
, EUC_2D
and EUC_3D
.
returns an object of class TSP
or
ATSP
.
Michael Hahsler
TSPLIB home page, http://comopt.ifi.uniheidelberg.de/software/TSPLIB95/
Other TSP:
ATSP()
,
Concorde
,
ETSP()
,
TSP()
,
insert_dummy()
,
reformulate_ATSP_as_TSP()
,
solve_TSP()
## Drilling problem from TSP drill < read_TSPLIB(system.file("examples/d493.tsp", package = "TSP")) drill tour < solve_TSP(drill, method = "nn", two_opt = TRUE) tour plot(drill, tour, cex=.6, col = "red", pch= 3, main = "TSPLIB: d493") ## Write and read data in TSPLIB format x < data.frame(x=runif(5), y=runif(5)) ## create TSP, ATSP and ETSP (2D) tsp < TSP(dist(x)) atsp < ATSP(dist(x)) etsp < ETSP(x[,1:2]) write_TSPLIB(tsp, file="example.tsp") #file.show("example.tsp") r < read_TSPLIB("example.tsp") r write_TSPLIB(atsp, file="example.tsp") #file.show("example.tsp") r < read_TSPLIB("example.tsp") r write_TSPLIB(etsp, file="example.tsp") #file.show("example.tsp") r < read_TSPLIB("example.tsp") r ## clean up unlink("example.tsp")
## Drilling problem from TSP drill < read_TSPLIB(system.file("examples/d493.tsp", package = "TSP")) drill tour < solve_TSP(drill, method = "nn", two_opt = TRUE) tour plot(drill, tour, cex=.6, col = "red", pch= 3, main = "TSPLIB: d493") ## Write and read data in TSPLIB format x < data.frame(x=runif(5), y=runif(5)) ## create TSP, ATSP and ETSP (2D) tsp < TSP(dist(x)) atsp < ATSP(dist(x)) etsp < ETSP(x[,1:2]) write_TSPLIB(tsp, file="example.tsp") #file.show("example.tsp") r < read_TSPLIB("example.tsp") r write_TSPLIB(atsp, file="example.tsp") #file.show("example.tsp") r < read_TSPLIB("example.tsp") r write_TSPLIB(etsp, file="example.tsp") #file.show("example.tsp") r < read_TSPLIB("example.tsp") r ## clean up unlink("example.tsp")
The USCA312
dataset contains the distances between 312 cities in the
US and Canada as an object of class TSP
. USCA50
is a subset
of USCA312
containing only the first 50 cities.
USCA312
and USCA50
are objects of class TSP
.
USCA312_GPS
is a data.frame with city name, long and lat.
The USCA312_GPS
dataset contains the location (long/lat) of the 312
cities.
Michael Hahsler
John Burkardt, CITIES – City Distance Datasets, Florida State University, Department of Scientific Computing
data("USCA312") ## calculate a tour tour < solve_TSP(USCA312) tour # Visualize the tour if package maps is installed if(require("maps")) { library(maps) data("USCA312_GPS") head(USCA312_GPS) plot((USCA312_GPS[, c("long", "lat")]), cex = .3) map("world", col = "gray", add = TRUE) polygon(USCA312_GPS[, c("long", "lat")][tour,], border = "red") }
data("USCA312") ## calculate a tour tour < solve_TSP(USCA312) tour # Visualize the tour if package maps is installed if(require("maps")) { library(maps) data("USCA312_GPS") head(USCA312_GPS) plot((USCA312_GPS[, c("long", "lat")]), cex = .3) map("world", col = "gray", add = TRUE) polygon(USCA312_GPS[, c("long", "lat")][tour,], border = "red") }