• Login
    View Item 
    •   IIMA Institutional Repository Home
    • Faculty Publications (Bibliographic)
    • Journal Articles
    • View Item
    •   IIMA Institutional Repository Home
    • Faculty Publications (Bibliographic)
    • Journal Articles
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Tolerance-based branch and bound algorithms for the ATSP

    Thumbnail
    View/Open
    Tolerancebasedbranch.pdf (519.8Kb)
    Date
    2008-11-09
    Author
    Turkensteen, M.
    Ghosh, Diptesh
    Goldengorin, B.
    Sierksma, G.
    Metadata
    Show full item record
    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.
    URI
    http://hdl.handle.net/11718/10188
    Collections
    • Journal Articles [3738]

    DSpace software copyright © 2002-2016  DuraSpace
    Contact Us | Send Feedback
    Theme by 
    Atmire NV
     

     

    Browse

    All of IIMA Institutional RepositoryCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    Login

    Statistics

    View Usage Statistics

    DSpace software copyright © 2002-2016  DuraSpace
    Contact Us | Send Feedback
    Theme by 
    Atmire NV