An Optimal Solution Method for Large-Scale Multiple Traveling Salesmen Problems
Bezalel Gavish, Kizhanathan Srikanth
Operations Research · 1986 · Volume 34 · Issue 5
Abstract
We develop an efficient branch-and-bound based method for solving the Multiple Traveling Salesman Problem, and develop lower bounds through a Lagrangean relaxation that requires computing a degree-constrained minimal spanning tree. A subgradient optimization procedure updates the Lagrange multipliers. We use fast sensitivity analysis techniques to increase the underlying graph sparsity and reduce the problem size. The algorithm was tested on 416 problems with up to 500 cities and 10 salesmen. We also present computational results on different data sets and parameters in order to identify the major factors that influence the performance of the developed code.
Keywords
491 Lagrangean relaxation and branch-and-bound, 627 traveling salesman problem
Enable JavaScript for citation tools and additional paper interactions.