gor (version 2.0)

compute_path_distance: Compute the distance of a TSP path

Description

It computes the distance covered by a path in a Traveling Salesman Problem

Usage

compute_path_distance(h, d)

Value

The path distance $$d(\{v_1,...,v_n\}) = \sum_{j=1}^{n-1} d(v_j,v_{j + 1}).$$

Arguments

h

A path specified by a vertex sequence

d

Distance matrix to use

Author

Cesar Asensio

Details

This function simply add the distances in a distance matrix indicated by a vertex sequence defining a path. It takes into account that, in a path, the last vertex is not joined to the first one by an edge, unlike compute_tour_distance.

See Also

build_tour_nn nearest neighbor heuristic with a single starting point, build_tour_nn_best repeats the previous algorithm with all possible starting points, compute_distance_matrix computes a distance matrix, compute_tour_distance computes tour distances, plot_tour plots a tour.

Examples

set.seed(1)
n <- 25
z <- cbind(runif(n,min=1,max=10),runif(n,min=1,max=10))
d <- compute_distance_matrix(z)
h <- sample(1:n)              # A random tour
compute_path_distance(h, d)   # 107.246
compute_tour_distance(h, d) - compute_path_distance(h, d) - d[h[1], h[n]]