improve_tour_3opt {gor}

Tour improving for a TSP using the 3-opt heuristic

Description

3-opt heuristic tour-improving algorithm for the Traveling Salesperson Problem

Usage

improve_tour_3opt(d, n, C)

Arguments

d

Distance matrix of the TSP.

n

Number of vertices of the TSP complete graph.

C

Starting tour to be improved.

Details

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

The 3-opt algorithm consists of applying all possible 3-interchanges on the starting tour. A 3-interchange removes three non-indicent edges from the tour, leaving three pieces, and combine them to form a new tour by interchanging the endpoints in all possible ways and gluing them together by adding the missing edges.

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

See Also

improve_tour_2opt improves a tour using the 2-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)
b <- build_tour_2tree(d, n)
b$distance    # Distance 38.43328
bi <- improve_tour_3opt(d, n, b$tour)
bi$distance   # Distance 32 (optimum)
plot_tour(z,b)
plot_tour(z,bi)

## 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)
b <- build_tour_2tree(d, n)
b$distance    # Distance 45.788
bi <- improve_tour_3opt(d, n, b$tour)
bi$distance   # Distance 32.48669
plot_tour(z,b)
plot_tour(z,bi)