Technical Note—An Improved Transformation of the Symmetric Multiple Traveling Salesman Problem

Roy Jonker and Ton Volgenant
Additional contact information
Roy Jonker: University of Amsterdam, The Netherlands
Ton Volgenant: University of Amsterdam, The Netherlands

Operations Research, 1988, vol. 36, issue 1, 163-167

Abstract: We improve the standard transformation of the symmetric, single-depot, multiple traveling salesman problem (MTSP) to one on a sparser edge configuration. The improvement tends to suppress, to a large extent, the degeneracy of the resulting symmetric traveling salesman problem (TSP). As a result, a 1-tree based TSP algorithm solves large MTSPs of the type we consider as easily as it solves standard TSPs. We demonstrate the improvement by presenting computational results that are currently the best available.

Keywords: 490 multiple traveling salesman problem; 630 minimal 1-tree-based algorithm; 837 vehicle routing (search for similar items in EconPapers)
Date: 1988
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.36.1.163 (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:36:y:1988:i:1:p:163-167

Access Statistics for this article

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