Towards a stochastic programming modeling framework for districting

Abstract

In this paper a stochastic districting problem is investigated. Demand is assumed to be represented by a random vector with a given joint probability distribution function. A two-stage mixed-integer stochastic programming model is proposed. The first stage comprises the decision about the initial territory design: the districts are defined and all the territory units assigned to one and exactly one of them. In the second stage, i.e., after demand becomes known, balancing requirements are to be met. This is ensured by means of two recourse actions: outsourcing and reassignment of territory units. The objective function accounts for the total expected cost that includes the cost for the first-stage territory design plus the expected cost incurred at the second stage by outsourcing and reassignment. The (re)assignment costs are associated with the distances between territory units, i.e., the focus is put on the compactness of the solution. The model is then extended in different ways to account for aspects of practical relevance such as a maximum desirable dispersion, reallocation constraints, or similarity of the second-stage solution w.r.t. the first-stage one. The new modeling framework proposed is tested computationally using instances built using real geographical data.

1 Introduction

Districting Problems (DPs) aim at partitioning a set of basic geographic areas, named Territorial Units (TUs), into a set of clusters, called districts, according to some criteria. The latter typically refer to balancing, which expresses the need for districts of equitable size in terms of dimension, as well as to topological properties like contiguity and compactness. Contiguity means that in order to travel between TUs in the same district there is no need to cross other districts. A contiguity requirement is relevant for dealing appropriately with enclaves (a district within a district). A good districting plan does not contain enclaves. Compactness indicates that a district is somewhat round-shaped and undistorted (Kalcsics and Ríos-Mercado 2019). Nevertheless, other relevant criteria in DPs include respecting natural boundaries, existing administrative subdivisions, similarity w.r.t existing districting plans, and socio-economic and cultural homogeneity (Bozkaya et al. 2003; Kalcsics et al. 2005; Kalcsics and Ríos-Mercado 2019).

The relevance of DPs resides in the strategic and long-term nature of the decisions involved, motivated by a wide spectrum of practical applications arising in different sectors. DPs have been extensively applied to tackle problems emerging in the context of political districting (Ricca and Simeone 2008; Ricca et al. 2013) and in strategic service planning and management like health-care (Blais et al. 2003; Benzarti et al. 2013), school systems (Ferland and Guénette 1990; Schoepfle and Church 1991; Caro et al. 2004; Bruno et al. 2016a), energy and power distribution networks (Bergey et al. 2003; De Assis et al. 2014; Yanık et al. 2016), police districts (D’Amico et al. 2002), waste collection (Mourão et al. 2009), and transportation (Bruno and Laporte 2002; Tavares et al. 2007). Other core applications of DPs regard the design of commercial areas to be assigned to a given sales force (Zoltners and Sinha 2005; Ríos-Mercado and López-Pérez 2013) and distribution logistics (Zhong et al. 2007).

For extensive reviews on DPs readers are encouraged to refer to Kalcsics et al. (2005) and, for a more up-to-date overview, to Kalcsics and Ríos-Mercado (2019). Given these references, next we focus on some recent contributions found in literature.

Bianchi et al. (2016) and Kim et al. (2017) explore an interesting application of DPs, which consists of the territory design of functional regions. In this kind of problems the hypotheses of complete and exclusive assignment of TUs to districts are relaxed and only clusters with a strong spatial interaction are created. Accordingly, the authors seek to optimize a distance-based compactness measure. The latter is frequently used as an objective function in DPs and represents a good proxy of users’ accessibility to public facilities (Bruno et al. 2017b); it usually leads to shorter travel times when designing distribution areas for service provision (Bender et al. 2016; García-Ayala et al. 2016).

The minimization of maximum territory dispersion, namely the maximum distance between any TU and the center of the districts they are assigned to, is considered in Ríos-Mercado (2016) and Ríos-Mercado and Escalante (2016). Due to the multiplicity of planning goals to be simultaneously achieved, some works adopt a multicriteria setting (Camacho-Collados and Liberatore 2015; Camacho-Collados et al. 2015; Xie and Ouyang 2016).

The objective to be optimized can also be specifically tailored according to the application. For instance, De Fréminville et al. (2015) introduce the so-called Financial Product Districting Problem, where the goal is to partition a set of geographical units in such a way that a cost homogeneity is achieved within the designed territories. Such homogeneity is expressed in terms of the cost variance. Bruno et al. (2016b) define a model to support the rationalization process of public facilities aimed at optimizing the total cost needed to the activation of additional capacities to satisfy the reallocated demand generated by the closure of some facilities. Lin et al. (2017) propose a mixed-integer programming formulation for a problem emerging in the context of home health-care services: the so-called Meals-On-Wheels service districting problem. The goal is to design the minimum number of districts covering all the TUs. Akdoğan et al. (2018) consider the minimization of the mean response time in a problem involving the location of emergency services.

One aspect of practical relevance in DPs is the need to cope with changing demand. This may stem for instance from the expansion of urban areas or migration movements. Depending on the particular problem we are dealing with, different possibilities emerge. One is to assume a reactive posture and solve a so-called redistricting problem. This is an optimization problem that aims at redesigning existing districts. De Assis et al. (2014) tackle such a problem in the context of meter reading in power distribution networks. A bi-objective problem is investigated. The objectives are related with compactness and homogeneity of districts. The authors develop a heuristic algorithm to approximate the Pareto front. Other works dealing with redistricting problems include those by Caro et al. (2004) and Bruno et al. (2017b). In particular, Caro et al. (2004) propose a mathematical model and a GIS-based approach to solve a school redistricting problem, whereas Bruno et al. (2017b) present several formulations to address a redistricting problem emerging in the redesign of administrative boundaries of the Italian provinces.

One alternative to cope with changes in demand is to become proactive and make a decision that directly accounts for such changes. When accurate forecasts are available, we can embed time in the optimization models. To the best of our knowledge, the only papers addressing multi-period territory design are those by Lei et al. (2015), Bender et al. (2016), Lei et al. (2016), and Bender et al. (2018). A multicriteria optimization framework is considered in the first and third works.

Finally, if demand changes are uncertain then embedding uncertainty in the models may be desirable. Assuming that uncertainty can be measured using a probability function a stochastic programming model emerges as appropriate.

To the best of the authors’ knowledge, the existing work closely related to stochastic districting has been developed in the context of vehicle routing problems. In that case,

the problem is cast as a two-stage stochastic program, where districts are designed in the first stage and routing decisions are planned in the second stage, once demands (Haugland et al. 2007) or customers (Lei et al. 2012) are revealed. These are problems in which the districting decisions are triggered by the need to build “good” routes for visiting the customers. In the above studies, tailored heuristic and metaheuristic solution methods are proposed. Stochastic vehicle routing problems based on efficient partitioning procedures of the service region are also exploited by Carlsson (2012) and Carlsson and Delage (2013).

In this paper we introduce a Stochastic Districting Problem with Recourse (SDPR) aiming at partitioning a given set of TUs into a previously given number of clusters in order to maximize the overall compactness while meeting balancing constraints, expressed in terms of average demand per district. The demand associated to each TU is is represented by a random variable. Districts are created in the first stage by allocating the basic areas to those TUs chosen as representative of the districts (centers). In the second stage, two recourse actions are considered: (i) outsourcing shortage/surplus demand; (ii) solving a redistricting problem.

The new modeling framework we propose can be useful to solve practical problems, namely: (i) problems emerging in the context of service districting, where the need to provide users with high service levels and fair accessibility conditions is a top priority for decision makers (schools, hospitals, postal and emergency services); (ii) problems aiming at redesigning political and administrative boundaries; (iii) planning of sales territory where demands for goods and services can be highly unpredictable.

Changing conditions in the labor market, the phenomenon of migratory flows and the strong impact of technology development on customers’ habits and behaviors, are examples of triggering factors that may push towards profound reorganization processes to meet new socio-economic and cultural homogeneity requirements and future demand trends (ESPAS, 2015). In all these cases, it is desirable to devise a plan able to hedge against uncertainty.

