build_tour_nn {gor}

Building a tour for a TSP using the nearest neighbor heuristic

Description

Nearest neighbor heuristic tour-building algorithm for the Traveling Salesperson Problem

Usage

build_tour_nn(d, n, v0)

Arguments

d

Distance matrix of the TSP.

n

Number of vertices of the TSP complete graph.

v0

Starting vertex. Valid values are integers between 1 and n.

Details

Starting from a vertex, the algorithm takes its nearest neighbor and incorporates it to the tour, repeating until the tour is complete. The result is dependent of the initial vertex. This algorithm is very efficient but its output can be very far from the minimum.

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_best repeats this algorithm with all possible starting points, compute_tour_distance computes tour distances, compute_distance_matrix computes a distance matrix, plot_tour plots a tour, build_tour_greedy constructs a tour using the greedy heuristic.

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_nn(d, n, 1)
b$distance    # Distance 50
plot_tour(z,b)
b <- build_tour_nn(d, n, 5)
b$distance    # Distance 52.38
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_nn(d, n, 1)
b$distance    # Distance 46.4088
plot_tour(z,b)
b <- build_tour_nn(d, n, 9)
b$distance    # Distance 36.7417
plot_tour(z,b)