<b>TSP</b>- Infrastructure for the Traveling Salesperson Problem
Journal of Statistical SoftwarePublished 1 January 2007Open access
Michael Hahsler, Kurt Hornik
Citations160
SJR quartileQ1
SJR score3.21
SNIP4.61
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The R package TSP is introduced which provides a basic infrastructure for handling and solving the traveling salesperson problem and provides an interface to Concorde, one of the best exact TSP solvers currently available.
Abstract
The traveling salesperson (or, salesman) problem (TSP) is a well known and important \ncombinatorial optimization problem. The goal is to find the shortest tour that visits each \ncity in a given list exactly once and then returns to the starting city. Despite this simple \nproblem statement, solving the TSP is difficult since it belongs to the class of NP-complete \nproblems. The importance of the TSP arises besides from its theoretical appeal from the \nvariety of its applications. Typical applications in operations research include vehicle \nrouting, computer wiring, cutting wallpaper and job sequencing. The main application \nin statistics is combinatorial data analysis, e.g., reordering rows and columns of data \nmatrices or identifying clusters. In this paper, we introduce the R package TSP which \nprovides a basic infrastructure for handling and solving the traveling salesperson problem. \nThe package features S3 classes for specifying a TSP and its (possibly optimal) solution \nas well as several heuristics to find good solutions. In addition, it provides an interface to \nConcorde, one of the best exact TSP solvers currently available. (authors' abstract)
Keywords
Engineering
Operations ResearchAn Effective Heuristic Algorithm for the Traveling-Salesman Problem
3,797 Citations1973Simon Lin, Brian W. Kernighan
This paper discusses a highly effective heuristic procedure for generating optimum and near-optimum solutions for the symmetric traveling-salesman problem based on a general approach to heuristics that is believed to have wide applicability in combinatorial optimization problems.
An Automatic Method for Solving Discrete Programming Problems
1,997 Citations2009A. H. Land, Alison Doig
Bell System Technical JournalComputer Solutions of the Traveling Salesman Problem
1,960 Citations1965Shen Lin
Two algorithms for solving the (symmetric distance) traveling salesman problem have been programmed for a high-speed digital computer and are based on a general heuristic approach believed to be of general applicability to various optimization problems.
The Traveling Salesman Problem
1,622 Citations2019Lawrence Snyder, Zuo‐Jun Max Shen
Operations ResearchA Method for Solving Traveling-Salesman Problems
1,532 Citations1958G. A. Croes
A method of solution for the traveling-salesman problem that is applicable to both symmetric and asymmetric problems with random elements, and does not use subjective decisions, so that it can be completely mechanized.
Combinatorial optimizationThe Traveling Salesman Problem and Its Variations
1,374 Citations2006Gregory Gutin, Abraham P. Punnen
This paper presents Polyhedral Theory and Branch-and-Cut Algorithms for the Symmetric TSP, a model for solving the Asymmetric Traveling Salesman Problem, and some examples of how this model was applied to the Geometric TSP.
Bulletin of the American Mathematical SocietyOutline of an algorithm for integer solutions to linear programs
1,352 Citations1958Ralph E. Gomory
Solution of a Large-Scale Traveling-Salesman Problem
1,273 Citations2009Vašek Chvátal, William J. Cook +3 more
The RAND Corporation in the early 1950s contained “what may have been the most remarkable group of mathematicians working on optimization ever assembled”: Arrow, Bellman, Dantzig, Flood, Ford, Fulkerson, Gale, Johnson, Nash, Orchard-Hays, Robinson, Shapley, Simon, Wagner, and other household names.
Journal of the Society for Industrial and Applied MathematicsA Dynamic Programming Approach to Sequencing Problems
1,253 Citations1962Michael Held, Richard M. Karp
An analysis of several heuristics for the traveling salesman problem
784 Citations2009Daniel J. Rosenkrantz, Richard E. Stearns +1 more
INFORMS journal on computingChained Lin-Kernighan for Large Traveling Salesman Problems
399 Citations2003David Applegate, William J. Cook +1 more
Combinatorial optimizationExperimental Analysis of Heuristics for the STSP
333 Citations2006David S. Johnson, Lyle A. McGeoch
This and the following chapter consider what approaches one should take when one is confronted with a real-world application of the TSP, and the more general and less well-studied asymmetric case.
Journal of the Operational Research SocietySome Simple Applications of the Travelling Salesman Problem
268 Citations1975Jan Karel Lenstra, A. H. G. Rinnooy Kan
This paper reports on typical applications in computer wiring, vehicle routing, clustering and job-shop scheduling that originated from real world problems and thus seem to be of particular interest.
Mathematical ProgrammingFacet identification for the symmetric traveling salesman polytope
130 Citations1990Manfred Padberg, Giovanni Rinaldi
Exact and heuristic shrinking conditions for the input graph are given that yield efficient procedures for the identification of simple and general comb inequalities and of some elementary clique tree inequalities.
Operations Research LettersTransforming asymmetric into symmetric traveling salesman problems
120 Citations1983Roy Jonker, Ton Volgenant
This paper describes how to transform an asymmetric traveling salesman problem into a symmetric one at the cost of almost doubled problem size.
Lecture notes in computer scienceTSP Cuts Which Do Not Conform to the Template Paradigm
112 Citations2001David Applegate, Robert E. Bixby +2 more
The purpose of this paper is to describe a technique for finding cuts that disdains all understanding of the TSP polytope and bashes on regardless of all prescribed templates.
Combinatorial optimizationThe Traveling Salesman Problem: Applications, Formulations and Variations
87 Citations2006Abraham P. Punnen
The traveling salesman problem (TSP) is to find a routing of a salesman who starts from a home location, visits a prescribed set of cities and returns to the original location in such a way that the total distance travelled is minimum and each city is visited exactly once.
Elsevier eBooksCompressing Large Boolean Matrices Using Reordering Techniques
81 Citations2004David S. Johnson, Shankar Krishnan +3 more
This work presents a lossless compression strategy to store and access large boolean matrices efficiently on disk, and adapts classical TSP heuristics by means of instance-partitioning and sampling.
Source Code for Biology and MedicineA traveling salesman approach for predicting protein functions
65 Citations2006Olin Johnson, Jing Liu
This work presents a new approach utilizing the classic Traveling Salesman Problem to study the protein-protein interactions and to predict protein functions in budding yeast Saccharomyces cerevisiae using the global optimization tool from combinatorial optimization algorithms to cluster the yeast proteins based on the global protein interaction information.
Open Scholarship Institutional Repository (Washington University in St. Louis)Rearrangement Clustering: Pitfalls, Remedies, and Applications
63 Citations2005Sharlee Climer
This paper points out two critical pitfalls that have been previously overlooked in rearrangement clustering and presents an algorithm that overcomes these pitfalls, based on a variation of the Traveling Salesman Problem, that identifies better clusters than those found by previous approaches in all five cases.
Computational Combinatorial Optimization: Optimal or Provably Near-Optimal Solutions
36 Citations2001Michael Jünger, Denis Naddef
This paper discusses branch-and-Cut Algorithms for Combinatorial Optimization and their Implementation in ABACUS, and TSP Cuts Which Do Not Conform to the Template Paradigm.
PsychometrikaApplications of Combinatorial Programming to Data Analysis: The Traveling Salesman and Related Problems
27 Citations1978Lawrence J. Hubert, Frank B. Baker
The “Traveling Salesman” and similar combinatorial programming tasks encountered in operations research are discussed as possible data analysis models in psychology, for example, in developmental scaling, Guttman scaling, profile smoothing, and data array clustering.
Journal of BiosciencesGene ordering in partitive clustering using microarray expressions
18 Citations2007Shubhra Sankar Ray, Sanghamitra Bandyopadhyay +1 more
The approach improves the result quality of partitive clustering solution, by identifying subclusters within big clusters, grouping functionally correlated genes within clusters, minimization of summation of gene expression distances, and the maximization of biological gene ordering using MIPS categorization.
Journal of ClassificationSplitting an Ordering into a Partition to Minimize Diameter
18 Citations1997Charles J. Alpert, Andrew B. Kahng
This work derives from a new restricted partition formulation that requires each cluster to be an interval of a given ordering of the objects being clustered, and shows that this algorithm, when combined with an appropriate ordering heuristic, outperforms traditional algorithms on both random and non-random data sets.