1999 | OriginalPaper | Buchkapitel
A Study of Branch-and-Bound on the Asymmetric Traveling Salesman Problem
verfasst von : Weixiong Zhang
Erschienen in: State-Space Search
Verlag: Springer New York
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
One of the approaches for optimally solving the asymmetric Traveling Salesman Problem (ATSP) is branch-and-bound subtour elimination using the assignment problem as a lower-bound cost function [10, 7]. This chapter studies the complexity of branch-and-bound subtour elimination on the asymmetric Traveling Salesman Problem. In Section 6.1, we first examine two-decade old arguments about the expected complexity of branch-and-bound subtour elimination, and shows that the branch-and-bound subtour elimination cannot find an optimal solution to the asymmetric Traveling Salesman Problem in polynomial time on average. This partially settles this long-standing debate on the expected complexity of branch-and-bound on the asymmetric Traveling Salesman Problem. Section 6.4 then compares depth-first branch-and-bound against local search, and shows that depth-first branch-and-bound significantly outperforms a local search algorithm.