improve_tour_LinKer {gor}

Tour improving for a TSP using a poor version of the Lin-Kernighan heuristic

Description

Lin-Kernighan heuristic tour-improving algorithm for the Traveling Salesperson Problem using fixed 2-opt instead of variable k-opt exchanges.

Usage

improve_tour_LinKer(d, n, C, try = 5)

Arguments

d

Distance matrix of the TSP.

n

Number of vertices of the TSP complete graph.

C

Starting tour to be improved.

try

Number of tries before quitting.

Details

It applies a version of the core Lin-Kernighan algorithm to a starting tour of a TSP instance until no further improvement can be found. The tour thus improved is a local minimum.

The Lin-Kernighan algorithm implemented here is based on the core routine described in the reference below. It is provided here as an example of a local search routine which can be embedded in larger search strategies. However, instead of using variable k-opt moves to improve the tour, it uses 2-exhanges only, which is far easier to program. Tours improved with this technique are of course 2-opt.

The TSP library provides an interface to the Lin-Kernighan algorithm with all its available improvements in the external program Concorde, which should be installed separately.

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

Hromkovic Algorithmics for Hard Problems (2004)

See Also

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 48)
m <- 10   # 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)
b <- build_tour_2tree(d, n)
b$distance    # Distance 57.868
bi <- improve_tour_LinKer(d, n, b$tour)
bi$distance   # Distance 48 (optimum)
plot_tour(z,b)
plot_tour(z,bi)

## Random points
set.seed(1)
n <- 25
z <- cbind(runif(n,min=1,max=10),runif(n,min=1,max=10))
d <- compute_distance_matrix(z)
b <- build_tour_2tree(d, n)
b$distance    # Distance 48.639
bi <- improve_tour_LinKer(d, n, b$tour)
bi$distance   # Distance 37.351 (2-opt)
plot_tour(z,b)
plot_tour(z,bi)