TSPInfrastructure for the Traveling Salesperson Problem

Michael Hahsler and Kurt Hornik

Journal of Statistical Software, 2007, vol. 023, issue i02

Abstract: The traveling salesperson (or, salesman) problem (TSP) is a well known and important combinatorial optimization problem. The goal is to find the shortest tour that visits each city in a given list exactly once and then returns to the starting city. Despite this simple problem statement, solving the TSP is difficult since it belongs to the class of NP-complete problems. The importance of the TSP arises besides from its theoretical appeal from the variety of its applications. Typical applications in operations research include vehicle routing, computer wiring, cutting wallpaper and job sequencing. The main application in statistics is combinatorial data analysis, e.g., reordering rows and columns of data matrices or identifying clusters. In this paper, we introduce the R package TSP which provides a basic infrastructure for handling and solving the traveling salesperson problem. The package features S3 classes for specifying a TSP and its (possibly optimal) solution as well as several heuristics to find good solutions. In addition, it provides an interface to Concorde, one of the best exact TSP solvers currently available.

Date: 2007-12-18
References: View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
https://www.jstatsoft.org/index.php/jss/article/view/v023i02/v23i02.pdf
https://www.jstatsoft.org/index.php/jss/article/do ... i02/TSP_0.2-1.tar.gz
https://www.jstatsoft.org/index.php/jss/article/do ... v023i02/v23i02.R.zip

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:jss:jstsof:v:023:i02

DOI: 10.18637/jss.v023.i02

Access Statistics for this article

Journal of Statistical Software is currently edited by Bettina Grün, Edzer Pebesma and Achim Zeileis

More articles in Journal of Statistical Software from Foundation for Open Access Statistics
Bibliographic data for series maintained by Christopher F. Baum (baum@bc.edu).