Improvements to the Or-opt heuristic for the symmetric travelling salesman problem

Abstract

Several variants and generalizations of the Or-opt heuristic for the Symmetric Travelling 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.

Keywords:

• symmetric travelling salesman problem
• local search heuristics
• edge and chain exchanges

Acknowledgements

This research was partially supported by the Canadian Natural Sciences and Engineering Research Council under grants 155899-03 and OGP0039682. This support is gratefully acknowledged. We thank the two referees for their valuable comments.