# solve_TSP

##### TSP solver interface

Common interface to all TSP solvers in this package.

- Keywords
- optimize

##### Usage

`solve_TSP(x, method = NULL, control = NULL, ...)`

##### Arguments

- x
- the TSP given as an object of class
`TSP`

,`ATSP`

or`ETSP`

. - method
- method to solve the TSP (default: arbitrary insertion algorithm with two_opt refinement.
- control
- a list of arguments passed on to the TSP solver
selected by
`method`

. - ...
- additional arguments are added to
`control`

.

##### Details

Treatment of `NA`

s and infinite values in `x`

:
`TSP`

and `ATSP`

contain distances and `NA`

s are not allowed.
`Inf`

is allowed and can be used to model the missing edges in
incomplete graphs
(i.e., the distance between the two objects is infinite).
Internally, `Inf`

is replaced by a large value given by
$max(x) + 2 range(x)$.
Note that the solution might still place the two objects next to each other
(e.g., if `x`

contains several unconnected subgraphs)
which results in a path length of `Inf`

.
All heuristics can be used with the control arguments `repetitions`

(uses the best from that many repetitions with random starts)
and `two_opt`

(a logical indicating if two_opt refinement should be
performed). If several repetitions are done (this includes method `"repetitive_nn"`

) then `registerDoParallel()`

).

`ETSP`

are currently solved by first calculating a dissimilarity matrix (a
`TSP`

). Only concorde and linkern can solve the TSP directly on the
`ETSP`

.

Currently the following methods are available: [object Object],[object Object],[object Object],[object Object],[object Object],[object Object]

##### Value

- An object of class
`TOUR`

.

##### References

Concorde home page,

David Appletgate, Robert Bixby, Vasek Chvatal, William Cook (2001): TSP cuts which do not conform to the template paradigm, Computational Combinatorial Optimization, M. Junger and D. Naddef (editors), Springer.

D. Applegate, W. Cook and A. Rohe (2003): Chained Lin-Kernighan for Large
Traveling Salesman Problems. *INFORMS Journal on Computing,
15(1):82--92.*

G.A. Croes (1958): A method for solving traveling-salesman problems.
*Operations Research, 6(6):791--812.*

S. Lin and B. Kernighan (1973): An effective heuristic algorithm for the
traveling-salesman problem. *Operations Research, 21(2): 498--516.*
D.J. Rosenkrantz, R. E. Stearns, and Philip M. Lewis II (1977): An analysis of
several heuristics for the traveling salesman problem. *SIAM Journal on
Computing, 6(3):563--581.*

##### See Also

`TOUR`

,
`TSP`

,
`ATSP`

,
`write_TSPLIB`

,
`Concorde`

.

##### Examples

```
## solve a simple Euclidean TSP (using the default method)
etsp <- ETSP(data.frame(x = runif(20), y = runif(20)))
tour <- solve_TSP(etsp)
tour
tour_length(tour)
plot(etsp, tour)
## compare methods
data("USCA50")
USCA50
methods <- c("identity", "random", "nearest_insertion",
"cheapest_insertion", "farthest_insertion", "arbitrary_insertion",
"nn", "repetitive_nn", "two_opt")
## calculate tours
tours <- lapply(methods, FUN = function(m) solve_TSP(USCA50, method = m))
names(tours) <- methods
## use the external solver which has to be installed separately
tours$concorde <- solve_TSP(USCA50, method = "concorde")
tours$linkern <- solve_TSP(USCA50, method = "linkern")
## register a parallel backend to perform repetitions in parallel
library(doParallel)
registerDoParallel()
## add some tours using repetition and two_opt refinements
tours$'nn+two_opt' <- solve_TSP(USCA50, method="nn", two_opt=TRUE)
tours$'nn+rep_10' <- solve_TSP(USCA50, method="nn", rep=10)
tours$'nn+two_opt+rep_10' <- solve_TSP(USCA50, method="nn", two_opt=TRUE, rep=10)
tours$'arbitrary_insertion+two_opt' <- solve_TSP(USCA50)
## show first tour
tours[[1]]
## compare tour lengths
opt <- 14497 # obtained by Concorde
tour_lengths <- c(sort(sapply(tours, tour_length), decreasing = TRUE),
optimal = opt)
dotchart(tour_lengths/opt*100-100, xlab = "percent excess over optimum")
```

*Documentation reproduced from package TSP, version 1.1-4, License: GPL-3*