An effective tour construction and improvement procedure for the traveling salesman problem
成果类型：
Article
署名作者：
Zweig, G
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.43.6.1049
发表日期：
1995
页码：
1049-1057
关键词：
摘要：
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.