  


Revisiting the Hamiltonian pmedian problem: a new formulation on directed graphs and a branchandcut algorithm
Tolga Bektaş (t.bektassoton.ac.uk) Abstract: This paper studies the Hamiltonian pmedian 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 socalled path elimination constraints that arise in multidepot/locationrouting 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 branchandcut 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 twonode circuits are not allowed suggest that the algorithm is competitive with stateoftheart methods. Keywords: Combinatorial optimization; Hamiltonian pmedian; multicut inequalities; multidepot routing; branchandcut 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 Download: [PDF] Entry Submitted: 03/06/2018 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  