The Hamiltonian p-median problem (Q918861)

The Hamiltonian p-median problem is to locate p depots to serve a given set of customers through p distinct Hamiltonian cycles at minimal total distribution cost. This may be modeled as a set partitioning problem with cost of a subset equal to the length of a shortest circuit of the subset. The paper describes several heuristic solution procedures: a clustering method which builds a solution, a 3-optimal improvement method, a solution building method based on the 2-matching relaxation, and a modification of the spanning walk heuristic for the travelling salesman problem, applicable only to planar problems. These methods are tested on several random test problems.