compute_gain_transp {gor} | R Documentation |
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)
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. |
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.
Value
The gain in distance after performing transposition tr in tour C with distance matrix d.
Author(s)
Cesar Asensio
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