gor (version 2.0)

compute_gain_transp: Distance gain when transposing two cities in a tour

Description

Distance gain when two cities in a TSP tour are interchanged, that is, the neighbors of the first become the neighbors of the second and vice versa. It is used to detect favorable moves in a Lin-Kernighan-based routine for the TSP.

Usage

compute_gain_transp(C, tr, d)

Value

The gain in distance after performing transposition tr in tour C with distance matrix d.

Arguments

C

Tour represented as a non-repeated vertex sequence. Equivalently, a permutation of the sequence from 1 to length(C).

tr

Transposition, represented as a pair of indices between 1 and length(C).

d

Distance matrix.

Author

Cesar Asensio

Details

It computes the gain in distance when interchanging two cities in a tour. The transformation is akin to a 2-interchange; in fact, if the transposed vertices are neighbors in the tour or share a common neighbor, the transposition is a 2-interchange. If the transposed vertices in the tour do not share any neighbors, then the transposition is a pair of 2-interchanges.

This gain is used in improve_tour_LinKer, where the transposition neighborhood is used instead of the variable k-opt neighborhood for simplicity.

See Also

improve_tour_LinKer, a where this function is used.

Examples

set.seed(1)
n <- 25
z <- cbind(runif(n,min=1,max=10),runif(n,min=1,max=10))
d <- compute_distance_matrix(z)
compute_gain_transp(sample(n),c(4,23),d)  # -6.661
compute_gain_transp(sample(n),c(17,3),d)  #  4.698