Abstract

A “branch and bound” algorithm is presented for solving the traveling salesman problem. The set of all tours (feasible solutions) is broken up into increasingly small subsets by a procedure called branching. For each subset a lower bound on the length of the tours therein is calculated. Eventually, a subset is found that contains a single tour whose length is less than or equal to some lower bound for every tour. The motivation of the branching and the calculation of the lower bounds are based on ideas frequently used in solving assignment problems. Computationally, the algorithm extends the size of problem that can reasonably be solved without using methods special to the particular problem.

Keywords

Travelling salesman problemBranch and boundBottleneck traveling salesman problem2-optUpper and lower boundsAlgorithmSet (abstract data type)MathematicsComputer scienceMathematical optimizationCombinatorics

Affiliated Institutions

Related Publications

Handbook of Genetic Algorithms

Lawrence Davis

This book sets out to explain what genetic algorithms are and how they can be used to solve real-world problems. The first objective is tackled by the editor, Lawrence Davis. Th...

1991 7308 citations

Publication Info

Year
1963
Type
article
Volume
11
Issue
6
Pages
972-989
Citations
1037
Access
Closed

External Links

View on DOI.org

Social Impact

Altmetric
PlumX Metrics

Social media, news, blog, policy document mentions

Citation Metrics

1037
OpenAlex

Cite This

John D. C. Little, Katta G. Murty, Dura W. Sweeney et al. (1963). An Algorithm for the Traveling Salesman Problem. Operations Research , 11 (6) , 972-989. https://doi.org/10.1287/opre.11.6.972

Identifiers

DOI
10.1287/opre.11.6.972