Revisiting the Hamiltonian p-median problem: A new formulation on directed graphs and a branch-and-cut algorithm

Tolga Bektaş, Luís Gouveia and Daniel Santos

European Journal of Operational Research, 2019, vol. 276, issue 1, 40-64

Abstract: This paper studies the asymmetric Hamiltonian p-median problem, which consists of finding p mutually disjoint circuits of minimum total cost in a directed graph, such that each node of the graph is included in one of the circuits. Earlier formulations view the problem as the intersection of two subproblems, one requiring at most p, and the other requiring at least p circuits, in a feasible solution. This paper makes an explicit connection between the first subproblem and subtour elimination constraints of the traveling salesman problem, and between the second subproblem and the so-called path elimination constraints that arise in multi-depot/location-routing problems. A new formulation is described that builds on this connection, that uses the concept of an acting depot, resulting in a new set of constraints for the first subproblem, and a strong set of (path elimination) constraints for the second subproblem. The variables of the new model also allow for effective symmetry-breaking constraints to deal with two types of symmetries inherent in the problem. The paper describes a branch-and-cut algorithm that uses the new constraints, for which separation procedures are proposed. Theoretical and computational comparisons between the new formulation and an adaptation of an existing formulation originally proposed for the symmetric Hamiltonian p-median problem are presented. Computational results indicate that the algorithm is able to solve asymmetric instances with up to 171 nodes and symmetric instances with up to 100 nodes.

Keywords: Combinatorial optimization; Hamiltonian p-median; Multi-cut inequalities; Multi-depot routing; Branch-and-cut algorithm (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221718311159
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:276:y:2019:i:1:p:40-64

DOI: 10.1016/j.ejor.2018.12.041

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().