An Algorithm for the Traveling Salesman Problem

John D. C. Little, Katta G. Murty, Dura W. Sweeney and Caroline Karel
Additional contact information
John D. C. Little: Massachusetts Institute of Technology
Katta G. Murty: Indian Statistical Institute
Dura W. Sweeney: International Business Machines Corporation
Caroline Karel: Case Institute of Technology

Operations Research, 1963, vol. 11, issue 6, 972-989

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.

Date: 1963
References: Add references at CitEc
Citations: View citations in EconPapers (48)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.11.6.972 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:11:y:1963:i:6:p:972-989

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().