insert_dummy

0th

Percentile

Insert dummy cities into a distance matrix

Inserts dummy cities into objects of class TSP or ATSP. 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). Several dummy cities can be used together with a TSP solvers to perform rearrangement clustering (Climer and Zhang 2006).

Keywords
manip
Usage
insert_dummy(x, n = 1, const = 0, inf = Inf, label =  "dummy")
Arguments
x
an object of class TSP or ATSP.
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

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.

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

TSP, ATSP

Aliases
  • insert_dummy
Examples
## make runs comparable
set.seed(4444)

data("iris")
tsp <- TSP(dist(iris[-5]))

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

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

## plot the distance matrix
image(tsp_dummy, tour)

## draw lines where the dummy cities are located
abline(h = which(labels(tour)=="boundary"), col = "red")
abline(v = which(labels(tour)=="boundary"), col = "red")
Documentation reproduced from package TSP, version 1.1-4, License: GPL-3

Community examples

Looks like there are no examples yet.