The contribution of this paper to the literature is fourfold: (i) to introduce a new modeling framework for a two-stage stochastic districting problem; (ii) to embed redistricting decisions as a way to hedge against uncertainty; (iii) to show the relevance of capturing stochasticity in districting problems; (iv) to show that the new models proposed in this paper make sense i.e., lead to plausible solutions.

Due to the strong connection between districting problems and facility location problems, we refer the reader to the book chapter by Correia and Saldaha-da-Gama (2019) and to the references therein for an overview on discrete stochastic facility location problems. Throughout the current paper we emphasize the specific aspects emerging in the context of districting.

The remainder of this paper is organized as follows: in Sect. 2 we introduce an optimization model for stochastic districting with outsourcing. This model is extended in Sect. 3 where the redistricting is assumed as a recourse action. In Sect. 4 we discuss the relevance of considering a stochastic modeling framework for our problem. Some extensions to the base model are then discussed in Sect. 5. Section 6 reports on the computational tests performed for assessing the relevance of our findings. Then, the paper ends with an overview of the work done and the main conclusions drawn from it.

2 A stochastic districting problem with outsourcing

In this section we introduce a first stochastic districting problem. For modeling purposes our starting point is the model proposed by Hess et al. (1965) that we revisit briefly to ensure that this manuscript is self-contained. We start by introducing some notation that we adapt when necessary according to the specific problem we are investigating.

We consider a set I of territorial units (TUs) that we want to divide into a fixed number, say p, of districts. Each district has a representative TU. Hence, when some other TU is assigned to the district we abuse the language and say that we are assigning a TU to the representative of the district. Single-assignment is assumed for the TUs as customary in districting problems. Additionally, we consider the following parameters:

$d_i$,	demand of TU i ($i \in I$);
$c_{ij}$,	cost for assigning TU i to TU j ($i,j \in I$);
$\mu$,	target value for the demand in every district.
	Typically $\mu = (1/p) \sum _{i \in I} d_i$, which we are also assuming unless stated otherwise. $\alpha$, maximum desirable deviation of the demand in a district w.r.t. the reference value $\mu$. We consider $\alpha \in (0,1)$.

A districting problem was first formulated as an optimization problem by Hess et al. (1965) who considered the following binary variables:

