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

G-2005-02

Improvements to the Or-opt Heuristic for the Symmetric Traveling Salesman Problem

, et

Several variants and generalizations of the Or-opt heuristic for the Symmetric Traveling Salesman Problem are developed and compared on random and planar instances. Some of the proposed algorithms are shown to significantly improve upon the standard 2-opt and Or-opt heuristics.

, 14 pages