Improved polyhedral descriptions and exact procedures for a broad class of uncapacitated p-hub median problems
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 pol…
The facility location problem with capacity transfers
Abstract This paper explores the concept of capacity transfer in the context of capacitated facility location problems. This is accomplished by assuming that facilities with surplus capacity/production can cooperate with those facing shortage by transferring part of that capacity/production. Such a transfer incurs a cost that nonetheless may be compensated by savings both in the installation costs and in the distribution costs. Mixed-integer mathematical programming models are proposed for the problem. A distinction is made between the case in which the triangle inequality holds for the transfer costs and the case in which it does not. We present compact models, which are enhanced with vali…
Heuristic Solutions for a Class of Stochastic Uncapacitated p-Hub Median Problems
In this work, we propose a heuristic procedure for a stochastic version of the uncapacitated r-allocation p-hub median problem with nonstop services. In particular, we assume that the number of hubs to which a terminal can be allocated is bounded from above by r. Additionally, we consider the possibility of shipping traffic directly between terminals (nonstop services). Uncertainty is associated with the traffic to be shipped between nodes and with the transportation costs. If we assume that such uncertainty can be captured by a finite set of scenarios, each of which with a probability known in advance, it is possible to develop a compact formulation for the deterministic equivalent proble…
Solutions for districting problems with chance-constrained balancing requirements
Abstract In this paper, a districting problem with stochastic demands is investigated. The goal is to divide a geographic area into p contiguous districts such that, with some given probability, the districts are balanced with respect to some given lower and upper thresholds. The problem is cast as a p -median problem with contiguity constraints that is further enhanced with chance-constrained balancing requirements. The total assignment cost of the territorial units to the representatives of the corresponding districts is used as a surrogate compactness measure to be optimized. Due to the tantalizing purpose of deriving a deterministic equivalent for the problem, a two-phase heuristic is d…