Quotation Hahsler, Michael, Hornik, Kurt. 2007. TSP - Infrastructure for the Traveling Salesperson Problem. Journal of Statistical Software 23 (2): 1-21.


RIS


BibTeX

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.

Tags

Press 'enter' for creating the tag

Publication's profile

Status of publication Published
Affiliation WU
Type of publication Journal article
Journal Journal of Statistical Software
Citation Index SCI
WU-Journal-Rating new FIN-A
Language English
Title TSP - Infrastructure for the Traveling Salesperson Problem
Volume 23
Number 2
Year 2007
Page from 1
Page to 21
Reviewed? Y
URL http://www.jstatsoft.org/v23/i02

Associations

People
Hahsler, Michael (Former researcher)
Hornik, Kurt (Details)
Organization
Applied Information Technology with Focus on IT in Organization (Details)
Institute for Statistics and Mathematics IN (Details)
Research Institute for Computational Methods FI (Details)
Google Scholar: Search