## 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)
## manually run a construction followed by an improvement heuristic by
## calling solve_TSP() twice.
tour_constr <- solve_TSP(etsp, method = "nn")
tour_constr
tour_improved <- solve_TSP(etsp, method = "sa", tour = tour_constr)
tour_improved
## chain improvement heuristics: 2-opt, then Or-opt, then 3-opt
tour_2 <- solve_TSP(etsp, method = "two_opt", tour = tour_constr)
tour_or <- solve_TSP(etsp, method = "or_opt", tour = tour_2)
tour_3 <- solve_TSP(etsp, method = "three_opt", tour = tour_or)
c(nn = tour_length(tour_constr), two_opt = tour_length(tour_2),
or_opt = tour_length(tour_or), three_opt = tour_length(tour_3))
## compare methods
data("USCA50")
USCA50
methods <- c("identity", "random", "nearest_insertion",
"cheapest_insertion", "farthest_insertion", "arbitrary_insertion",
"nn", "repetitive_nn", "two_opt", "or_opt", "three_opt", "sa")
## 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
if (FALSE) {
tours$concorde <- solve_TSP(USCA50, method = "concorde")
tours$linkern <- solve_TSP(USCA50, method = "linkern")
}
## register a parallel backend to perform repetitions in parallel
if (FALSE) {
library(doParallel)
registerDoParallel()
}
## add some tours using repetition and two_opt refinements
tours$'nn+two_opt' <- solve_TSP(USCA50, method = "nn", opt = "two")
tours$'nn+two_opt+or_opt' <- solve_TSP(USCA50, method = "nn", opt = "two+or")
tours$'nn+rep_10' <- solve_TSP(USCA50, method = "nn", rep = 10)
tours$'nn+two_opt+rep_10' <- solve_TSP(USCA50, method = "nn", opt = "two", 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 <- sort(sapply(tours, tour_length), decreasing = TRUE)
dotchart(tour_lengths / opt * 100 - 100, xlab = "percent excess over optimum")
abline(v = 0, col = "red")
Run the code above in your browser using DataLab