Iterative Patching and the Asymmetric Traveling Salesman Problem

Marcel Turkensteen, Diptesh Ghosh (), Boris Goldengorin and Gerard Sierksma
Additional contact information
Gerard Sierksma: Groningen University

No 04A27, Research Report from University of Groningen, Research Institute SOM (Systems, Organisations and Management)

Abstract: Although Branch and Bound (BnB) methods are among the most widely used techniques for solving hard problems, it is still a challenge to make these methods smarter. In this paper, we investigate iterative patching, a technique in which a fixed patching procedure is applied at each node of the BnB search tree for the Asymmetric Traveling Salesman Problem. Computational experiments show that iterative patching results in general in search trees that are smaller than the usual classical BnB trees, and that solution times are lower for usual random and sparse instances. Furthermore, it turns out that, on average, iterative patching with the Contract-or-Patch procedure of Glover, Gutin, Yeo and Zverovich (2001) and the Karp-Steele procedure are the fastest, and that ?iterative? Modified Karp-Steele patching generates the smallest search trees.

Date: 2004
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://irs.ub.rug.nl/ppn/274569213 (application/pdf)
Our link check indicates that this URL is bad, the error code is: 403 Forbidden (http://irs.ub.rug.nl/ppn/274569213 [302 Found]--> https://irs.ub.rug.nl/ppn/274569213 [302 Found]--> https://www.rug.nl/research/portal/publications/pub(8067a99b-e3c1-4d1c-9cdc-a950fad31d8c).html [301 Moved Permanently]--> https://research.rug.nl/en/publications/pub(8067a99b-e3c1-4d1c-9cdc-a950fad31d8c).html [301 Moved Permanently]--> https://research.rug.nl/en/publications/iterative-patching-and-the-asymmetric-traveling-salesman-problem-3)

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:gro:rugsom:04a27

Access Statistics for this paper

More papers in Research Report from University of Groningen, Research Institute SOM (Systems, Organisations and Management) Contact information at EDIRC.
Bibliographic data for series maintained by Hanneke Tamling ().