The m–Peripatetic Salesman Problem (m–PSP) is defined on a undirected graph G = (V, E) where V={1,…, n} is the vertex set, E= {(i, j): i, j ∈ V, i< j is the edge set and (cij) is a cost matrix defined on E. The m–PSP consists of determining m edge–disjoint Hamiltonian cycles of least total cost on G. This article describes seven new heuristics for the m–PSP and compares them with the heuristic proposed by Krarup in 1975.
