solve_TSP | R Documentation |
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, ...)
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 2-optimal.
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 branch-and-cut.
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 Lin-Kernighan heuristic (Applegate et al. 2003). [TSP, ETSP]
The Lin-Kernighan (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 unfeasable 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 Lin-Kernighan for Large Traveling Salesman Problems. INFORMS Journal on Computing, 15(1):82–92.
G.A. Croes (1958): A method for solving traveling-salesman problems. Operations Research, 6(6):791–812.
S. Lin and B. Kernighan (1973): An effective heuristic algorithm for the traveling-salesman 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()
,
TSPLIB
,
TSP()
,
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")
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.