Accession Number:

ADA237878

Title:

An Exact Two-Matching Based Branch and Bound Algorithm for the Symmetric Traveling Salesman Problem

Descriptive Note:

Research rept.,

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA GRADUATE SCHOOL OF INDUSTRIAL ADMINISTRATION

Report Date:

1991-02-01

Pagination or Media Count:

13.0

Abstract:

An algorithm is described for the symmetric traveling salesman problem TSP based on a bipartite two-matching lower bounding technique. The lower bound is strengthened by using the bipartite two-matching as the basis for a heuristic algorithm for the dual of integer two-matching. We use this dual as a lower bound for the symmetric traveling salesman problem in a branch and bound algorithm. Results are presented for random symmetric TSPs with up to 3000 cities. On Euclidean problems the two-matching bound is weaker than on random problems and algorithm performance deteriorates as a result. The algorithm successfully solves 11 of 15 Euclidean problems from the literature with sizes ranging from 17 to 99 cities.

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE