Approximation schemes for districting problems with probabilistic constraints

In this work a districting problem with stochastic demand is investigated. Chance-constraints are used to model the balancing requirements. Explicit contiguity constraints are also considered. After motivating the problem and discussing several modeling aspects, an approximate deterministic counterpart is proposed which is the core of new solution algorithms devised. The latter are based upon a location-allocation scheme, whose first step consists of considering either a problem with a sample of scenarios or a sample of single-scenario problems. This leads to two variants of a new heuristic. The second version calls for the use of a so-called attractiveness function as a means to find a good trade-off between the (approximate) solutions obtained for the single-scenario problems. Different definitions of such functions are discussed. Extensive computational tests were performed whose results are reported.