Solutions for districting problems with chance-constrained balancing requirements

In this paper, a districting problem with stochastic demands is investigated. The goal is to divide a geo-graphic 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 to-tal 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 deter-ministic equivalent for the problem, a two-phase heuristic is developed. In the first phase, the chance-constraints are ignored and a feasible solution is constructed for the relaxed problem; in the second phase, the solution is corrected if it does not meet the chance-constraints. In this case, a simulation pro-cedure is proposed for estimating the probability of a given solution to yield a balanced districting. That procedure also provides information for guiding the changes to make in the solution. The results of a series of computational tests performed are discussed based upon a set of testbed instances randomly generated. Different families of probability distributions for the demands are also investigated, namely: Uniform, Log-normal, Exponential, and Poisson. (c) 2021 Elsevier Ltd. All rights reserved.

Automated summary

This paper investigates a districting problem with stochastic demands, aiming to find a balanced division with given probability. A two-phase heuristic method is developed, along with a simulation procedure to estimate the probability of balanced districting. Different probability distributions for demands are also explored.