A branch and bound algorithm for symmetric 2-peripatetic salesman problems (Q1310005)

The symmetric 2-peripatetic salesman problem (2-PSP) is an extension of the symmetric travelling salesman problem in the sense that 2 edge- disjoint Hamiltonian cycles of minimum total length arc required in a graph with \(n\) vertices. A branch-and-bound algorithm is developed based on the procedures to solve symmetric problems. Lower bound solutions are provided by 2 minimum length edge-disjoint 1-trees (in \(O(n^ 2\log(n))\) operations). Generating upper bound solutions and executing edge elimination tests takes \(O(n^ 2)\) operations. Computational results are available for Euclidean problems up to 60 vertices and problems with randomly generated distance matrices up to 130 vertices.