Number of 2-opt Moves

To find the number of 2-opt possible moves, we need to consider that the edges involved in the node must have different nodes. For each of the \(n\) edges of a cycle covering all nodes, only \(n-3\) edges have this property, as we need to exclude the edge itself and the two edges sharing a node with the considered edge. This leads to \(n(n-3)\) possible moves.

But if the problem is symmetric, each 2-opt move has another move yielding the same effect. For the plot above, the \((4, 6)\) move is equivalent to the \((3, 7)\) move. Therefore, the total number of 2-opt moves in a symmetric TSP instance of size \(n\) is \(n(n-3)/2\).

Generating 2-opt Moves

The function move_2opt_table() generates all 2-opt moves for a symmetric TSP in the following way:

• We generate the edges data frame with the positions of node edges (i. j) of a solution.
• For each edge, I find all edges e2 with no common nodes for each edge e1. Then, I obtain the i element as the second node of the first edge, and j as the first node of the second edge.
• Finally, I choose moves with i > j to pick those moves with sequences to revert not including the first node.

move_2opt_table <- function(n){
  
  edges <- data.frame(edge = 1:n, i = 1:n, j = c(2:n, 1))
  e1 <- rep(1:n, each = n-3)
  e2 <- c(sapply(1:n, \(i) ((i+1):(i+n-3) %% n) + 1))
  
  moves <- data.frame(e1 = e1, e2 = e2, i = e1+1, j = e2)
  
  moves <- moves[which(moves$i < moves$j), 3:4]
  
  return(moves)
}

The function is encoded in R base, so there is no additional package to use it.

Here is the result for n = 7…

move_2opt_table(7)

##    i j
## 1  2 3
## 2  2 4
## 3  2 5
## 4  2 6
## 5  3 4
## 6  3 5
## 7  3 6
## 8  3 7
## 9  4 5
## 10 4 6
## 11 4 7
## 13 5 6
## 14 5 7
## 17 6 7

… and the result for n = 8:

move_2opt_table(8)

##    i j
## 1  2 3
## 2  2 4
## 3  2 5
## 4  2 6
## 5  2 7
## 6  3 4
## 7  3 5
## 8  3 6
## 9  3 7
## 10 3 8
## 11 4 5
## 12 4 6
## 13 4 7
## 14 4 8
## 16 5 6
## 17 5 7
## 18 5 8
## 21 6 7
## 22 6 8
## 26 7 8

Obtanining 2-opt Moves

The moves selected by move_2opt_table() reverse sequences that do not contain the first node. This makes the coding of move_2opt() simpler, as we need to care only for the case where \(j\) is equal to the \(n\)-eth node.

move_2opt <- function(vec, i, j, n){
  if(j == n)
    v <- vec[c(1:(i-1), j:i)]
  else
    v <- vec[c(1:(i-1), j:i, (j+1):n)]
  return(v)
}

Here is the move \((4,6)\) of the solution \(\{1,2,3,4,5,6,7,8\}\), presented in the figure above.

move_2opt(1:8, 4, 6, 8)

## [1] 1 2 3 6 5 4 7 8

We can use the purrr::pmap() function to iterate along the table of 2-opt moves and obtain all solutions as a list.

n <- 6
moves_6 <- move_2opt_table(n)
pmap(moves_6, ~  move_2opt(vec = 1:n, .x, .y, n = n))

## [[1]]
## [1] 1 3 2 4 5 6
## 
## [[2]]
## [1] 1 4 3 2 5 6
## 
## [[3]]
## [1] 1 5 4 3 2 6
## 
## [[4]]
## [1] 1 2 4 3 5 6
## 
## [[5]]
## [1] 1 2 5 4 3 6
## 
## [[6]]
## [1] 1 2 6 5 4 3
## 
## [[7]]
## [1] 1 2 3 5 4 6
## 
## [[8]]
## [1] 1 2 3 6 5 4
## 
## [[9]]
## [1] 1 2 3 4 6 5

In the following figure, I am presenting the twenty 2-opt moves for a TSP instance of size eight.

Value of Solution for 2-opt Moves

In a local search algorithm like simulated annealing or tabu search, we need to perform many evaluations of the total distance of a solution, so it is relevant to calculate them in a fast way. Let’s illustrate how to do this with a distance matrix D of a TSP instance of size n = 8.

points <- function(n){
  df <- data.frame(x = sample(1:(2*n), n),
                   y = sample(1:(2*n), n))
  return(df)
}

n <- 8
set.seed(1111)
D <- dist(points(n), method = "manhattan", upper = TRUE) |> as.matrix()

The TSP() function calculates the value of a solution in a fast way, because we are not iterating to obtain edge values.

TSP <- function(v, sol, n) sum(v[sol[c(1:(n-1), 1)] + (sol[c(2:n, n)] - 1)*n])

If we look again at the first picture, we observe that when we perform a 2-opt move, we remove two edges and add two new ones. So substracting and adding edge distances can be used to calculate objective function faster.

