gor (version 2.0)

search_tour_chain2opt: Chained 2-opt search with multiple, random starting tours

Description

Random heuristic algorithm for TSP which performs chained 2-opt local search with multiple, random starting tours.

Usage

search_tour_chain2opt(
  d,
  n,
  Nit,
  Nper,
  log = FALSE,
  plot.best = FALSE,
  cities = NA,
  ...
)

Value

A list with two components: $tour contains a permutation of the 1:n sequence representing the tour constructed by the algorithm, $distance contains the value of the distance covered by the tour.

Arguments

d

Distance matrix of the TSP instance.

n

Number of vertices of the TSP complete graph.

Nit

Number of iterations of the algorithm, see details.

Nper

Number of chained perturbations of 2-opt minima, see details.

log

Boolean: Whether the algorithm should record the distances of the tours it finds during execution. It defaults to FALSE.

plot.best

Boolean to plot each new best tour as the algorithm finds it. Parameter "cities" is needed. It defaults to FALSE.

cities

Locations of the cities of the problem, given as a \(n\times2\) matrix. It is used only for plotting, that is, when parameter "plot.best" is TRUE.

...

Parameters to pass on the plot_tour routine.

Author

Cesar Asensio

Details

Chained local search consists of starting with a random tour, improving it using 2-opt, and then perturb it using a random 4-exchange. The result is 2-optimized again, and then 4-exchanged... This sequence of chained 2-optimizations/perturbations is repeated Nper times for each random starting tour. The entire process is repeated Nit times, drawing a fresh random tour each iteration.

The purpose of supplement the deterministic 2-opt algorithm with random additions (random starting point and random 4-exchange) is escaping from the 2-opt local minima. Of course, more iterations and more perturbations might lower the result, but recall that no random algorithm can guarantee to find the optimum in a reasonable amount of time.

This technique is most often applied in conjunction with the Lin-Kernighan local search heuristic.

It should be warned that this algorithm calls Nper*Nit times the routine improve_tour_2opt, and thus it is not especially efficient.

References

Cook et al. Combinatorial Optimization (1998)

See Also

perturb_tour_4exc transforms a tour using a random 4-exchange, improve_tour_2opt improves a tour using the 2-opt algorithm, improve_tour_3opt improves a tour using the 3-opt algorithm, build_tour_nn_best nearest neighbor heuristic, build_tour_2tree double-tree heuristic, compute_tour_distance computes tour distances, compute_distance_matrix computes a distance matrix, plot_tour plots a tour.

Examples

## Regular example with obvious solution (minimum distance 32)
m <- 6   # Generate some points in the plane
z <- cbind(c(rep(0,m), rep(2,m), rep(5,m), rep(7,m)), rep(seq(0,m-1),4))
n <- nrow(z)
d <- compute_distance_matrix(z)
bc <- search_tour_chain2opt(d, n, 5, 3)
bc     # Distance 48
plot_tour(z,bc)

## Random points
set.seed(1)
n <- 15
z <- cbind(runif(n,min=1,max=10),runif(n,min=1,max=10))
d <- compute_distance_matrix(z)
bc <- search_tour_chain2opt(d, n, 5, 3)
bc     # Distance 32.48669
plot_tour(z,bc)