A service provided by the WU Library and the WU IT-Services

TSP - Infrastructure for the Traveling Salesperson Problem

Hahsler, Michael and Hornik, Kurt (2006) TSP - Infrastructure for the Traveling Salesperson Problem. Research Report Series / Department of Statistics and Mathematics, 45. Department of Statistics and Mathematics, WU Vienna University of Economics and Business, Vienna.

WarningThere is a more recent version of this item available.
[img]
Preview
PDF
Download (890Kb) | Preview

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. In addition to vehicle routing, many other applications, e.g., computer wiring, cutting wallpaper, job sequencing or several data visualization techniques, require the solution of a TSP. 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. (author's abstract)

Item Type: Paper
Keywords: Combinatorial optimization / traveling salesman problem / R
Classification Codes: RVK SK 890, QH 425 ; JEL CCS_G.2.1
Divisions: Departments > Finance, Accounting and Statistics > Statistics and Mathematics
Depositing User: Repository Administrator
Date Deposited: 21 Dec 2006 15:59
Last Modified: 06 May 2015 03:17
URI: http://epub.wu.ac.at/id/eprint/1230

Available Versions of this Item

Actions

View Item