build_tour_nn_best: Build a tour for a TSP using the best nearest neighbor...

In gor: Algorithms for the Subject Graphs and Network Optimization

Build a tour for a TSP using the best nearest neighbor heuristic

Description

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

Usage

build_tour_nn_best(d, n)

Arguments

d	Distance matrix of the TSP.
n	Number of vertices of the TSP complete graph.

Details

It applies the nearest neighbor heuristic with all possible starting vertices, retaining the best tour returned by build_tour_nn.

Value

A list with four components: $tour contains a permutation of the 1:n sequence representing the tour constructed by the algorithm, $distance contains the value of the distance covered by the tour, $start contains the better starting vertex found, and $Lall contains the distances found by starting from each vertex.

Author(s)

Cesar Asensio

See Also

build_tour_nn nearest neighbor heuristic with a single starting point, compute_tour_distance computes tour distances, compute_distance_matrix computes a distance matrix, plot_tour plots a tour.

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_best(d, n)
b$distance    # Distance 48.6055
b$start       # Vertex 12
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_best(d, n)
b$distance    # Distance 36.075
b$start       # Vertex 13
plot_tour(z,b)

gor documentation built on May 4, 2023, 1:06 a.m.