search_tour_chain2opt {gor}

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)

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.

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.

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.

Author(s)

Cesar Asensio

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)