A Connected M-Tree Relaxation for M-Travelling Salesmen Problems

Abstract

Utilizing branch-and-bound and relaxation techniques to solve large scale m-travelling salesmen problems to optimum needs strong lower bound procedures. Since the landmark 1-tree relaxation model devised by Held and Karp for travelling salesman problems, some relaxation models, such as: m-trees, augmented degree-constrained spanning trees have been developed for the solution of m-travelling salesman problem. This paper presents a new graphical structure, denoted as connected m-tree, to be a more promising relaxation model for m-travelling salesmen problems. Model, algorithm, and computational results are reported.