TSP (version 1.1-4)

solve_TSP: TSP solver interface

Description

Common interface to all TSP solvers in this package.

Usage

solve_TSP(x, method = NULL, control = NULL, ...)

Arguments

x
the TSP given as an object of class TSP, ATSP or ETSP.
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 method.
...
additional arguments are added to control.

Value

  • An object of class TOUR.

Details

Treatment of NAs and infinite values in x: TSP and ATSP contain distances and NAs 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). 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. 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 registerDoParallel()).

ETSP are currently solved by first calculating a dissimilarity matrix (a TSP). Only concorde and linkern can solve the TSP directly on the ETSP.

Currently the following methods are available: [object Object],[object Object],[object Object],[object Object],[object Object],[object Object]

References

Concorde home page, http://www.tsp.gatech.edu/concorde/

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.

See Also

TOUR, TSP, ATSP, write_TSPLIB, Concorde.

Examples

Run this code
## 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[[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")

Run the code above in your browser using DataCamp Workspace