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

Bezalel Gavish and Kizhanathan Srikanth
Additional contact information
Bezalel Gavish: University of Rochester, Rochester, New York
Kizhanathan Srikanth: University of Illinois, Chicago, Illinois

Operations Research, 1986, vol. 34, issue 5, 698-717

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 (search for similar items in EconPapers)
Date: 1986
References: Add references at CitEc
Citations: View citations in EconPapers (12)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.34.5.698 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:34:y:1986:i:5:p:698-717

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().