TSP_2opt <- function(D, fit, i, j, n){
  if(j == n)
    new_sol <- fit + D[i-1, j] + D[i, 1] - D[i-1, i] - D[j, 1]
  else
    new_sol <- fit +  D[i-1, j] + D[i, j+1] - D[i-1, i] - D[j, j+1]
  
  return(new_sol)
}

Let’s check if the function works. We start calculating the total distance of a solution sol.

sol <- 1:n
fit <- TSP(as.numeric(D), sol, 8)
fit

## [1] 84

Now we generate a new solution with the \((3,6)\) move, and compare the result obtained in the two ways.

new_sol <- move_2opt(1:n, 3, 6, 8)
TSP(as.numeric(D), new_sol, 8) 

## [1] 92

TSP_2opt(D, fit, 3, 6, 8)

## [1] 92

We observe that both functions lead to the same result.

Exploring a 2-opt Neighbourhood

We can use purrr:pmap() on the table of 2-opt moves to evaluate the value of cycle of each move, and find the best move arranging the table.

moves |>
  mutate(sol = pmap_dbl(moves, ~ TSP_2opt(D, fit, .x, .y, n))) |>
  arrange(sol, i)

##    i j sol
## 1  4 6  68
## 2  5 7  80
## 3  7 8  80
## 4  2 4  82
## 5  2 3  84
## 6  5 6  84
## 7  4 5  86
## 8  2 6  88
## 9  4 7  88
## 10 4 8  88
## 11 5 8  88
## 12 2 7  90
## 13 3 4  90
## 14 3 5  92
## 15 3 6  92
## 16 6 8  92
## 17 2 5  96
## 18 3 8 100
## 19 6 7 102
## 20 3 7 106

In this case, we observe that the best move for this solution is \((4,6)\), which reduces total cycle value from 92 to 68.

Session Info

## R version 4.4.0 (2024-04-24)
## Platform: x86_64-pc-linux-gnu
## Running under: Linux Mint 21.1
## 
## Matrix products: default
## BLAS:   /usr/lib/x86_64-linux-gnu/blas/libblas.so.3.10.0 
## LAPACK: /usr/lib/x86_64-linux-gnu/lapack/liblapack.so.3.10.0
## 
## locale:
##  [1] LC_CTYPE=es_ES.UTF-8       LC_NUMERIC=C              
##  [3] LC_TIME=es_ES.UTF-8        LC_COLLATE=es_ES.UTF-8    
##  [5] LC_MONETARY=es_ES.UTF-8    LC_MESSAGES=es_ES.UTF-8   
##  [7] LC_PAPER=es_ES.UTF-8       LC_NAME=C                 
##  [9] LC_ADDRESS=C               LC_TELEPHONE=C            
## [11] LC_MEASUREMENT=es_ES.UTF-8 LC_IDENTIFICATION=C       
## 
## time zone: Europe/Madrid
## tzcode source: system (glibc)
## 
## attached base packages:
## [1] stats     graphics  grDevices utils     datasets  methods   base     
## 
## other attached packages:
## [1] patchwork_1.2.0 gridExtra_2.3   ggraph_2.2.1    ggplot2_3.5.1  
## [5] tidygraph_1.3.1 purrr_1.0.2    
## 
## loaded via a namespace (and not attached):
##  [1] viridis_0.6.5      sass_0.4.9         utf8_1.2.4         generics_0.1.3    
##  [5] tidyr_1.3.1        blogdown_1.19      digest_0.6.35      magrittr_2.0.3    
##  [9] evaluate_0.23      grid_4.4.0         bookdown_0.39      fastmap_1.1.1     
## [13] jsonlite_1.8.8     ggrepel_0.9.5      fansi_1.0.6        viridisLite_0.4.2 
## [17] scales_1.3.0       tweenr_2.0.3       jquerylib_0.1.4    cli_3.6.2         
## [21] graphlayouts_1.1.1 rlang_1.1.3        polyclip_1.10-6    munsell_0.5.1     
## [25] withr_3.0.0        cachem_1.0.8       yaml_2.3.8         tools_4.4.0       
## [29] memoise_2.0.1      dplyr_1.1.4        colorspace_2.1-0   vctrs_0.6.5       
## [33] R6_2.5.1           lifecycle_1.0.4    MASS_7.3-60        pkgconfig_2.0.3   
## [37] pillar_1.9.0       bslib_0.7.0        gtable_0.3.5       glue_1.7.0        
## [41] Rcpp_1.0.12        ggforce_0.4.2      highr_0.10         xfun_0.43         
## [45] tibble_3.2.1       tidyselect_1.2.1   rstudioapi_0.16.0  knitr_1.46        
## [49] farver_2.1.1       htmltools_0.5.8.1  igraph_2.0.3       labeling_0.4.3    
## [53] rmarkdown_2.26     compiler_4.4.0