Fast Heuristics for Large Geometric Traveling Salesman Problems

Very frequently in practical applications we are faced with large or very large scale traveling salesman problems where the number of cities may range from several hundreds or thousands up to even millions. Due to timing restrictions in the production process there may be situations where good approximative solutions to an instance of the traveling salesman problem have to be found very fast, and where it is not feasible to call even O(n²) time procedures too often. In this paper we discuss several ideas to handle such large traveling salesman problems under time restrictions. We will consider Euclidean traveling salesman problems in the plane and show how their geometric structure can be exploited to derive fast heuristics.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.