Improved polyhedral descriptions and exact procedures for a broad class of uncapacitated p-hub median problems. (May 2019)

• Record Type: Journal Article
• Authors: Corberán, Ángel; Landete, Mercedes; Peiró, Juanjo; Saldanha-da-Gama, Francisco
• Is Part Of: Transportation research. Volume 123(2019)
• Page Start: 38
• Page End: 63
• Publication Date: 2019-05
• Subjects: Hub location -- Non-stop services -- Set packing polytope -- Branch and cut; Transportation -- Research -- Periodicals; Transportation -- Mathematical models -- Periodicals
• DOI: 10.1016/j.trb.2019.03.007
• Languages: English
• ISSNs: 0191-2615

Abstract

Highlights: A broad family of hub location problems is investigated. Improved formulations are proposed and discussed. A polyhedral study is conducted rendering many facet-defining inequalities. Additional valid inequalities are derived, whose separation is analyzed. A cutting-plane approach and a branch-and-cut algorithm are devised. 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 proposed 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 algorithms 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.