A Subtour Elimination Algorithm for the Bottleneck Traveling Salesman Problem.

摘要

In this paper we propose a LIFO implicit enumeration algorithm for the bottleneck traveling salesman problem which uses the bottleneck assignment problem as a relaxation. We also present computational experience on a UNIVAC 1108 with symmetric and asymmetric problems, ranging in size from 30 to 2000 nodes. Our results indicate that for asymmetric problems the time requirement of the proposed algorithm grows slower than the square of the problem size -- i.e. the algorithm is empirically good (in the sense of Edmonds). (Author)