This paper studies the Hamiltonian p-median problem defined on a directed graph, which consists of finding p mutually disjoint circuits of minimum total cost, such that each node of the graph is included in one of the circuits. Earlier formulations are based on viewing the problem as one resulting from the intersection of two subproblems. The first subproblem states that at most p circuits are required, which are usually modeled by using subtour elimination constraints known from the traveling salesman problem. The second subproblem states that at least p circuits are required, for which this paper makes an explicit connection to the so-called path elimination constraints that arise in multi-depot/location-routing problems. A new extended formulation is proposed that builds on this connection as well as on the concept of acting depot, and that allows the derivation of a stronger set of subtour elimination constraints for the first subproblem, and implies a stronger set of path elimination constraints for the second subproblem. The paper describes separation routines for the two sets of constraints that are used in a branch-and-cut algorithm. The variables in the new model also allow for an effective way of dealing with two types of symmetries inherent in this problem, those induced by the use of the concept of an acting depot and those based on the two possible orientations for a given circuit. Computational results on symmetric cost instances where two-node circuits are not allowed suggest that the algorithm is competitive with state-of-the-art methods.
Citation
https://doi.org/10.1016/j.ejor.2018.12.041