A Fast Composite Heuristic for the Symmetric Traveling Salesman Problem

This article describes a new composite heuristic for the symmetric Traveling Salesman Problem. The heuristic consists of three phases: construction of an initial envelope, insertion of the remaining vertices, and improvement procedure. The heuristic is shown to perform very well both on randomly generated instances and on TSPLIB problems.