TSP solver interface
Common interface to all TSP solvers in this package.
solve_TSP(x, method = NULL, control = NULL, ...)
- the TSP given as an object of class
- method to solve the TSP (default: arbitrary insertion algorithm with two_opt refinement.
- a list of arguments passed on to the TSP solver
- additional arguments are added to
NAs and infinite values in
ATSP contain distances and
NAs are not allowed.
Inf is allowed and can be used to model the missing edges in
(i.e., the distance between the two objects is infinite).
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
x contains several unconnected subgraphs)
which results in a path length of
All heuristics can be used with the control arguments
(uses the best from that many repetitions with random starts)
two_opt (a logical indicating if two_opt refinement should be
performed). If several repetitions are done (this includes method
ETSP are currently solved by first calculating a dissimilarity matrix (a
TSP). Only concorde and linkern can solve the TSP directly on the
Currently the following methods are available: [object Object],[object Object],[object Object],[object Object],[object Object],[object Object]
- An object of class
Concorde home page,
David Appletgate, 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.
## 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 tours$concorde <- solve_TSP(USCA50, method = "concorde") tours$linkern <- solve_TSP(USCA50, method = "linkern") ## register a parallel backend to perform repetitions in parallel library(doParallel) registerDoParallel() ## 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[] ## 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")