example2_tsp_sann | R Documentation |
Solve Travelling Salesman Problem (TSP) using SANN.
example2_tsp_sann(distmat, x)
distmat |
a distance matrix for storing all pair of locations. |
x |
initial route. |
## Combinatorial optimization: Traveling salesman problem library(stats) # normally loaded eurodistmat <- as.matrix(eurodist) distance <- function(sq) { # Target function sq2 <- embed(sq, 2) sum(eurodistmat[cbind(sq2[,2], sq2[,1])]) } genseq <- function(sq) { # Generate new candidate sequence idx <- seq(2, NROW(eurodistmat)-1) changepoints <- sample(idx, size = 2, replace = FALSE) tmp <- sq[changepoints[1]] sq[changepoints[1]] <- sq[changepoints[2]] sq[changepoints[2]] <- tmp sq } sq <- c(1:nrow(eurodistmat), 1) # Initial sequence: alphabetic distance(sq) # rotate for conventional orientation loc <- -cmdscale(eurodist, add = TRUE)$points x <- loc[,1]; y <- loc[,2] s <- seq_len(nrow(eurodistmat)) tspinit <- loc[sq,] plot(x, y, type = "n", asp = 1, xlab = "", ylab = "", main = "initial solution of traveling salesman problem", axes = FALSE) arrows(tspinit[s,1], tspinit[s,2], tspinit[s+1,1], tspinit[s+1,2], angle = 10, col = "green") text(x, y, labels(eurodist), cex = 0.8) ## The original R optimization: ## set.seed(123) # chosen to get a good soln relatively quickly ## res <- optim(sq, distance, genseq, method = "SANN", ## control = list(maxit = 30000, temp = 2000, trace = TRUE, ## REPORT = 500)) ## res # Near optimum distance around 12842 ## corresponding C++ implementation: set.seed(4) # chosen to get a good soln relatively quickly res <- example2_tsp_sann(eurodistmat, sq) tspres <- loc[res$par,] plot(x, y, type = "n", asp = 1, xlab = "", ylab = "", main = "optim() 'solving' traveling salesman problem", axes = FALSE) arrows(tspres[s,1], tspres[s,2], tspres[s+1,1], tspres[s+1,2], angle = 10, col = "red") text(x, y, labels(eurodist), cex = 0.8)
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.