insert_dummy: Insert dummy cities into a distance matrix

Description

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).

Usage

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

Arguments

an object of class TSP or ATSP.

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.

Examples

Run this code

## 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")

## print the results (NAs are the dummy cities)
iris[tour, "Species"]