improve_tour_2opt {gor}

Tour improving for a TSP using the 2-opt heuristic

Description

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

Usage

improve_tour_2opt(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 2-opt algorithm to a starting tour of a TSP instance until no further improvement can be found. The tour thus improved is a 2-opt local minimum.

The 2-opt algorithm consists of applying all possible 2-interchanges on the starting tour. Informally, a 2-interchange is the operation of cutting the tour in two pieces (by removing two nonincident edges) and gluing the pieces together to form a new tour by interchanging the endpoints.

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_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_2opt(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_2opt(d, n, b$tour)
bi$distance   # Distance 37.351
plot_tour(z,b)
plot_tour(z,bi)