example2_tsp_sann {roptim}

Example 2: Solve Travelling Salesman Problem (TSP) using SANN

Description

Solve Travelling Salesman Problem (TSP) using SANN.

Usage

example2_tsp_sann(distmat, x)

Arguments

distmat

a distance matrix for storing all pair of locations.

x

initial route.

Examples

## 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)