On location-routing formulations for the Hamiltonian p-median problem

Given a positive integer p and a weighted undirected graph G=(V,E), the Hamiltonian p-Median Problem (HpMP) on G is to find a minimum weight set of p elementary cycles partitioning V. We study extended formulations for this problem including node-depot assignment (NDA) variables, in addition to edge variables. These formulations are based on the selection of certain nodes as depots and thus can be viewed as formulations for location-routing problems. Known NDA formulations and valid inequalities are reviewed, and new extended formulations, including edge-depot assignment (EDA) variables, are presented. We relate EDA formulations with known NDA formulations and, from the former, derive new exponentially sized sets of constraints defined with the edge and NDA variables. Computational results show that the EDA formulations produce very strong lower bounds and are effective for instances with up to 100 nodes and large values of p, and that the branch-and-cut algorithms based on NDA formulations including (some of) the generalized constraints are competitive with (and often outperform) the current state of the art (which involves solving instances with up to 400 nodes). We also address and present computational results for a variant of the HpMP in which setup costs for depots are considered.