Lower tolerance-based Branch and Bound algorithms for the ATSP

R. Germs, B. Goldengorin, M. Turkensteen

Research output: Contribution to journalArticleAcademicpeer-review

23 Citations (Scopus)

Abstract

In this paper, we develop a new tolerance-based Branch and Bound algorithm for solving NP-hard problems. In particular, we consider the asymmetric traveling salesman problem (ATSP), an NP-hard problem with large practical relevance. The main algorithmic contribution is our lower bounding strategy that uses the expected costs of including arcs in the solution to the assignment problem relaxation of the ATSP, the so-called lower tolerance values. The computation of the lower bound requires the calculation of a large set of lower tolerances. We apply and adapt a finding from [23] that makes it possible to compute all lower tolerance values efficiently. Computational results show that our Branch and Bound algorithm exhibits very good performance in comparison with state-of-the-art algorithms, in particular for difficult clustered ATSP instances
Original languageEnglish
Pages (from-to)291-298
JournalComputers and Operations Research
Volume39
Issue number2
DOIs
Publication statusPublished - 2012

Keywords

  • traveling salesman problems
  • assignment

Fingerprint Dive into the research topics of 'Lower tolerance-based Branch and Bound algorithms for the ATSP'. Together they form a unique fingerprint.

  • Cite this