$$\begin{aligned} x_{ij} = {\left\{ \begin{array}{ll} 1, &{} \hbox {if TU} i\,\hbox {is assigned to TU} j;\\ 0, &{} \text{ otherwise }. \end{array}\right. } \qquad {(i,j \in I)} \end{aligned}$$

In this case, $x_{jj}=1$ indicates that TU j is “assigned to itself”, i.e.,

it is selected as the representative of its district.

Using the above decision variables, Hess et al. (1965) proposed the following mathematical model:

$$\begin{aligned}&\text{ minimize }&\quad&\sum _{i \in I} \sum _{j \in I} c_{ij} x_{ij},&\end{aligned}$$

(1)

$$\begin{aligned}&\text{ subject } \text{ to }&\quad&\sum _{j \in I} x_{ij} = 1,&\qquad&i \in I, \end{aligned}$$

(2)

$$\begin{aligned}&&\sum _{j \in I} x_{jj} = p,&\end{aligned}$$

(3)

$$\begin{aligned}&&(1-\alpha ) \mu x_{jj} \le \sum _{i \in I} d_i x_{ij} \le (1+\alpha ) \mu x_{jj},&j \in I, \end{aligned}$$

(4)

$$\begin{aligned}&&x_{ij} \le x_{jj},&i,j, \in I, \end{aligned}$$

(5)

$$\begin{aligned}&&x_{ij} \in \{0,1\},&i,j \in I, \end{aligned}$$

(6)

The objective function (1) quantifies the total cost to be minimized. Constraints (2) ensure that each TU is assigned to exactly one district whereas Constraints (3) guarantee that exactly p districts will be designed. Constraints (4) are the balancing constraints and Inequalities (5) state that we can only assign TUs to representatives of a district. Finally (6) define the domain of the decision variables.

Observing the model we easily conclude that Constraints (5) are redundant in the presence of (4). We are considering them because they will be relevant to ensure the consistency of the stochastic programming models to be presented.

In districting problems, the costs $c_{ij}$ are typically related with the distances (Kalcsics and Ríos-Mercado 2019). Denoting by $\ell _{ij}$ the distance between i and j ($i,j \in I$), a common cost to consider is $c_{ij}=\ell _{ij}$ or $c_{ij}=\ell ^2_{ij}$. This turns the above objective function into a so-called compactness measure known as moment of inertia (Hess et al. 1965). The reader may refer to Kalcsics and Ríos-Mercado (2019) for variants of distance-based compactness measures. In that book chapter, we also observe cost structures that consider the demands as weighting factors. Finally, we note that Euclidean distances are often considered (Bergey et al. 2003; Bard and Jarrah 2009).

Remark 1

The above model does not solve exactly a districting problem but only a relaxation of it; it solves a location-allocation model with a demand balancing requirement. The model ignores one important aspect in districting: contiguity (and consequently the exclusion of enclaves). Therefore, apparently, a solution provided by the model may yield contiguous solutions only by chance. Nevertheless, when we seek to optimize a compactness measure in a districting problem the resulting solution is often strong in terms of contiguity.

It is also true that the introduction of balancing constraints may disfavor compactness and, thus districts’ contiguity. In other words, balancing and compactness may easily become conflicting measures. Despite these facts, most of the authors do not explicitly address contiguity in their models (Kalcsics and Ríos-Mercado 2019). Hence the model proposed by Hess et al. (1965) keeps being the basic model considered in the literature on districting problems.

For this reason, we also consider it as a starting point for the developments proposed in the current paper. $\square$

2.1 A stochastic districting problem with auxiliary recourse decisions

A natural source of uncertainty in districting problems are the demands $d_i$, $i \in I$ and, consequently, the reference value $\mu$ (average demand per district). If the organization of the territory into districts is a here-and-now decision to make (i.e. made before uncertainty is revealed) it is desirable that it hedges against such uncertainty.

Under uncertainty, looking for a solution that is feasible for all the possible future observations (scenarios) of the demand vector $\varvec{\xi }=[d_1,\ldots ,d_{|I|}]$ may be impossible. Even if it is possible, it may lead to a “fat” solution because we may end up planning for realizations that are too extreme although occurring with a very low probability. An alternative is to devise a plan that takes uncertainty into account without being too strict in terms of imposing its feasibility for every “future” but considering some recourse action in case the initial solution is rendered infeasible for the demands actually observed.

The above setting can be looked into in the context of two-stage stochastic programming when $\varvec{\xi }=[d_1,\ldots ,d_{|I|}]$ is a random vector with some known joint cumulative distribution function (e.g. estimated using historical data).

Under uncertainty, the balancing constraints (4) are not well-defined before the actual demands become known. Therefore, we must relax such constraints when looking for a here-and-now solution and assume that extra costs are incurred if, upon observing the actual demand, we realize that in some district it is above [below] the maximum [minimum] threshold. These costs correspond to additional measures due to having unbalanced demand (e.g., outsourcing for surplus demand). As we show next, the deterministic model introduced by Hess et al. (1965) can be reformulated to capture the new setting we are considering.

Let us denote by $g_j$ ($>0$) the extra cost in district j for every unit of demand above the maximum threshold and by $h_j$ ($>0$) the extra cost for every unit of demand below the minimum threshold (w.r.t a here-and-now solution).

Additionally, let us consider two sets of auxiliary variables accounting for the “shortage” and “surplus” demand in each district w.r.t the thresholds initially set:

• $\psi _j$ = demand surplus w.r.t. the maximum threshold, $j \in I$;

• $\varphi _j$ = demand shortage w.r.t. the minimum threshold, $j \in I$;

If the surplus demand is outsourced, the corresponding amount is represented by variables $\psi _j$. The new problem we are dealing with can be formulated mathematically as a two-stage stochastic programming problem:

$$\begin{aligned}&\text{ minimize }&\quad&\sum _{i \in I} \sum _{j \in I} c_{ij} x_{ij} + \mathcal{Q}(\mathbf {x}),&\nonumber \\&\text{ subject } \text{ to }&\quad&{(2)}, {(3)}, {(5)}, {(6)}, \end{aligned}$$

(7)

with $\mathcal{Q}(\mathbf {x})=E_{\varvec{\xi }}[Q(\mathbf {x},\varvec{\xi })]$ and

$$\begin{aligned} Q(\mathbf {x},\varvec{\xi })=&\min&\quad&\sum _{j \in I} g_j \psi _j(\varvec{\xi }) + \sum _{j \in I} h_j \varphi _j(\varvec{\xi }),&\end{aligned}$$

(8)

$$\begin{aligned}&\text{ s. } \text{ t. }&\quad&(1-\alpha ) \mu x_{jj} \le \sum _{i \in I} d_i x_{ij} + \varphi _j(\varvec{\xi }) - \psi _j(\varvec{\xi }) \le (1+\alpha ) \mu x_{jj},&\qquad&j \in I, \end{aligned}$$

(9)

$$\begin{aligned}&&\varphi _j(\varvec{\xi }) \ge 0,&j \in I, \end{aligned}$$

(10)

$$\begin{aligned}&&\psi _j(\varvec{\xi }) \ge 0,&j \in I. \end{aligned}$$

(11)

In the above model, the first stage problem seeks a here-and-now territory design (possibly violating the balancing constraints for some—or all—observations of the demand vector). The second stage model (8)–(11) accounts for the extra cost incurred due to the actual demand observed and given a first-stage decision. Note that in the second-stage model the values of $x_{ij}$ are constants. Although a feasible solution to the second-stage problem may have $\varphi _j>0$ and $\psi _j > 0$ for some $j \in I$, it is easy to see that every optimal solution to that problem will have at most one of those variables above zero (due to $g_j,h_j >0$).

The above stochastic programming problem has simple recourse since the coefficient matrix of the second-stage decision variables is deterministic and can be written as $[\, I \,|\, -I\,]$. In particular, we note that for every here-and-now feasible decision there is a feasible completion in the second stage, which is a nice (and desirable) feature of a stochastic program. Related with this we also note that the values for the variables $\varphi _j(\varvec{\xi })$ and $\psi _j(\varvec{\xi })$ can be trivially obtained for every observation of the underlying random vector. For this reason such variables do not actually correspond to a decision we can make—they are auxiliary variables that help us to formulate the problem in a more elegant way (see Remark 3). For this reason we name the problem we are dealing with as a stochastic districting problem with auxiliary recourse (SDPAR).

We note that $Q(\mathbf {x},\varvec{\xi })$ is a random variable since the quantities $d_i$ (and thus $\mu$) are random variables. By considering its expected value for defining the recourse function $\mathcal{Q}(\mathbf {x})$, we are assuming a so-called neutral attitude of the decision maker towards risk which in our opinion defines a reasonable starting point for the study of stochastic districting problems. Other attitudes towards risk often lead to measures that generalize the one we are considering and thus their analysis should be performed as follow-up to what we are presenting in the current paper.

Finally, we note that like the original model proposed by Hess et al. (1965) this model represents in fact a stochastic location-allocation problem with balancing requirements. Nevertheless, as the computational results presented in Sect. 6 show, it renders plausible solutions to our districting problem.

Assuming a finite support, say $\Xi$, for the random vector $\varvec{\xi }$, we can go farther in terms of the model. In that case, we can index the different scenarios in a finite set, say $S=\{1,\ldots ,|\Xi |\}$. Moreover, we can index in S the stochastic demands, the assignment costs as well as the second-stage decision variables, as follows:

$d_{is}$,	demand of TU $i \in I$ under scenario $s \in S$;
$\varphi _{js}$	demand shortage in district $j \in I$ w.r.t. the minimum threshold under scenario $s \in S$;
$\psi _{js}$	demand surplus in district $j \in I$ w.r.t. the maximum threshold, $j \in I$ under scenario $s \in S$.

We assume that the probabilities associated with the different scenarios are known (for instance estimated using historical data). We define by $\pi _s$ the probability that scenario s occurs, $s \in S$. Naturally, $\pi _s \ge 0$, $s \in S$ and $\sum _{s \in S} \pi _s = 1$. Additionally, we denote by ${\hat{\mu }}$ the reference value to be used in the balancing constraints (to be detailed later).

We can finally write the so-called extensive form of the deterministic equivalent that we call model ($M_1$):

$$\begin{aligned}&\text{ minimize }&\quad&\sum _{i \in I} \sum _{j \in I} c_{ij} x_{ij} + \sum _{s \in S} \pi _s \left( \sum _{j \in I} g_j \psi _{js} + \sum _{j \in I} h_j \varphi _{js} \right) ,&\end{aligned}$$

(12)

$$\begin{aligned} \,&\text{ subject } \text{ to }&\,\quad&{(2)}, {(3)}, {(5)}, {(6)}, \nonumber \\ \,&\,&\,&(1-\alpha ) {\hat{\mu }} x_{jj}\le \sum _{i \in I} d_{is} x_{ij} - \psi _{js} + \varphi _{js} \le (1+\alpha ) {\hat{\mu }} x_{jj},&\, \quad&j \in I, s \in S, \end{aligned}$$

(13)

$$\begin{aligned}&&\varphi _{js} \ge 0,&j \in I, s \in S, \end{aligned}$$

(14)

$$\begin{aligned}&&\psi _{js} \ge 0,&j \in I, s \in S. \end{aligned}$$

(15)

The objective function (12) can be written in a different way:

$$\begin{aligned} \sum _{i \in I} \sum _{j \in I} c_{ij} x_{ij} + \sum _{j \in I} (g_j \sum _{s \in S} \pi _s \psi _{js}) +\sum _{j \in I} (h_j \sum _{s \in S} \pi _s \varphi _{js}), \end{aligned}$$

(16)

Remark 2

In the original model by Hess et al. (1965) the target demand per district is defined as the average demand per district (total demand divided by the number of districts). Under uncertainty, demand is not known beforehand, the same holding with the average demand per district that becomes a random variable. For this reason, in general, the best we can do is to consider the expected average. Considering that uncertainty is captured by a finite number of scenarios such expectation is obtained as follows:

For every scenario $s \in S$, $\sum _{i \in I} d_{is}$ is the total demand under that scenario. Accordingly, $\sum _{s \in S} ( \pi _s \sum _{i \in I} d_{is})$ is the expected total demand. Hence, we get the value we are looking for:

$$\begin{aligned} {\hat{\mu }} = \frac{1}{p} \sum _{s \in S} (\pi _s \sum _{i \in I} d_{is}). \end{aligned}$$

(17)

$\square$

Remark 3

The knowledge about the values of the x-variables as well as of the occurring scenario immediately determines the values of the (auxiliar) variables $\varphi _{js}$ and $\psi _{js}$ ($j \in I$, $s \in S$):

$$\begin{aligned}&\varphi _{js} = \max \left\{ 0 , (1-\alpha ) {\hat{\mu }} x_{jj} - \sum _{i \in I} d_i x_{ij} \right\} , j \in I, s \in S;\\&\psi _{js} = \max \left\{ 0 , \sum _{i \in I} d_i x_{ij} - (1+\alpha ) {\hat{\mu }} x_{jj} \right\} , j \in I, s \in S. \end{aligned}$$

Hence, we could easily reformulate our problem as a single-stage problem. However, we omit this reformulation since it is not helpful when it comes to solving the problem.$\square$

3 A stochastic districting-redistricting problem

In the stochastic model presented in the previous section, a here-and-now decision is made and there is no effective recourse decision. As stated in Remark 3, the second-stage decision variables considered simply help us to account for the costs of having demand surplus or shortage w.r.t. the minimum and maximum thresholds set for the districts.

In practice, it may be relevant to be proactive. This means that upon observing a violation in the balancing constraints in some scenarios, instead of simply taking recourse actions that overcome infeasibilities of the here-and-now solution (and thus accounting for the corresponding costs), we may try to adapt slightly the territory design (the first-stage solution) to the occurring demands. In other words, we may think of performing a so-called redistricting, in line with works such as those by Bruno et al. (2017b), Caro et al. (2004), and De Assis et al. (2014). This is what we propose next.

We still seek to define a fixed number p of districts. This corresponds to a major decision that keeps being done here-and-now. As mentioned before, we may end up facing a scenario for which the demand in some district is above or below the thresholds initially set. In this case, in addition to the recourse actions discussed in the previous section we also consider a “redistricting” recourse decision for some (hopefully just a few) territories. This means that such territories would be included in other district(s) as a reaction to the occurring scenario. This type of recourse action makes sense since it corresponds to a “redistribution” of the demand in order to get an overall balanced solution. The only TUs that cannot be reassigned are those that were set as district representatives by the first stage decision.

We keep assuming that the support of the random vector underlying the problem is finite. Hence, we consider directly scenario-indexed demands. Furthermore, we assume that reassigning a TU incurs an extra cost. We define by $r_{ijs}$ the cost for reassigning the demand of TU i to the district represented by TU j, under scenario $s \in S$. Like for the previous models, the reassignment costs $r_{ijs}$ can be related with the distances. Nevertheless, it may be desirable to “penalize” reassignments. For this extension we consider one additional set of decision variables:

$$\begin{aligned} w_{ijs} = {\left\{ \begin{array}{ll} 1, &{} \hbox {if TU} i\,\hbox {is assigned to district} j under scenario s;\\ 0, &{} \text{ otherwise }. \end{array}\right. } \qquad {(i,j \in I, s \in S)} \end{aligned}$$

In addition to these variables, we consider a set of auxiliary variables that help us to present a linear model: for every $i,j \in I$, $s \in S$, $v_{ijs}$ is a binary variable equal to 1 if the assignment of TU i to TU j under scenario s corresponds actually to a reassignment. More formally, we can define these variables as:

$$\begin{aligned} v_{ijs} = {\left\{ \begin{array}{ll} 1, &{} \hbox {if}\,w_{ijs}=1\,\hbox {and}\,x_{ij}=0;\\ 0, &{} \text{ otherwise }. \end{array}\right. } \qquad {(i,j \in I, s \in S)} \end{aligned}$$

The new problem will be called a Stochastic Districting Problem with Recourse (SDPR). Given all the aspects already discussed as well as the notation above introduced we can directly present the extensive form of the deterministic equivalent denoted by ($M_2$):

$$\begin{aligned} \,&\text{ minimize }&\,&\sum _{i \in I} \sum _{j \in I} c_{ij} x_{ij} \nonumber \\ \,&\,&\,&+ \sum _{s \in S} \pi _s \left( \sum _{i \in I} \sum _{j \in I} r_{ijs} v_{ijs} + \sum _{j \in I} g_j \psi _{js} + \sum _{j \in I} h_j \varphi _{js} \right) , \end{aligned}$$

(18)

$$\begin{aligned} \,&\text{ subjet } \text{ to }&\,&{(2)}, {(3)}, {(5)}, {(6)},{(14)},{(15)},&\, \nonumber \\ \,&\,&\,&\sum _{j \in I} w_{ijs} = 1,&i \in I, \, s \in S \end{aligned}$$

(19)

$$\begin{aligned} \,&\,&\,&(1-\alpha ) {\hat{\mu }} x_{jj}\le \sum _{i \in I} d_{is} w_{ijs} - \psi _{js} + \varphi _{js} \le (1+\alpha ) {\hat{\mu }} x_{jj},&j \in I,\, s \in S, \end{aligned}$$

(20)

$$\begin{aligned} \,&\,&\,&\sum _{\ell \ne j} w_{j\ell s} \le 1-x_{jj},&{j \in I},\, s \in S, \end{aligned}$$

(21)

$$\begin{aligned} \,&\,&\,&v_{ijs} \ge w_{ijs} - x_{ij},&i,j \in I,\, s \in S, \end{aligned}$$

(22)

$$\begin{aligned} \,&\,&\,&v_{ijs} \ge 0&i,j \in I,\, s \in S, \end{aligned}$$

(23)

$$\begin{aligned} \,&\,&\,&w_{ijs} \in \{ 0 , 1 \},&i,j \in I,\, s \in S. \end{aligned}$$

(24)

The objective function (18) accounts for the initial territory design plus the expected cost for redesigning the territory, and the expected costs for demand shortage and surplus in each district (w.r.t. the minimum and maximum thresholds, respectively). Constraints (19) and (20) seek a territory redesign (dependent on the observed scenario). Constraints (21) guarantee that a district that is selected as a district representative according to the first-stage solution is not reassigned in the second stage. Constraints (22) and (23) are an alternative way of writing that $v_{ijs} \ge \max \{ 0 , w_{ijs} - x_{ij}\}$, $i,j \in I$, $s \in S$. On the other hand, due to the non-negativity costs $r_{ijs}$ we know that in every optimal solution the equality holds, i.e., $v_{ijs} = \max \{ 0 , w_{ijs} - x_{ij}\}$, $i,j \in I$, $s \in S$. Therefore, we are paying the reassignment cost for the demand that is actually reassigned. Finally, constraints (24) define the domain of the w-variables.

In principle, the above model allows the reassignment of all territories. However, since there are extra costs for reassignments as well as for demand shortage and surplus, an optimal solution to the problem will seek to reassigning as little demand as necessary to achieve an overall balancing.

Remark 4

The above model is a generalization of model $\min$ (16), s. t. (2), (3), (5), (6), (13)–(15): setting the costs $r_{ijs}=\infty$, $i,j \in I$, $s \in S$, all the v-variables become equal to zero in an optimal solution which leads to the redundancy of all constraints involving these variables. $\square$

Remark 5

Due to the auxiliary variables $\psi _{js}$ and $\varphi _{js}$ ($j \in I$, $s \in S$) there is always a feasible solution to the above model. Hence, for every feasible first-stage solution, there is always a feasible completion at the second stage, which means that we are again dealing with a stochastic programming with complete recourse. $\square$

4 The relevance of considering a stochastic modeling framework

In the previous sections we have considered stochastic programming modeling frameworks for a districting problem under uncertainty. One important question in this case concerns the relevance of considering such frameworks instead of simpler ones (e.g. deterministic). Two measures are usually considered for evaluating such relevance: the Value of the Stochastic Solution (VSS) and the Expected Value of Perfect Information (EVPI). The reader can refer to Birge and Louveaux (2011) for further details. Next we specialize these measures to the more general problem that we considered: SDPR.

Consider the model:

$$\begin{aligned}&\text{ minimize } \qquad {(18)}, \\&\text{ subjet } \text{ to } \qquad \; {(2)}, {(3)}, {(5)}, {(6)}, {(14},{(15)}, \\&\qquad \qquad \qquad \;\; {(19)} - {(24)}, \end{aligned}$$

and denote by SP its optimal value.

Consider the single-scenario problem obtained by replacing all the random variables with the corresponding expected values. By solving that model, we obtain a first-stage solution, say $\hat{{\mathbf {x}}}$, that is also feasible for the stochastic problem. Hence, we can evaluate its cost as a feasible solution to the stochastic problem. To do so, we just need to fix the values of the x-variables according to $\hat{{\mathbf {x}}}$ in the problem $\min$ (18) s. t. (2), (3), (5), (6),(14),(15), (19)–(24). The resulting value is denoted by EEV (the Expected value of the optimal solution provided by the Expected Value problem, see Birge and Louveaux 2011).

The value of the stochastic solution is computed as VSS=EEV-SP. This (non-negative) value indicates how good is the optimal solution to the expected value problem as an approximation to the optimal solution of the stochastic problem.

The EVPI is a measure of how much a decision maker would be willing to pay to get access to perfect information. A high EVPI indicates that having access to that information is quite relevant which means that uncertainty plays an important role in the problem. In order to compute the EVPI we start by solving the single scenario problem for every possible scenario. Denote by $\mathcal {V}_s$ the corresponding optimal value ($s \in S$). The so-called Wait-and-See solution value is defined as WS=$\sum _{s \in S} \pi _s \mathcal {V}_s$. The expected value of perfect information is equal to EVPI=SP-WS.

5 Extensions of the proposed model

In this section, we discuss some possible extensions to the problem investigated in the previous sections. These extensions are motivated by the need to include features of practical relevance that were not considered in our formulations. Examples of such features include territory dispersion and similarity w.r.t. to an existing districting plan. Furthermore, it may be relevant to manage some practical issues related with the second-stage decisions since the reassignment recourse action that we have considered can lead to disadvantageous allocations for TUs as we discuss below.

The additional aspects discussed in this section are modeled mathematically by the introduction of new sets of constraints in the optimization model presented in Sect. 3. Unless stated otherwise, we adopt the assumptions and modeling considerations presented in that section.

5.1 Maximum dispersion

As we mentioned directly in Sect. 1, territory dispersion indicates the maximum distance between any TU and the center of the district it is allocated to (Ríos-Mercado 2016; Ríos-Mercado and Escalante 2016). In the context of the stochastic districting problem we are studying, let us suppose that there is a maximum desirable dispersion, say $l_{\max }$, for the districting to be obtained. This can be easily ensured for the first-stage solution by setting $x_{ij}=0$, for all $(i,j) \in I$ such that $\ell _{ij} > l_{\max }$. Moreover, if a maximum value for the dispersion should also hold for the second-stage solution then all variables $x_{ij}$, $w_{ijs}$, and $v_{ijs}$ with $\ell _{ij} > l_{\max }$ are set equal to 0 for every $s \in S$. In this case, such variables do not even need to be considered/defined.

There is a trivial maximum dispersion that makes sense to impose to a solution which is the one that results from solving the plain model ($M_2$). This aspect is taken into account later when we report on the computational tests performed.

5.2 Reallocation constraints

In the SDPR that we are studying, second-stage decisions ensure TUs reallocations to avoiding demand shortages or surplus in the created districts. However, as our computational experiments show, adapting a solution to the occurring scenarios may disfavor the compactness (and thus contiguity) of the districts. Hence, a natural extension to the problem consists of limiting the number of reassignments in the second stage.

Denoting by m the maximum number of allowed reassignments , we can make use of the v-variables presented in the previous section, and impose:

$$\begin{aligned} \sum _{i \in I} \sum _{j \in I} v_{ijs} \le m, \quad s \in S. \end{aligned}$$

(25)

5.3 Similarity with respect to an initial plan

Another relevant aspect often considered in DPs, regards the need to guarantee a certain degree of “similarity” w.r.t. some territory organization already planned (Bozkaya et al. 2003; Caro et al. 2004; Bruno et al. 2017a).

In our stochastic setting we can consider similarity constraints associated with the second stage in order to ensure that we redesign districts keeping a certain degree of similarity w.r.t. the first-stage districting plan. This can be ensured using the following inequalities:

$$\begin{aligned} \sum _{i \in I}x_{ij}w_{ijs} \ge \gamma \sum _{i \in I}x_{ij}, \, \, \, j \in I, s \in S, \end{aligned}$$

(26)

In this expression, $\gamma \in [0,1]$ is the minimum percentage of TUs to be kept together in the same district according to the first-stage plan.

Constraints (26) can be linearized by considering the following linear constraints:

$$\begin{aligned}&v_{ijs} \le w_{ijs},&\qquad&i,j \in I, s\in S, \end{aligned}$$

(27)

$$\begin{aligned}&x_{ij} + v_{ijs} \le 1 ,&i,j \in I, s\in S, \end{aligned}$$

(28)

Constraints (27) guarantee that in each scenario the v-variables do not account for a reassignment to some district if the assignment does not hold in the second stage solution. Constraints (28) ensure that TU i can be either assigned to district j in the first-stage solution or reassigned to the same district in a second-stage districting plan for every scenario $s \in S$.

Hence, Constraints (26) can be rewritten as follows:

$$\begin{aligned} \sum _{i \in I} (w_{ijs} - v_{ijs}) \ge \gamma \sum _{i \in I}x_{ij}, \qquad j \in I, s \in S, \end{aligned}$$

(29)

6 Computational experiments

In this section, we report on the computational tests performed to assess the relevance of our contribution. The tests aim at checking whether the models yield plausible solutions. In this analysis we consider real geographical data.

In Sect. 6.1 we describe the test data used. In Sect. 6.2 we focus on one particular instance as a way to better understand the type of solutions we obtain using our model and also to understand the consequences driven by changing the reallocation costs. We proceed in Sect. 6.3 by using the same instance to analyze the effect in the solutions by considering the extensions proposed in Sect. 5. In Sect. 6.4 we extend the results to all the instances with a fixed number of TUs. In this case we focus on the VSS, EVPI and CPU time. Finally, in Sect. 6.5 we extend the results farther by considering all the generated instances (i.e., varying number of TUs). In this case our focus will be the CPU time required to solve the model.

6.1 Test data

The stochastic programming models proposed in the previous sections were tested using data corresponding to the province of Novara, in northern Italy. This is a province divided into 88 municipalities (ISTAT, 2011) that we take as the reference TUs for our study.

Fig. 1

Novara province: the municipalities and the corresponding centroids

Making use of the GIS software QGIS we discretized the region by determining the centroids of the municipalities. Afterwards, we identified set I with the set of the extracted centroids, where we suppose that demands $d_{i}$ are concentrated. Euclidean distances $\ell _{ij}$ between all pairs of centroids $i,j \in I$ have been computed. The province of Novara, its municipalities, and their centroids are depicted in Fig. 1.

Since no real data could be found in terms of the demand for existing services we decided to randomly generate the missing data. A so-called intermediate scenario was obtained by randomly generating the 88 demands according to a uniform distribution in the range [1, 10]. Then, two additional scenarios were computed by considering a 20% positive and negative deviation respectively, from the intermediate scenario.

The reason for considering only three scenarios has to do with the purpose of our computational tests: to check the relevance of the stochastic models proposed in the previous sections. If they are relevant for a small number of scenarios—as we show—they should also be relevant when a larger number of scenarios is considered.

In order to obtain extended data that can better help evaluating the modeling framework we are proposing in this paper, we tested instances that differ among each other in terms of the number of TUs involved. We considered the data corresponding to Fig. 1 and produced a larger instance with 120 TUs. This was done by looking for additional municipalities that have a border in common with some TU(s) already considered. Additionally, we considered 2 subsets of the 88 initial TUs: one with 60 TUs drawn from the 88-TU-instance and another one with 40 TUs drawn from the 60-TU-instance. The selection of the 60 TUs to draw from the 88 was made in such a way that the remaining region would be meaningful (e.g., no holes). The same was done when drawing the 40-TU-instance from the one with 60 TUs. In the appexdix, Tables 5 and 6 we detail the relevant information.

Four probability distributions, indexed in $K=\{1,2,3,4\}$, were considered inducing an equal number of base data sets for the computational tests. We denote by $\pi _{sk}$ the probability of scenario s according to the k-th probability distribution ($k \in K$). The information is provided in Table 1.

Table 1 Probability distributions across the scenarios

As we discussed in Sect. 2.1, the target demand (${\hat{\mu }}$) to be used in the balancing constraints needs to be specified in every instance of the problem. In our case, we follow expression (17) and thus we consider a value that depends on the underlying probability distribution. For a particular probability distribution $k \in K$ we can specify it as follows:

$$\begin{aligned} \bar{\mu }_k = \frac{1}{p} \sum _{i \in I}\sum _{s \in S} \pi _{sk}d_{is}, \quad k \in K. \end{aligned}$$

Demands have been chosen as weighting factors in the computation of the assignment costs. For the instance associated with probability distribution k ($k \in K$) we defined:

$$\begin{aligned} c_{ij}^{(k)} = \ell _{ij} \, \sum _{s \in S} \pi _{sk} d_{is}, \quad i,j \in I. \end{aligned}$$

Concerning the reassignment costs, they were set as follows:

$$\begin{aligned} r_{ijs} = \omega \, d_{is} \, \ell _{ij}, \quad i,j \in I, s \in S. \end{aligned}$$

We make the above costs dependent on the observed demand, and Euclidean distance between the centroids of interest and a parameter $\omega$ that accounts for the penalty due to the reassignment. The chosen expressions for generating the reassignment costs bare resemblance with those used in the redistricting problems investigated by Caro et al. (2004) and Bruno et al. (2017b).

Remark 6

In case $\omega =1$ we have $c_{ij}^{(k)}=\sum _{s \in S} \pi _{sk} r_{ijs}$. This means that we have a relation between the initial assignment costs and the second stage (re)assignment costs. This relation allows us to quantify the expected “total second stage (re)assignment cost”, which can be accomplished by considering the expression $\sum _{i \in I} \sum _{j \in I} \sum _{s \in S} \pi _{sk} r_{ijs} w_{ijs}$. We recall that w-variables define the second stage territory design in which some TUs remain assigned like in the first stage (the w-variable coincides with the corresponding x-variable but some other TUs are assigned to other TU and a reassignment occurs). This expression is directly comparable with $\sum _{i \in I} \sum _{j \in I} c_{ij} x_{ij}$.

In other words, if $\omega =1$ we can directly compare the (expected) compactness of the second-stage territory design with the compactness of the first-stage one. $\square$

In our experiments, in addition to $\omega =1$ (to allow the above mentioned comparison) we also considered $\omega =2$.

Concerning the unit costs for shortage and surplus demand (w.r.t. the reference value) we defined:

$$\begin{aligned} g_{j}^{(k)} = h_{j}^{(k)} = M_{k} = {\max _{i \in I}} \{ \ell _{ij} \, \sum _{s \in S} \pi _{sk} d_{is} \}, \qquad j \in I, \, k \in K. \end{aligned}$$

The above values seem too high. However, we think they are appropriate to foster reallocation mechanism by adapting the solution to the occurring demands.

Finally, in order to better test the behavior of our modeling framework, parameter $\alpha$ was varied from 0.05 up to 0.30 with a step of 0.05, while p was set equal to 4 and 6.

In total, for the 88-TU territory depicted in Fig. 1 we generated 96 instances: four values for k, two values for $\omega$, six values for $\alpha$ and two values for p.

All the models were solved using the commercial solver IBM CPLEX v12.8 on an Intel(R) Celeron(R) with 1.50 GHz and 4 GB of RAM. Next, we report on the computational results obtained by the implementation of the models proposed for the SDPR. In particular, we focus only on model ($M_2$) since it includes ($M_1$) as a particular case.

6.2 First observations

We start by analyzing one specific instance to illustrate the relevance of capturing uncertainty in districting problems. The instance considered is the one defined by $p=4$, $k=3$, $\omega =1$, and $\alpha =0.20$. The results obtained for the SDPR are depicted in Fig. 2, where

different colors refer to different districts. The TUs selected as districts’ centers or representatives are depicted in yellow. We also note that each TU is labeled with a unique ID code.

Fig. 2

Solutions for the instance defined by $p=4$, $k=3$, $\omega =1$, $\alpha =0.20$

In Fig. 2a we observe that the stochastic model led to a firts-stage solution with very compact clusters. The cost associated with this territory design is $\sum _{i \in I} \sum _{j \in I} c_{ij}x_{ij}=3299.38$. Additionally we observe that apart from TU 44, contiguity holds although it was not explicitly imposed ( TU 44 belongs to the green district although it is contiguous only to TU 68 and TU 8 that belong to the cyan district).

In Fig. 2b–d we observe the second-stage solutions—one for each possible realization of the demand vector. Looking into these figures we conclude that when demand becomes known the model “suggests” some reassignments in order to meet balancing constraints without incurring in too high penalty costs. For instance, when scenario 1 (“below intermediate”) is observed, 6 TUs (16, 50, 53, 59, 74, and 87) are reallocated from the orange and cyan districts to the dark blue one. This is a way to let the latter to comply with the minimum demand threshold. Similarly, when scenario 3 (“above intermediate”) occurs, 7 TUs (19, 53, 59, 74, 79, 83, and 87) are reassigned to avoid above-threshold demand in the districts. To accomplish this, for example, the model “suggests” the reallocation of TUs 79 and 83 to the orange district. According to the chosen probability distribution ($k=3$), the first stage solution remains unchanged when scenario 2 (“intermediate”) is considered.

Finally, we note that the total expected reassignment cost is $\sum _{i \in I} \sum _{j \in I} \sum _{s \in S} \pi _{sk} r_{ijs} v_{ijs}=163.82$. Since the total penalty cost is equal to zero (all variables $\psi _{js}$ and $\varphi _{js}$ are equal to zero) we obtain $3299.38+163.82= 3463.2$ as the optimal value to the stochastic problem.

Not surprisingly, we observe that the second stage (re)allocation decisions lead to lower quality solutions both in terms of contiguity and compactness. The latter is testified by the expected total (re)assignment costs $\sum _{i \in I} \sum _{j \in I} \sum _{s \in S} \pi _{s}r_{ijs} w_{ijs} = 3396.09$ (see Remark 6).

Overall, in this illustrative instance we observe what we would expect (and wish) in practice: a major plan is initially devised (the first-stage solution) that suffers several minor changes according to how uncertainty is revealed. A major change in the first-stage solution would indicate that it was not hedging appropriately against uncertainty.

In a second phase of the experiments, we wanted to see the effect of changing the penalty factor $\omega$. Hence, we considered the instance similar to the previous one but with $\omega =2$. In Fig. 3 we depict side by side the first-stage solution for both instances. Figure 3a is the same as Fig. 2a but we repeat it for the sake of an easier comparison.

When $\omega =2$, the penalty for reassignment decisions becomes higher. In this case, the model suggests no reassignment independently from the demand observed. However, in order to better hedge against uncertainty, some changes are observed in the first-stage solution: for $\omega =2$, TUs 7, 19, and 73 are assigned to the dark blue district, while units 26 and 59 are included in the orange one whose representative is now TU 15. These changes are reflected in a lower compactness of the solution that is reflected in a higher value of the objective function of the model, which increases up to 3498.56.

Fig. 3

First stage solutions for the instances with $p=4$, $k=3$, and $\alpha =0.20$

Finally, in addition to determining the solutions for the above two instances we computed both the VSS and the EVPI. This is done in percentage w.r.t. the optimal value of the stochastic problem (SP), i.e., we compute $100 \times VSS/SP$ and $100 \times EVPI/SP$. As explained before, this is a means to quantify the relevance of considering the stochastic approach we have proposed.

We start by computing the solution for the single-scenario (deterministic) problem that results from replacing the random demands by their expectation. Since the difference between the two above instances regards the value of $\omega$ it is easy to conclude that the single scenario problem has the same optimal solution for both $\omega =1$ and $\omega =2$. Note that when we consider just one scenario, no reassignment is made. The resulting solution is depicted in Fig. 4. Clearly, this solution differs from the optimal first-stage solutions depicted in Fig. 3.

Fig. 4

Optimal solution to the expected value problem ($p=4$, $k=3$, $\alpha =0.20$)

The optimal solution to the expected value problem presents a higher compactness value than the two first-stage solutions previously analyzed (the territory design costs—$\sum _{i \in I} \sum _{j \in I} c_{ij}x_{ij}$—have decreased to 3249.18). Nevertheless, it turns out to be very weak when implemented as a first-stage solution in our stochastic problem. When scenarios 1 and 3 occur the model forces the reallocation of 10 TUs in order to meet the balancing constraints (Fig. 5). Thus, we obtained $100 \times VSS/SP$ equal to 3.87% ($\omega =1$) and to 12.77% ($\omega =2$). This shows that for the two instances considered the expected value problem provides a poor approximation to the stochastic problem, which indicates a high relevance of capturing uncertainty in these cases.

Fig. 5

Map of the solutions to the expected value problem ($p=4, \alpha = 0.20, k = 3$)

Finally, we computed the percentage value of the EVPI w.r.t. SP, obtaining $6.00\%$ ($\omega =1$) and $17.64\%$ ($\omega =2$). This means that the EVPI is equal to 6% of the optimal value of the stochastic problem for $\omega =1$ and 17.64% for $\omega =2$. Again, we conclude for a clear relevance of the introduced stochastic approach in the analyzed cases.

6.3 The effect of extending the model

We focus now on the extensions to the base model that were proposed in Sect. 5. We consider the same instance as before ($p=4$, $k=3$, $\omega =1$, $\alpha =0.20$). This allows us to perform some sensitivity analysis and thus to better capture the effect of considering either a maximum dispersion, reallocation constraints or similarity w.r.t. the first-stage districting plan.

6.3.1 Maximum dispersion

To evaluate the effect of including a maximum dispersion constraint, we considered the exclusion of subsets of decision variables as discussed in Sect. 5.1.

In order the ensure the effectiveness of these constraints and thus to analyze their effect, we established a maximum value for $l_{\max }$ defined by

$$\begin{aligned} l_{\max } = \left\lfloor \max _{i,j \in I,\, s \in S} \{ \ell _{ij} {\tilde{w}}_{ijs} \} \right\rfloor , \end{aligned}$$

where ${\tilde{w}}$ stands for the second-stage districting obtained using model ($M_2$).

In the particular case of the instance we are analyzing we have $\max _{i,j \in I,\, s \in S} \{ \ell _{ij} w_{ijs} \} = 31.60$, which gives $l_{\max }=31.$ Starting from this value, we produced several instances by decreasing the value of $l_{\max }$ successively until the expected value problem becomes infeasible. The results are depicted in Table 2.

Table 2 Results for different thresholds ($l_{\max }$) defining the maximum dispersion ($l_{\max } = \infty$ corresponds to ignoring the additional constraints)

Before commenting on Table 2 we note that if we focus on the single-scenario solutions we have $\max _{i,j \in I} \{\ell _{ij} x_{ij} \}=15.60$. This explains why in this table the wait-and-see values are the same before $l_{\max }$ drops to 15.00.

Concerning the relative values of VSS and EVPI w.r.t SP we observe an increasing trend with the decrease of $l_{\max }$. They become quite large when we set more stringent values for $l_{\max }$. We have $100*VSS/SP$ larger than 90% for $l_{\max }$ equal to 16.00 and 18.00. This holds due to the fact that the expected value problem produces a first-stage solution that implies higher penalties for reallocations in the second stage namely, when the allowed maximum dispersion decreases. Interestingly, when $l_{\max }$ decreases to 15.00, $100\times VSS/SP$ decreases significantly. This is due to the fact that the value for that parameter is so stringent that not even the stochastic model can find a good first-stage solution (avoiding high penalties in the second stage). We see that the optimal value to the stochastic problem increases significantly when $l_{\max }$ decreases from 16.00 to 15.00. This is an indication that stringent values of $l_{\max }$ that are not extreme give relevance to a stochastic modeling framework when accounting for maximum dispersion.

Concerning the CPU time required to solve the model with maximum dispersion constraints, the trend is not clear. Nevertheless, we observe that the model can be solved up to proven optimality within a reasonable CPU time.

6.3.2 Reallocation constraints

To evaluate the impact of considering reallocation constraints, we added Constraints (25) to model ($M_2$). Like for $l_{\max }$ we tried several values of m starting with the first non-binding one that is given by $\max _{s \in S} \{\sum _{i \in I} \sum _{j \in I} {\tilde{v}}_{ijs}\}$, where ${\tilde{v}}$ stands for the optimal values of v-variables when the plain model ($M_2$) is considered. In our specific instance we obtained a value of 7, i.e., if m is larger than or equal to 7 then Constraints (25) are non-binding. We note that the smallest value we can consider for m is zero which corresponds to the case in which we do not allow for reallocations in the second stage. The results obtained can be observed in Table 3.

Table 3 Results corresponding to reallocation constraints for different values of m ($m = \infty$ corresponds to ignoring the additional constraints)

The first aspect to point out in Table 3 concerns the wait-and-see value (WS) which is the same regardless the value of m. This holds because reallocations affect only the second-stage solutions, which under a single scenario does not produce any change w.r.t. the first-stage solution. In other words, the reallocation constraints are redundant in a single-scenario instance.

From the above table we can draw other conclusions. First, the relative values of VSS and EVPI w.r.t SP have an increasing trend with the reduction of m.

Concerning the relative values of EVPI we see that the values are in general small. The stochastic program is not much affected by penalties and thus the differences between the wait-and-see solution and the solution to the stochastic problem are rather limited.

Concerning the relative values of VSS (w.r.t. SP), we can see how they rapidly increase when m decreases. This is explained by the fact that the (first-stage) solution for the expected value problem implies significant changes (penalties) in the second stage which is not the case when we consider the first-stage solution produced by our stochastic model. This shows that the stochastic programming problem is able to produce solutions that can better hedge against uncertainty.

Finally, as far as the CPU time required to solve the models to proven optimality is concerned, we do not observe a clear trend. In any case, we can solve the model within an acceptable CPU time.

6.3.3 Similarity w.r.t. the first-stage districts

To analyze the effect of imposing a some degree of similarity between the first- and second-stage solutions, we included Constraints (27)–(29) in model ($M_2$).

To ensure that Constraints (29) are binding, we looked for the $\ll$minimum value of similarity$\gg$, say $\gamma ^*$, between the first- and second-stage solution that we could observe in our instance. Such a value was found as follows: for every district and scenario we computed the percentage of TUs belonging to the district that remain so in the second stage. Then we look for the minimum value. In synthesis, we set

$$\begin{aligned} \gamma ^* = \min _{j \in I,\, s \in S} \left\{ \frac{\sum _{i \in I} x_{ij} w_{ijs}}{\sum _{i \in I} x_{ij}} \right\} . \end{aligned}$$

For the instance we have been working with we obtained $\gamma ^* = 0.84$ ( using the solutions depicted in Fig. 2). The cyan district is the one to which this lowest value corresponds. In the first-stage solution (Fig. 2a), 25 TUs are in this district out of which 21 remain so in the second stage both for scenarios 1 and 3 (Figs. 2b, d). Higher values are found in the other cases.

Hence, when implementing Constraints (29) we set $\gamma =0.85$. To get a deeper insight on parameter $\gamma$ we then tested other possibilities, namely: 0.90, 0.95, and 1.00. The last one corresponds to the case in which we have full similarity between the first-stage and the second-stage solutions (no reallocation occurs in the second stage).

The results are summarized in Table 4.

Table 4 The effect of constraints imposing similarity between the first- and the second-stage solutions

Like for the reallocation constraints, similarity constraints are redundant in a single-scenario setting, which explains the constant value observed for the wait-and-see solution (WS).

Both the the relative values of VSS and EVPI w.r.t SP exhibit an increasing trend when $\gamma$ increases.

Again, the values observed for the (relative) EVPI are not very high. The explanation is similar to that presented for a similar aspect when considering the reallocation constraints.

The relative values of VSS increases significantly when $\gamma$ increases. This is an indication that the first-stage solution obtained when solving the expected value problem is not good hedging against uncertainty (and thus incurs on much penalties in the second stage). In any case, this is a clear indication that our stochastic programming model produces solutions that can better hedge against uncertainty.

Regarding the CPU time required to solve the model up to proven optimality, we see an increasing trend with the increase in $\gamma$. It is interesting to note that for $\gamma =1.00$ the solver required more than 2000 s of CPU. However, the same solution can be obtained by imposing a maximum number of reallocations $m=0$, which requires only 27 s.

6.4 Computational results for the tested instances

Having presented some detailed results for one instance, we proceeded with results obtained by solving the mathematical model proposed for the SDPR ($M_2$) for all the generated instances described in Sect. 6.1. For obvious reasons we do not present the solutions obtained. Instead, we focus on measures that help us to quantify the relevance of capturing stochasticity in our problem: the relative values of VSS and EVPI w.r.t. SP.

The results for the relative VSS are depicted in Fig. 6. The values used in this figure can be found in Tables 7 and 8 that we include in the appendix.

Fig. 6

The relative value of VSS w.r.t. SP (%)

One expected conclusion from observing Fig. 6 is that we obtain larger values for $\omega =2$. As explained above, the optimal solution to the expected value problem does not change with $\omega$ (in a single scenario, no relocation occurs because we can directly plan optimally for that scenario). Therefore, when that solution is considered as a first-stage solution for the stochastic problem, relocations cost more when $\omega =2$ than when $\omega =1$. This explains why the optimal solution to the expected value problem provides a better approximation for the stochastic problem when $\omega =1$. Overall, we observe an average $100~\times ~VSS/SP$ equal to 1.29 for $\omega =1$ and 3.60 for $\omega =2$. Additionally, this value decreases with an increase in p. This means that when more districts are considered, the expected value problem provides a better approximation to the stochastic problem. This indicates that with a larger number of districts we typically observe less reassignments required.

When we focus our analysis on the pairs $(\omega ,p)$, we observe that probability distribution 1 seems to “dominate” the others in terms of VSS. This is an indication that a stochastic approach is less effective when one scenario is more likely than the others.

When we focus our attention on the pairs (k, p), we see that the value of the stochastic solution is typically higher for $\alpha =0.20,0.25$. On average, $100\times VSS/SP$ is equal to 14.32% when $\alpha = 0.20$ and $\omega = 2$. Given the generated demand scenarios, on one hand, the high penalties paid for demand shortages or surplus make the two approaches equivalent when $\alpha \le 0.15$. On the other, no significant differences are detected when balancing constraints are loose ($\alpha = 0.30$). Not by chance, all the instances characterized by a null VSS are associated with these values of $\alpha$.

The above comments suggest a deeper look into the solutions we are obtaining. In our objective function we are considering the (re)assignment costs as well as the penalty costs for shortage/surplus demands w.r.t. the reference values. Since the penalty costs are high, they may blur a solution feature of great relevance to us: compactness. Therefore, we decided to take the instances for which penalties are observed and focus only on the (re)assignment costs which, as we have explained before, are a reliable measure of the solution compactness. We computed a measure that we call the Compactness Value of the Stochastic Solution (CVSS). It is computed like the VSS (i.e. for the same solutions) but ignoring the penalty costs (i.e. setting them to 0). The results can be observed in Fig. 7. Overall, these results show that although the values VSS are rather small, in terms of compactness, the expected value solution provides a poor approximation to the stochastic problem.

Fig. 7

The compactness value of the stochastic solution (%)

In Fig. 8 we present the results obtained for the relative values of EVPI w.r.t. the optimal value of the stochastic problem. The detailed results can be found in the Appendix—Tables 7 and 8. Our computational experience reveals quite significant values for $100\times EVPI/SP$. On average, it is equal to 50.00% for $\omega = 1$ and 52.36% for $\omega = 2$. These high values give an indication that capturing uncertainty in our districting problem is of great relevance. Moreover, the behavior of the EVPI is clear: it is rather insensitive to the adopted value of p and it shows a decreasing trend with $\alpha$. Not surprisingly, the lower the parameter $\alpha$ the higher the risk of observing demand surplus or shortages. Therefore, a decision maker would be willing to pay a higher price to know perfect information about the future.

Fig. 8

The relative value of EVPI w.r.t. SP (%)

Finally we report on the CPU time required to solve our stochastic programming model ($M_2$). This information is depicted in Fig. 9 with the details provided in the Appendix—Tables 7 and 8.

Overall, we conclude that the model could be solved for all the instances within an acceptable CPU time. Most of the instances were solved in less than 1000 s and often much below that. The extreme cases can be devised in Fig. 9.

The CPU times observed show that a stochastic districting problem such as the one that we are investigating in this paper can be solved to optimality using tools that are available to most practitioners. We also note that the instances with $p=6$ seem “easier” to solve than those with $p=4$. We can also observe a tendency for higher CPU times with $\omega =1$ than with $\omega =2$. For the former we observed an average of 306 s while for the latter we observed 249 s. The averages per each value of p can be found in the Appendix.

Fig. 9

CPU time (seconds)

6.5 Extended results: computational performance of the model

So far in terms of computational results we have focused on a single geographical data corresponding to the 88 municipalities of the province of Novara in Northern Italy. We extend now this analysis by considering the 120-, 60-, and 40-TU instances that were also built. In terms of the tractability of the model ($M_2$) we focused in the CPU time required to solve it to proven optimality. The detailed results can be found in the Appendix—Tables 9 and 10. In Fig. 10 we depict the performance analysis.

Fig. 10

Performance evaluation regarding the CPU time (seconds) required to solve the instances

The most significant aspect to highlight in Fig. 10 is that the stochastic model ($M_2$) could be solved to proven optimality for all instances: approximately 95% of the largest instances could be solved in less than 1 hour of CPU. Apart from this, we see that changing the value of the relocation costs $\omega$ does not have a significant impact in the performance of the model.

7 Conclusions

In this paper we investigated a stochastic districting problem triggered by uncertainty in the demand vector. Assuming that uncertainty can be captured by a finite set of scenarios each of which occurring with a given probability, a mixed-integer two-stage stochastic programming framework with some variants and extensions was developed. Computational tests were performed with instances built from real geographical data—and thus instances of a realistic size.

The results show that all instances could be solved to proven optimality using a general purpose solver. This aspect is of particular relevance for a practitioner who may be interested in this type of problems but who does not master sophisticated stochastic programming tools. Moreover, by making use of appropriate measures, the computational results also show that capturing uncertainty may be of great relevance in the districting problems studied.

The work presented suggests several future research directions. First, some discussion provided in this work shows the multicriteria nature of some districting problems. This calls for investigating multicriteria stochastic programming variants of the problems we have investigated in this work. Another aspect that may be interesting to investigate concerns the possibility of capturing uncertainty using chance constraints. This means that instead of modeling the balancing requirements as hard constraints, a (high) probability can be imposed to the satisfaction of these constraints. This possibility leads to a totally different modeling framework which, nonetheless, is worth investigating.

Finally, we note that we have dealt with uncertainty by adopting stochastic programming models. This implies that uncertainty can be captured by some joint cumulative distribution function. If this is not the case, then we may need to resort to other possibilities such as robust optimization. This may also be a promising research direction.

Appendix

In this Appendix we details the information concerning the test data used to realize our computational experiments and we present the detailed results that were reported in Sect. 6.

For each TU, Table 5 reports the generated demand vector and the coordinates of the respective centroid. The original code assigned by ISTAT to uniquely identify TUs (i.e. PRO_COM) is also reported. TUs constituting each of the considered instances are indicated in Table 6.

Table 5 Demands and coordinates of the centroids (Coordinate Reference System: ED50 / UTM Zone 32N EPSG:23032)

Table 6 TUs that are part of each instance

Table 7 Computational results for the 88-TU instances, $p=4$

Table 8 Computational results for the 88-TU instances, $p=6$

Table 9 CPU time (seconds)—for all the instances with $p=4$

Table 10 CPU time (seconds)—for all the instances with $p=6$

For each tested instance, Tables 7 and 8 contain the realtive values of VSS and EVPI w.r.t. SP as well as the CPU time in seconds required by the general purpose solver to solve the instance to optimality. Tables 7 refers to the instances with 4 districts and Tables 8 to instances with 6 districts.

Finally, Tables 9 and 10 contain the CPU time (seconds) required to solve the instances to proven optimalty for different values of |I| (40, 60, 88, and 120).