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).
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.
Author(s)
Michael Hahsler
References
Sharlee Climer, Weixiong Zhang (2006): Rearrangement Clustering: Pitfalls,
Remedies, and Applications, Journal of Machine Learning Research7(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
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")