Districting: Multi-Period and Stochastic Approaches

Districting involves grouping smaller areas into larger ones or dividing a larger area into multiple subareas. This thesis examines districting with a focus on multi-period dynamics and uncertainty - two aspects that have received limited attention in existing models since the field’s beginning in 1965. The consideration of these two factors not only better reflects reality, but - as shown in this thesis - taking them into account can also lead to better decisions. A deterministic model is first proposed to serve as a basis, ensuring feasible solutions. The first major contribution of the thesis then consists of an in-depth examination of the multi-period setting, where time-dependent reassignments are allowed and a savings parameter is introduced to balance compactness and reassignments. Computational analyses are conducted to identify when the multi-period model provides advantages over static approaches. This is achieved through detailed computational experiments that perform linear correlation analysis at different levels of granularity in order to provide a comprehensive assessment of the relation between demand fluctuations and values of multi-period solutions. The next part of the thesis then addresses the topic of districting under uncertainty in detail. To this end, we adapt a two-stage stochastic model. Modifications are made to the definition of the average allowed demand in each district, which is now scenario-dependent. The analysis focuses on performance indicators, including the value of the stochastic solution and the expected value of perfect information. The conditions under which stochastic modeling is beneficial, particularly with demand fluctuations between scenarios, are evaluated. In the final methodological part, both uncertainty and multi-periodicity are combined in a multi-stage stochastic districting model, supported by a relax-and-fix heuristic. The model is tested on various instances, including larger instances, to assess its applicability and performance with respect to cost, demand variability, and the number of territorial units and periods. The methodology proposed in this thesis is applied in a comprehensive case study of home healthcare services in Karlsruhe. This realistic case demonstrates the benefits of the developed models in addressing districting challenges, highlighting their potential impact on decision-making. The case study begins with a deterministic single-period setting, followed by an exploration of a multi-period framework. It then transitions to a stochastic setting before combining both time and uncertainty factors. The case study offers valuable insights into the practical application of the proposed districting models in real-world settings, along with important managerial implications.