Branch and Bound Methods for the Traveling Salesman Problem
CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
Pagination or Media Count:
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.
- Statistics and Probability