An Effective Tour Construction and Improvement Procedure for the Traveling Salesman Problem
Operations Research · 1995 · Volume 43 · Issue 6
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
Enable JavaScript for citation tools and additional paper interactions.