Bounds for the symmetric 2-peripatetic salesman problem

Abstract

The 2-Peripatetic Salesman Problem (2-PSP) minimizes the total length of 2 edge-disjoint Hamil-tonian cycles. This type of problems arises in designing communication or computer networks, or whenever one aims to increase network reliability using disjoint tours. The NP-hardness of the 2-PSP is shown. Lower bound values are obtained by generalizing the 1-tree approach for the TSP to a 2 edge-disjoint 1-trees approach for the 2-PSP. One can construct 2 edge-disjoint 1-trees using a greedy algorithm, into which a partitioning procedure is incorporated that runs O(n 2 log n) time. Upper bound solutions are obtained by two heuristics based on a lower bound solution and by a modified Savings heuristic for problems up to 140 cities.