Tolerance-based Branch and Bound algorithms for the ATSP

Marcel Turkensteen, Diptesh Ghosh (), Boris Goldengorin and Gerard Sierksma

European Journal of Operational Research, 2008, vol. 189, issue 3, pages 775-788

Abstract: 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].

Date: 2008

Downloads: (external link)
http://www.sciencedirect.com/science/article/B6VCT ... 776dd0076a9b50fc7e16
Full text for ScienceDirect subscribers only

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: http://EconPapers.repec.org/RePEc:eee:ejores:v:189:y:2008:i:3:p:775-788

Access Statistics for this article

European Journal of Operational Research is edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Series data maintained by Heidi Boesdal ().