build_tour_2tree {gor} | R Documentation |
Double-tree heuristic for TSP
Description
Double-tree heuristic tour-building algorithm for the Traveling Salesperson Problem
Usage
build_tour_2tree(d, n, v0 = 1)
Arguments
d |
Distance matrix defining the TSP instance |
n |
Number of cities to consider with respect to the distance matrix |
v0 |
Initial vertex to find the eulerian walk; it defaults to 1. |
Details
The double-tree heuristic is a 2-factor approximation algorithm which begins by forming a minimum distance spanning tree, then it forms the double-tree by doubling each edge of the spanning tree. The double tree is Eulerian, so an Eulerian walk can be computed, which gives a well-defined order of visiting the cities of the problem, thereby yielding the tour.
In practice, this algorithm performs poorly when compared with another simple heuristics such as nearest-neighbor or insertion methods.
Value
A list with two components: $tour contains a permutation of the 1:n sequence representing the tour constructed by the algorithm, and $distance contains the value of the distance covered by the tour.
Author(s)
Cesar Asensio
See Also
build_tour_nn uses the nearest heighbor heuristic, build_tour_nn_best repeats the previous algorithm with all possible starting points, compute_tour_distance computes tour distances, compute_distance_matrix computes a distance matrix, plot_tour plots a tour, find_euler finds an Eulerian walk.
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.86
plot_tour(z,b)
## 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.63
plot_tour(z,b)