Accession Number:

ADA126957

Title:

Branch and Bound Methods for the Traveling Salesman Problem

Descriptive Note:

Technical rept.

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP

Personal Author(s):

Report Date:

1983-03-01

Pagination or Media Count:

71.0

Abstract:

This paper reviews the state of the art in enumerative solution methods for the traveling salesman problem TSP. The introduction Section 1 discusses the main ingredients of branch and bound methods for the TSP. Sections 2, 3 and 4 discuss classes of methods based on three different relaxations of the TSP the assignment problem with the TSP cost function, the 1-tree problem with a Lagrangian objective function, and the assignment problem with a Lagrangean objective function. Section 5 briefly reviews some other relaxations of the TSP, while Section 6 discusses the performance of some state of the art computer codes. Besides material from the literature, the paper also includes the results and statistical analysis of some computational experiments designed for the purposes of this review.

Subject Categories:

  • Statistics and Probability

Distribution Statement:

APPROVED FOR PUBLIC RELEASE