# example2_tsp_sann: Example 2: Solve Travelling Salesman Problem (TSP) using SANN In roptim: General Purpose Optimization in R using C++

 example2_tsp_sann R Documentation

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

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

roptim documentation built on Aug. 6, 2022, 5:08 p.m.