A new formulation for the Hamiltonian p-median problem
Abstract: This paper concerns 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 resulting from the intersection of two subproblems. The first subproblem states that at most p circuits are required, that 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, 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 to solve asymmetric instances with up to 150 nodes and symmetric instances with up to 100 nodes using the new formulation.
Keywords: Combinatorial optimization; Hamiltonian p-median; multi-cut inequalities; multi-depot routing; branch-and-cut algorithm.
Category 1: Combinatorial Optimization (Branch and Cut Algorithms )
Category 2: Integer Programming ((Mixed) Integer Linear Programming )
Category 3: Applications -- OR and Management Sciences (Transportation )
Citation: Working paper - CMAFCIO
Entry Submitted: 03/06/2018
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|