Lower bounds for symmetric<i>K</i>-peripatetic salesman problems

Abstract

Abstract The criterion of the KPeripatetic Salesman (K-PSP) is to minimize the total length of K edge-disjoint Hamiltonian cycles. We describe a method to compute lower bounds for the kPSP. To obtain these bounds a simple transformation of the distance matrix is executed, followed by the addition of a set of constraints. Computational results with respect to Euclidean and randomly generated instances are given for the 2-PSP. Also upper and lower bounds are computed by using optimal TSP solutions. In general the description method to compute lower bound values outperforms the TSP based lower bound values. Keywords: k-peripatetic salesman problemgraphsroutingtransportation problemAMS 1980 Subject Classifications: Primary: 90C08Secondary: 05C38