Iterative Patching and the Asymmetric Traveling Salesman Problem
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.
Year of publication: |
2004
|
---|---|
Authors: | Turkensteen, Marcel ; Ghosh, Diptesh ; Goldengorin, Boris ; Sierksma, Gerard |
Institutions: | Faculteit Economie en Bedrijfskunde, Rijksuniversiteit Groningen |
Saved in:
freely available
Saved in favorites
Similar items by person
-
Branch and peg algorithms for the simple plant location problem
Goldengorin, Boris, (2001)
-
Equivalent instances of the simple plant location problem
Ghosh, Diptesh, (2000)
-
Tolerance-based Branch and Bound algorithms for the ATSP
Turkensteen, Marcel, (2008)
- More ...