Optimal Districting and Territory Design

The intent of this book is to present recent developments and insights on optimal territory design problems. In the literature, territory design can also be referred as districting or zone design. In particular emphasis is given to modeling aspects, theory, and algorithmic development of recent complex developments on districting and territory design by leading experts in the field. The book includes some literature surveys on particular areas of districting such as police patrolling, health care districting, and computational geometry methods, and successful case studies in political and sales force deployment districting.

The police districting problem concerns the efficient and effective design of patrol sectors in terms of performance attributes. Effectiveness is particularly important as it directly influences the ability of police agencies to stop and prevent crime. However, in this problem, a homogeneous distribution of workload is also desirable to guarantee fairness to the police agents and an increase in their satisfaction. This chapter provides a systematic review of the literature related to the police districting problem, whose history dates back to almost 50 years ago. Contributions are categorized in terms of attributes and solution methodology adopted. Also, an annotated bibliography that presents the most relevant elements of each research is given.

In this chapter, we review the districting literature in the health care domain. Our goal is to provide the reader with the most relevant studies in the literature as well as a direction for future research. We classify the health care districting problems into three main areas: home care services, primary and secondary health care services, and emergency health care services. We first identify the special characteristics of these different areas. Then we present the modeling approaches, assumptions and solution methods for each of them. In general, we find that certain aspects and dimensions of health care service delivery, which we highlight in this chapter, lend themselves better to the design and implementation of districting-based approaches. As such, we limit our review mostly to studies that include traditional districting models and formulations as well as solution approaches. In closing, we discuss some gaps in the literature and provide directions for future areas of research.

Dividing a piece of land into sub-regions is a natural problem that belongs to many different domains within the world of operations research. There are many different tools that one can use to solve such problems, such as infinite-dimensional optimization, integer programming, or graph theoretic models. In this chapter, we summarize previous methods for solving districting problems that use computational geometry.

In service districting, a given set of customers has to be assigned to the individual members of the service workforce such that each customer has a unique representative, each service provider faces an equitable workload and travel time, and service districts are compact and contiguous. One important, but rarely addressed feature of many service districting applications is that customers require service with different frequencies. As a result, planners not only have to design the service districts, but also schedule visits to customers within the planning horizon such that the workload for each service provider is the same across all periods and the set of all customers visited in the same time period is as compact as possible.

We present a mixed-integer linear programming formulation for the problem. As it turns out, only very small data sets can be solved to optimality within a reasonable amount of time. One of the reasons for that appears to be the high level of symmetry between solutions. We first characterize these symmetries and propose ideas to try to eliminate them in the formulation. Afterwards, we focus on the scheduling component of the problem and present a location-allocation based heuristic for determining visiting schedules for the service providers for fixed districts. In addition, we propose a branch-and-price algorithm to solve larger data sets to proven optimality. One of the novel features of the algorithm is a symmetry-reduced branching scheme that results in a significant speed-up.

For ambulances, quick response to a medical emergency is critical. Limiting response area for each ambulance may lead to shorter response times to emergency scenes and more evenly distributed workload for ambulances. We propose a two-stage stochastic mixed-integer programming model to address the service district design problem under uncertainty. The proposed model recommends how to locate ambulances to the waiting sites in the service area, and how to assign a set of demand zones to each ambulance at different backup levels. Our proposed Stochastic Service District Design (SSDD) model enables quick response times by jointly addressing the location and dispatching policies in a stochastic and dynamic environment. Each backup level is associated with a given response time threshold. The objective function is to maximize the expected number of covered calls while restricting the workload of each ambulance. The proposed model can be optimized offline as is commonly done for “patrol-beats” used in policing models. We evaluate the implementation of the proposed model via a discrete-event simulation, and compare the model with two baseline policies. Our computational results show a significant improvement in mean response time, reduction of 2 min, and statistically lower average workload of ambulances, of 4% on average, when the proposed model is fully implemented.

Voting is a critical political activity and gives voters the opportunity and right to express their opinion in modern democratic society. Ways to increase voter turnout have been widely explored, but, the optimization approach is recognized by many scholars as the best way to assess the efficiency of the current system and draw policy implications. This research highlights the necessity for a spatial optimization approach in determining the location of polling facilities and polling stations tailored to the regulations of the voting process of South Korea. The effects of distance and preference, such as that based on pre-knowledge of or experience with existing facilities, are prescribed as the function ‘utility cost’ in formulating a spatial optimization model, named the Capacitated p-Median Problem with Multiple Stations in the Same Facility (CPMP-M). In a case study of an area with several precincts in Seoul, South Korea, our numerical results based on preference factors demonstrate the need to relocate the existing polling facilities, merge certain precincts, and adjust existing boundaries of precincts to enhance the efficiency of administration of the voting process.

In sales territory design applications, a sales force team is in charge of performing recurring visits to the customers and typically, each territory is assigned to a sales representative with the aim to establish long-term personal relationship with the customers. At the strategic level, the decision maker must partition the set of customer in sales territories and at the tactical level, the daily routes (schedule of visits) of the sales representatives must be planned. Balanced sales territories allow better customer coverage and balanced workload. Additionally, efficient routes allow to perform more visits and to reduce the travel time. In this work, we focus in an application of territory design for determining the size of the sales force in a Mexican company. We also describe a simple heuristic for this problem and analyze its performance in two real cases from the company. Computational results show that the proposed heuristic produces high-quality solutions within a low computation time.