README.Rmd

---
output: github_document
bibliography: vignettes/TSP.bib
link-citations: yes
---

```{r echo=FALSE, results = 'asis'}
pkg <- 'TSP'

source("https://raw.githubusercontent.com/mhahsler/pkg_helpers/main/pkg_helpers.R")
pkg_title(pkg)
```
[![Anaconda.org](https://anaconda.org/conda-forge/r-tsp/badges/version.svg)](https://anaconda.org/conda-forge/r-tsp)

## Introduction

The TSP package [@Hahsler+Hornik2007] provides the 
basic infrastructure and some algorithms for the traveling
salesman problems (symmetric, asymmetric and Euclidean TSPs). 
The package provides some fast implementations of simple algorithms including:

* __Tour construction heuristics__
  * __Insertion algorithms__: nearest insertion, farthest insertion, cheapest insertion, arbitrary insertion [@Rosenkrantz1977]
  * __Nearest neighbor methods__: Nearest neighbor and repetitive nearest neighbor [@Rosenkrantz1977]

* __Tour improvement methods__
  * __Two-opt heuristic__ [@Croes1958]
  * __Simulated annealing__ [@Kirkpatrick1983]

* __State-of-the-art solver interfaces__
  * __Concorde TSP solver interface__ [@Applegate2000; @Applegate2006]
  * __Concorde Chained-Lin-Kernighan heuristic interface__ [@Applegate2003]

The package can read and write the TSPLIB format [@Reinelt1991] and it can solve many of the 
problems in the [TSPLIB95 problem library (local copy of the archive)](https://github.com/mhahsler/TSP/tree/master/TSPLIB95).

```{r echo=FALSE, results = 'asis'}
pkg_usage(pkg)
pkg_citation(pkg, 2L)
pkg_install(pkg)
```

## Usage

Load a data set with 312 cities (USA and Canada) and create a TSP object. 
```{r}
library("TSP")
data("USCA312")
 
tsp <- TSP(USCA312)
tsp
```

Find a tour using the default heuristic. 
```{r}
tour <- solve_TSP(tsp)
tour
```

Show the first few cities in the tour.
```{r}
head(tour, n = 10)
```

Visualize the complete tour.
```{r, fig.dim=c(6, 6)}
library(maps)
data("USCA312_GPS")

plot((USCA312_GPS[, c("long", "lat")]), cex = .3)
map("world", col = "gray", add = TRUE)
polygon(USCA312_GPS[, c("long", "lat")][tour,], border = "red")
```


An online example application of TSP can be found on [shinyapps](https://shrinidhee.shinyapps.io/SimpleTSP).

## Help and Bug Reports

You can find Q&A's and ask your own questions at 
https://stackoverflow.com/search?q=TSP+R

Please submit bug reports to https://github.com/mhahsler/TSP/issues

## References