Nonoptimal Edges for the Symmetric Traveling Salesman Problem

Roy Jonker and Ton Volgenant
Additional contact information
Roy Jonker: University of Amsterdam, Amsterdam, The Netherlands
Ton Volgenant: University of Amsterdam, Amsterdam, The Netherlands

Operations Research, 1984, vol. 32, issue 4, 837-846

Abstract: For the symmetric traveling salesman problem, we identify a set of (undirected) edges that can be eliminated while still retaining at least one optimal solution of the problem. The simple identification rules are based on the fact that a solution can be optimal only if it is 2-optimal. The rules are less stringent than those formulated for nonoptimal arcs (directed), applied to the symmetric case. So, in general, they identify more nonoptimal edges. Application of the theory in a 1-tree based traveling salesman algorithm roughly halves the average computation time for Euclidean problems. We indicate to what extent the theorems presented here can be adapted for variants of the traveling salesman problem.

Keywords: 491; nonoptimal; edges (search for similar items in EconPapers)
Date: 1984
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.32.4.837 (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:32:y:1984:i:4:p:837-846

Access Statistics for this article

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