Resource title

TSP - Infrastructure for the Traveling Salesperson Problem

Resource image

image for OpenScout resource :: TSP - Infrastructure for the Traveling Salesperson Problem

Resource description

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) ; Series: Research Report Series / Department of Statistics and Mathematics

Resource author

Michael Hahsler, Kurt Hornik

Resource publisher

Resource publish date

Resource language

en

Resource content type

application/pdf

Resource resource URL

http://epub.wu.ac.at/1230/1/document.pdf

Resource license

Adapt according to the license agreement. Always reference the original source and author.