Branch and Bound Methods for the Traveling Salesman Problem

摘要

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.