Tolerance-based Branch and Bound algorithms for the ATSP

Tolerance-based Branch and Bound algorithms for the ATSP,10.1016/j.ejor.2006.10.062,European Journal of Operational Research,Marcel Turkensteen,Diptes

Tolerance-based Branch and Bound algorithms for the ATSP   (Citations: 5)
BibTex | RIS | RefWorks Download
The selection of entries to be included/excluded in Branch and Bound algorithms is usually done on the basis of cost values. We consider the class of Depth First Search algorithms, and we propose to use upper tolerances to guide the search for optimal solutions. In spite of the fact that it needs time to calculate tolerances, our computational experiments for Asymmetric Traveling Salesman Problems show that in most situations tolerance-based algorithms outperform cost-based algorithms. The solution time reductions are mainly caused by the fact that the branching process becomes much more effective, so that optimal solutions are found in an earlier stage of the branching process. The use of tolerances also reveals why the widely used choice for branching on a smallest cycle in assignment solutions is on average the most effective one. Moreover, it turns out that tolerance-based DFS algorithms are better in solving difficult instances than the Best First Search algorithm from Carpaneto et al. (Carpaneto, G., Dell'Amico, M., Toth, P., 1995. Exact solution of large-scale asymmetric traveling salesman problems. ACM Transactions on Mathematical Software 21 (4), 394-409). 2006 Elsevier B.V. All rights reserved.
Journal: European Journal of Operational Research - EJOR , vol. 189, no. 3, pp. 775-788, 2008
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...Goldengorin et al. [10,11] and Turkensteen et al. [29] have shown that the arcs with strictly positive upper tolerance in an optimal Assignment Problem (AP) solution are common arcs for all optimal AP solutions...
    • ...Ghosh et al. [8], Goldengorin and J¨ager [9], Goldengorin et al. [12,13], and Turkensteen et al. [29] have applied the largest (bottleneck) upper tolerance for an arc in an optimal solution of the relaxed AP to guide a search of either a high quality heuristic or an exact algorithm for the Asymmetric TSP...
    • ...In Section 2 we define the notion of tolerances [10,29]...

    Dirk Richteret al. Improving the Efficiency of Helsgaun's Lin-Kernighan Heuristic for the...

    • ...Recently, Turkensteen, Ghosh et al.[19] reported a new branching rule in B&B algorithm which utilizes tolerances to indicate which arcs are preferred to save in the optimal ATSP tour...

    Jie Baiet al. Collaborative Optimization under a Control Framework for ATSP

Sort by: