Some New Branching and Bounding Criteria for the Asymmetric Travelling Salesman Problem

Giorgio Carpaneto and Paolo Toth
Additional contact information
Giorgio Carpaneto: University of Bologna, Italy
Paolo Toth: University of Bologna, Italy

Management Science, 1980, vol. 26, issue 7, 736-743

Abstract: Many algorithms have been developed for the optimal solution of the asymmetric travelling salesman problem: the most efficient ones are based on the subtour elimination approach. This paper presents a breadth-first branch and bound algorithm which differs from the method of Smith, Srinivasan and Thompson in the selection of the subtour to be split, in the ordering of the arcs in the selected subtour, in the computation of different partial lower bounds and in different data structures to facilitate the updating of the cost matrix. Extensive computational results considering random problems with up to 240 vertices are presented for various ranges of the coefficients of the cost matrix.

Keywords: assignment problem; assymetric TSP; branch and bound; subtour elimination (search for similar items in EconPapers)
Date: 1980
References: Add references at CitEc
Citations: View citations in EconPapers (16)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.26.7.736 (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:ormnsc:v:26:y:1980:i:7:p:736-743

Access Statistics for this article

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