Groupe d’études et de recherche en analyse des décisions

G-91-25

A Line-clustering Heuristic for the Euclidean Planar TSP

et

This paper presents a new heuristic for the Euclidean planar traveling salesman problem. The heuristic takes advantage of the natural alignment of the points to visit. This situation is very frequent in the insertion of components on printed circuit boards, in punching flat metal, and in other applications. Given a set of points to visit, the heuristic looks for alignments by deleting some edges of the minimum spanning tree. In a second phase, the lines are reassembled to obtain a Hamiltonnian path.

, 22 pages