This Article Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Gavish, B. Articles by Srikanth, K. Search for Related Content

An Optimal Solution Method for Large-Scale Multiple Traveling Salesmen Problems

University of Rochester, Rochester, New York
University of Illinois, Chicago, Illinois

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.

Subject classifications: 491 Lagrangean relaxation and branch-and-bound; 627 traveling salesman problem.

This article has been cited by other articles:

				P. Schermerhorn and M. Scheutz Investigating the Adaptiveness of Communication in Multi-Agent Behavior Coordination Adaptive Behavior, December 1, 2007; 15(4): 423 - 445. [Abstract] [PDF]