Abstract
The 2-peripatetic Salesman Problem (2-PSP for short) is the problem. where 2 edge-disjoint Hamiltonian cycles of minimal to tallength are required. We have investigated whether the 2-PSP, either the sum version or the bottleneck version can also be wellsolved in known well-solved cases of the TSP.
We show how to polynomially solve the 2-PSP in the following non-trivial cases:
— Problems on Small matrices with distinct values for the sum as wellx as for the bottleneck criterion;
— Problems on asymmetric Circulant matrices with a prime number of cities again for both criteria;
— Problems with the bottleneck criterion on max-distribution matrices with the number of negative a-values equal to the number of nonnegative b-values.