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. (authors' abstract)
| Identifer | oai:union.ndltd.org:VIENNA/oai:epub.wu-wien.ac.at:3990 |
| Date | 12 1900 |
| Creators | Hahsler, Michael, Hornik, Kurt |
| Publisher | American Statistical Association |
| Source Sets | Wirtschaftsuniversität Wien |
| Language | English |
| Detected Language | English |
| Type | Article, PeerReviewed |
| Format | application/pdf |
| Relation | http://www.jstatsoft.org/v23/i02/paper, http://epub.wu.ac.at/3990/ |
Page generated in 0.0016 seconds