An Effective Tour Construction and Improvement Procedure for the Traveling Salesman Problem

Geoffrey Zweig
Additional contact information
Geoffrey Zweig: International Computer Science Institute, Berkeley, California

Operations Research, 1995, vol. 43, issue 6, 1049-1057

Abstract: This paper presents an effective neighborhood structure for the traveling salesman problem. The neighbors of a tour are defined as the tours that can be produced by breaking the initial tour into two closed subtours, rejoining the subtours in a new configuration, and finally performing local optimization around all the changed edges. This process of generating a neighbor is termed divide and merge . Neighbor lists are used to develop variants of divide and merge that require linear and constant time per iteration, as well as an O ( Nln ( N )) tour construction algorithm based on insertion into the convex hull.

Keywords: networks/graphs; traveling salesman; heuristics; tour construction; and tour improvement (search for similar items in EconPapers)
Date: 1995
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.43.6.1049 (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:43:y:1995:i:6:p:1049-1057

Access Statistics for this article

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