Technical Note—An Effective Heuristic for the M -Tour Traveling Salesman Problem with Some Side Conditions

Robert A. Russell
Additional contact information
Robert A. Russell: University of Tulsa, Tulsa, Oklahoma

Operations Research, 1977, vol. 25, issue 3, 517-524

Abstract: This note presents a heuristic for determining very good solutions for the symmetric M -tour traveling salesman problem with some side conditions. These side conditions' pertain to load, distance and time, or sequencing restrictions. The heuristic is an extension of the highly successful one of Lin and Kernighan for the single traveling salesman problem. Computational experience with widely tested vehicle dispatch problems indicates that the proposed heuristic consistently yields better solutions than existing heuristics that have appeared in the literature. Run times grow approximately as N 2.3 , where N is the number of cities. The heuristic is generally slower than the modified SWEEP heuristic except on problems having a large number of points per route.

Date: 1977
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.25.3.517 (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:25:y:1977:i:3:p:517-524

Access Statistics for this article

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