¹Nanyang Technological University, Singapore

Correspondence: P M E Shutler, Division of Mathematics, School of Science, National Institute of Education Nanyang Technological University, 469 Bukit Timah Road, Singapore 259756. E-mail: shutler@nie.edu.sg

Received March 2000; Accepted August 2000.

Abstract

This paper presents an improvement to an existing branch and bound algorithm for solving the symmetric travelling salesman problem. The lower bound used is the standard one obtained from the sequence of minimal spanning 1-trees computed via subgradient optimization, but the branching rule is new. Rather than selecting for inclusion or exclusion those edges which violate the tour constraints in the final 1-tree of the sequence, we consider edges which are present in roughly half of the final few 1-trees. This results in a decision tree whose number of nodes grows by powers of two rather than three, hence significantly reducing the total number of decision nodes required to solve the problem.