Technical Note—Bounds for the Travelling-Salesman Problem

Abstract

This paper concerns finding a tight lower bound to the travelling-salesman problem, with the hope that all the different branch-and-bound algorithms for this problem can benefit from it. The bound is calculated by an iterative procedure with guaranteed convergence and is shown to require a computation time only about 9 per cent greater than the time required to solve an equivalent assignment problem. This new bound was tested on 14 sample problems and, on the average, found to be only 4.7 per cent below the optimum for symmetrical, and 3.8 per cent below the optimum for asymmetrical problems.