Simple Patch: A New Heuristic for the Product Traveling Salesman Problem

摘要

The paper describes the heuristic Simple Patch and compares it to otherheuristics for the product Traveling Salesman Problem (TSP). Besides the well-known heuristics for the Euclidean TSP and the heuristic Uniflow, these heuristics include an algorithm of Gilmore and Gomory. Section 2 introduces some terminology and basic concepts used. In Section 3, solvable cases of the product TSP are considered. We give proof of the fact that the improvement algorithm 2-Opt (starting with an arbitrary tour) yields an optimal solution for the symmetric product TSP in polynomial time. Section 4 describes heuristics for the product TSP based on the idea of subtour patching. In Section 5, we give worst case analyses of the three subtour patching heuristics and a complexity analysis of the heuristic Simple Patch. The results of a computational experiment are presented in Section 6. Finally, we draw some conclusions in Section 7.