کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1141619 | 957046 | 2006 | 15 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Iterative patching and the asymmetric traveling salesman problem Iterative patching and the asymmetric traveling salesman problem](/preview/png/1141619.png)
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 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.
Journal: Discrete Optimization - Volume 3, Issue 1, 1 March 2006, Pages 63–77