R package TSP - Traveling Salesperson Problem (TSP)
This package provides the basic infrastructure and some algorithms for the traveling salesman problems (symmetric, asymmetric and Euclidean TSPs). The package provides some simple algorithms and an interface to the Concorde TSP solver and its implementation of the Chained-Lin-Kernighan heuristic.
Installation
Stable CRAN version: Install from within R with
install.packages("TSP")Current development version: Install from r-universe.
install.packages("TSP", repos = "https://mhahsler.r-universe.dev")Usage
Load a data set with 312 cities (USA and Canada) and create a TSP object.
library("TSP")
data("USCA312")
tsp <- TSP(USCA312)
tsp## object of class 'TSP'
## 312 cities (distance 'euclidean')
Find a tour using the default heuristic.
tour <- solve_TSP(tsp)
tour## object of class 'TOUR'
## result of method 'arbitrary_insertion+two_opt' for 312 cities
## tour length: 40743
Show the first few cities in the tour.
head(tour, n = 10)## Sheboygan, WI Milwaukee, WI Racine, WI Kenosha, WI South Bend, IN
## 253 165 214 135 259
## Gary, IN Chicago, IL Rockford, IL Madison, WI Dubuque, IA
## 104 58 224 158 78
An online example application of TSP can be found on shinyapps.
References
- Michael Hahsler and Kurt Hornik, TSP - Infrastructure for the Traveling Salesperson Problem, Journal of Statistical Software, 22(2), 2007.
- TSP package vignette with complete examples.
- Reference manual
- Concorde TSP solver home page.