Ángel Corberán (University of Valencia), Mercedes Landete (University Miguel Hernández of Elche), Juanjo Peiró (University of Valencia) and Francisco Saldanha-da-Gama (University of Lisboa).
Abstract. This work focuses on a broad class of uncapacitated p -hub median problems that includes non-stop services and setup costs for the network structures. In order to capture both the single and the multiple allocation patterns as well as any intermediate case of interest, we consider the so-called r -allocation pattern with r denoting the maximum number of hubs a terminal can be allocated to. We start by revisiting an optimization model recently pro- posed for the problem. For that model, we introduce several families of valid inequalities as well as optimality cuts. Moreover, we consider a relaxation of the model that contains several sets of set packing constraints. This motivates a polyhedral study that we perform and that leads to the identification of many families of facets and other valid inequalities to the relaxed problem that, in turn, provide valid inequalities for the original model. Some of these families are too large for being handled directly. For those cases, separation algo- rithms are also presented. Finally, we gather all the above elements in a branch-and-cut procedure that we devise and implement for tackling the problem. The methodological developments proposed are tested computationally using data generated from the well- known AP data set.
Keywords. Hub location; Non-stop services; Set packing polytope; Branch and cut
Categories: Scientific articles