A branch and bound algorithm for symmetric 2-Peripatetic Salesman Problems

The symmetric 2-Peripatetic Salesman Problem is an extension of te well-known symmetric Traveling Salesman Problem in the sense that 2 edge-disjoint Hamiltonian cycles of minimum total length are required in a graph G with n vertices. Lower bound solutions are provided by 2 minimum length edge-disjoint 1-trees which can be constructed in at most O(n²logn) operations if G is complete. Generating upper bound solutions and executing edge elimination tests takes O(n²) time. A branch and bound algorithm has been developed based on these procedures to solve symmetric problems. Computational results are available for Euclidean problems up to 60 vertices and problems with randomly generated distance matrices up to 130 vertices.