build_tour_2tree {gor}

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)