EPUB	WORKING PAPERS	DISSERTATIONS

back | new search | print Hahsler, Michael; Hornik, Kurt: TSP - Infrastructure for the Traveling Salesperson Problem Research Report Series / Department of Statistics and Mathematics, Nr. 45, December 2006 Department of Statistics and Mathematics , Wirtschaftsuniversität Wien, Augasse 2-6, A-1090 Wien, Austria, 2006 Holdings from the WU library catalog | document ID: oai:epub.wu-wien.ac.at:epub-wu-01_b1b Download document 16 pages/899 kB © Copyright notice  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)  Keywords: Combinatorial optimization / traveling salesman problem / R  Classification: CCS G.2.1 © 2009 University Library and Institute for Information Business, Vienna University of Economics and Business | Thu Sep 2 19:28:33 2010