insert_dummy: Insert dummy cities into a distance matrix

In TSP: Traveling Salesperson Problem (TSP)

Insert dummy cities into a distance matrix

Description

Inserts dummy cities into a TSP problem. A dummy city has the same, constant distance (0) to all other cities and is infinitely far from other dummy cities. A dummy city can be used to transform a shortest Hamiltonian path problem (i.e., finding an optimal linear order) into a shortest Hamiltonian cycle problem which can be solved by a TSP solvers (Garfinkel 1985).

Usage

insert_dummy(x, n = 1, const = 0, inf = Inf, label = "dummy")

## S3 method for class 'TSP'
insert_dummy(x, n = 1, const = 0, inf = Inf, label = "dummy")

## S3 method for class 'ATSP'
insert_dummy(x, n = 1, const = 0, inf = Inf, label = "dummy")

## S3 method for class 'ETSP'
insert_dummy(x, n = 1, const = 0, inf = Inf, label = "dummy")

Arguments

x	an object with a TSP problem.
n	number of dummy cities.
const	distance of the dummy cities to all other cities.
inf	distance between dummy cities.
label	labels for the dummy cities. If only one label is given, it is reused for all dummy cities.

Details

Several dummy cities can be used together with a TSP solvers to perform rearrangement clustering (Climer and Zhang 2006).

The dummy cities are inserted after the other cities in x.

A const of 0 is guaranteed to work if the TSP finds the optimal solution. For heuristics returning suboptimal solutions, a higher const (e.g., 2 * max(x)) might provide better results.

Value

returns an object of the same class as x.

Author(s)

Michael Hahsler

References

Sharlee Climer, Weixiong Zhang (2006): Rearrangement Clustering: Pitfalls, Remedies, and Applications, Journal of Machine Learning Research 7(Jun), pp. 919–943.

R.S. Garfinkel (1985): Motivation and modelling (chapter 2). In: E. L. Lawler, J. K. Lenstra, A.H.G. Rinnooy Kan, D. B. Shmoys (eds.) The traveling salesman problem - A guided tour of combinatorial optimization, Wiley & Sons.

See Also

Other TSP: ATSP(), Concorde, ETSP(), TSPLIB, TSP(), reformulate_ATSP_as_TSP(), solve_TSP()

Examples

## Example 1: Find a short Hamiltonian path
set.seed(1000)
x <- data.frame(x = runif(20), y = runif(20), row.names = LETTERS[1:20])

tsp <- TSP(dist(x))

## add a dummy city to cut the tour into a path
tsp <- insert_dummy(tsp, label = "cut")
tour <- solve_TSP(tsp)
tour

plot(x)
lines(x[cut_tour(tour, cut = "cut"),])


## Example 2: Rearrangement clustering of the iris dataset
set.seed(1000)
data("iris")
tsp <- TSP(dist(iris[-5]))

## insert 2 dummy cities to creates 2 clusters
tsp_dummy <- insert_dummy(tsp, n = 3, label = "boundary")

## get a solution for the TSP
tour <- solve_TSP(tsp_dummy)

## plot the reordered distance matrix with the dummy cities as lines separating
## the clusters
image(tsp_dummy, tour)
abline(h = which(labels(tour)=="boundary"), col = "red")
abline(v = which(labels(tour)=="boundary"), col = "red")

## plot the original data with paths connecting the points in each cluster
plot(iris[,c(2,3)], col = iris[,5])
paths <- cut_tour(tour, cut = "boundary")
for(p in paths) lines(iris[p, c(2,3)])

## Note: The clustering is not perfect!

TSP documentation built on April 4, 2023, 5:13 p.m.