A LIFO Implicit Enumeration Algorithm for the Asymmetric Traveling Salesman Problem Using a One-Arborescence Relaxation.

摘要

The author proposes a LIFO implicit enumeration algorithm for the asymmetric traveling salesman problem in which the one-arborescence relaxation of the traveling salesman problem (originally suggested by Held and Karp) is employed as a fathoming device. The efficient Edmonds-Fulkerson algorithm is used to construct minimum-cost arborescences. Computational exerpience with the algorithm is also presented.