Learn R Programming

R package TSP - Infrastructure for the Traveling Salesperson Problem

Maintainer: Michael Hahsler

Introduction

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

Most algorithms are optimized to work on symmetric TSPs stored as distance matrices, but asymmetric TSPs (ATSPs) and Euclidean TSPs (ETSPs) are also supported.

The package can read and write the TSPLIB format (Reinelt 1991) and it can solve many of the problems in the TSPLIB95 problem library (local copy of the archive).

The following R packages use TSP: archetypes, cholera, condvis, CRTspat, ForagingOrg, ggEDA, isocir, MLCOPULA, nilde, nlnet, PairViz, sensitivity, seriation, sfnetworks, tspmeta, VineCopula, wompwomp

To cite package ‘TSP’ in publications use:

Hahsler M, Hornik K (2007). “TSP - Infrastructure for the traveling salesperson problem.” Journal of Statistical Software, 23(2), 1-21. ISSN 1548-7660. doi:10.18637/jss.v023.i02 https://doi.org/10.18637/jss.v023.i02.

@Article{,
  title = {TSP -- {I}nfrastructure for the traveling salesperson problem},
  author = {Michael Hahsler and Kurt Hornik},
  year = {2007},
  journal = {Journal of Statistical Software},
  volume = {23},
  number = {2},
  pages = {1--21},
  doi = {10.18637/jss.v023.i02},
  month = {December},
  issn = {1548-7660},
}

Installation

Stable CRAN version: Install from within R with

install.packages("TSP")

Current development version: Install from r-universe.

install.packages("TSP",
    repos = c("https://mhahsler.r-universe.dev",
              "https://cloud.r-project.org/"))

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: 40632

Show the first few cities in the tour.

head(tour, n = 10)
##    Santa Cruz, CA      San Jose, CA      Stockton, CA   Carson City, NV 
##               245               242               268                48 
##          Reno, NV    Sacramento, CA      Berkeley, CA       Oakland, CA 
##               219               225                26               186 
## San Francisco, CA          Hilo, HI 
##               241               119

Visualize the complete tour.

library(maps)
data("USCA312_GPS")

plot((USCA312_GPS[, c("long", "lat")]), cex = 0.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.

Help and Bug Reports

You can find Q&As 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

  • Applegate, David, Robert E. Bixby, Vasek Chvátal, and William Cook. 2000. “TSP Cuts Which Do Not Conform to the Template Paradigm.” In Computational Combinatorial Optimization, Optimal or Provably Near-Optimal Solutions, edited by M. Junger and D. Naddef, vol. 2241. Lecture Notes in Computer Science. Springer-Verlag. https://doi.org/10.1007/3-540-45586-8_7.

  • Applegate, David, Robert Bixby, Vasek Chvátal, and William Cook. 2006. Concorde TSP Solver. https://www.math.uwaterloo.ca/tsp/concorde.html.

  • Applegate, David, William Cook, and Andre Rohe. 2003. “Chained Lin-Kernighan for Large Traveling Salesman Problems.” INFORMS Journal on Computing 15 (1): 82–92. https://doi.org/10.1287/ijoc.15.1.82.15157.

  • Bock, F. 1958. “An Algorithm for Solving "Traveling-Salesman" and Related Network Optimization Problems.” Unpublished manuscript.

  • Croes, G. A. 1958. “A Method for Solving Traveling-Salesman Problems.” Operations Research 6 (6): 791–812. https://doi.org/10.1287/opre.6.6.791.

  • Hahsler, Michael, and Kurt Hornik. 2007. “TSP – Infrastructure for the Traveling Salesperson Problem.” Journal of Statistical Software 23 (2): 1–21. https://doi.org/10.18637/jss.v023.i02.

  • Kirkpatrick, S., C. D. Gelatt, and M. P. Vecchi. 1983. “Optimization by Simulated Annealing.” Science 220 (4598): 671–80. https://doi.org/10.1126/science.220.4598.671.

  • Lin, S. 1965. “Computer Solutions of the Traveling-Salesman Problem.” Bell System Technology Journal 44: 2245–69.

  • Or, I. 1976. “Traveling Salesman-Type Combinatorial Problems and Their Relation to the Logistics of Regional Blood Banking.” PhD thesis, Northwestern University.

  • Reinelt, Gerhard. 1991. “TSPLIB—a Traveling Salesman Problem Library.” ORSA Journal on Computing 3 (4): 376–84. https://doi.org/10.1287/ijoc.3.4.376.

  • Rosenkrantz, Daniel J., Richard 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–81. https://doi.org/10.1007/978-1-4020-9688-4_3.

Copy Link

Version

Install

install.packages('TSP')

Monthly Downloads

28,290

Version

1.3.0

License

GPL-3

Issues

Pull Requests

Stars

Forks

Maintainer

Michael Hahsler

Last Published

November 13th, 2026

Functions in TSP (1.3.0)

ATSP

Class ATSP -- Asymmetric traveling salesperson problem
TSP-package

TSP: Infrastructure for the Traveling Salesperson Problem
TSP

Class TSP -- Symmetric traveling salesperson problem
insert_dummy

Insert dummy cities into a distance matrix
cut_tour

Cut a tour to form a path
tour_length

Calculate the length of a tour
reformulate_ATSP_as_TSP

Reformulate an ATSP as a symmetric TSP
solve_TSP

TSP solver interface
USCA

USCA312/USCA50 -- 312/50 cities in the US and Canada
TSPLIB

Read and write TSPLIB files
ETSP

Class ETSP -- Euclidean traveling salesperson problem
TOUR

Class TOUR -- Solution to a traveling salesperson problem
Concorde

Using the Concorde TSP Solver