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

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.