Technical Note—An Improved Transformation of the Symmetric Multiple Traveling Salesman Problem
Operations Research · 1988 · Volume 36 · Issue 1
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
Enable JavaScript for citation tools and additional paper interactions.