An Optimal Solution Method for the Multiple Travelling Salesman Problem

A new optimal solution method for the Multiple Travelling Salesman Problem is developed. A Lagrangean relaxation which requires the computation of a degree-constrained minimal spanning tree is utilized, and the Lagrangean multipliers are updated by the subgradient optimization method. Fast sensitivity analysis techniques are used to increase graph sparsity and reduce the problem size. The algorithm has been tested on problems with up to 400 cities and 10 salesmen. Work is in progress on an improved version of the algorithm that holds promise of being able to solve even larger problems