Staff Publications

Staff Publications

  • external user (warningwarning)
  • Log in as
  • language uk
  • About

    'Staff publications' is the digital repository of Wageningen University & Research

    'Staff publications' contains references to publications authored by Wageningen University staff from 1976 onward.

    Publications authored by the staff of the Research Institutes are available from 1995 onwards.

    Full text documents are added when available. The database is updated daily and currently holds about 240,000 items, of which 72,000 in open access.

    We have a manual that explains all the features 

Record number 444362
Title Lower tolerance-based Branch and Bound algorithms for the ATSP
Author(s) Germs, R.; Goldengorin, B.; Turkensteen, M.
Source Computers and Operations Research 39 (2012)2. - ISSN 0305-0548 - p. 291 - 298.
Department(s) Operations Research and Logistics
Publication type Refereed Article in a scientific journal
Publication year 2012
Keyword(s) traveling salesman problems - assignment
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
There are no comments yet. You can post the first one!
Post a comment
Please log in to use this service. Login as Wageningen University & Research user or guest user in upper right hand corner of this page.