gor (version 2.0)

build_tour_greedy: Building a tour for a TSP using the greedy heuristic

Description

Greedy heuristic tour-building algorithm for the Traveling Salesperson Problem

Usage

build_tour_greedy(d, n)

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.

Arguments

d

Distance matrix of the TSP.

n

Number of vertices of the TSP complete graph.

Author

Cesar Asensio

Details

The greedy heuristic begins by sorting the edges by increasing distance. The tour is constructed by adding an edge under the condition that the final tour is a connected spanning cycle.

See Also

build_tour_nn uses the nearest neighbor 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, build_tour_2tree constructs a tour using the double tree 2-factor approximation algorithm.

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_greedy(d, n)
b$distance    # Distance 50
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_greedy(d, n)
b$distance    # Distance 36.075
plot_tour(z,b)