Skip to main content

About this book

This book highlights recent advances in the field of districting, territory design, and zone design. Districting problems deal essentially with tactical decisions, and involve mainly dividing a set of geographic units into clusters or territories subject to some planning requirements. This book presents models, theory, algorithms (exact or heuristic), and applications that would bring research on districting systems up-to-date and define the state-of-the-art.

Although papers have addressed real-world problems that require districting or territory division decisions, this is the first comprehensive book that directly addresses these problems. The chapters capture the diverse nature of districting applications, as the book is divided into three different areas of research. Part I covers recent up-to-date surveys on important areas of districting such as police districting, health care districting, and districting algorithms based on computational geometry. Part II focuses on recent advances on theory, modeling, and algorithms including mathematical programming and heuristic approaches, and finally, Part III contains successful applications in real-world districting cases.

Table of Contents


Introduction and Literature Reviews


Chapter 1. Research Trends in Optimization of Districting Systems

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.
Roger Z. Ríos-Mercado

Chapter 2. Police Districting Problem: Literature Review and Annotated Bibliography

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.
Federico Liberatore, Miguel Camacho-Collados, Begoña Vitoriano

Chapter 3. A Review of Districting Problems in Health Care

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.
Seda Yanık, Burcin Bozkaya

Chapter 4. Computational Geometric Approaches to Equitable Districting: A Survey

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.
Mehdi Behroozi, John Gunnar Carlsson

Theory, Models, and Algorithms


Chapter 5. Bounding Procedures and Exact Solutions for a Class of Territory Design Problems

In this chapter, we present and evaluate exact methods and lower and upper bounding procedures for a class of territory design problems. Most territory design problems, as the one studied in this chapter, consider requirements of compactness, contiguity, and balance with respect to one or more activity measures, for example, number of customers and sales volume in the case of commercial territories, voting potential equality in the case of political territories, workload balance when designing service territories, etc. To obtain solutions with compact territories, a minisum objective function equivalent to the objective function of the p-median problem is used. The exact solution methods presented here use different relaxations of integer linear programming formulations of the problem. Additionally, two methodologies to obtain upper bounds (feasible solutions) are presented. The first one uses the relaxation of an integer quadratic programming formulation. The second methodology obtains feasible solutions using a primal heuristic within the framework of a subgradient optimization algorithm to solve a Lagrangian dual that also provides lower bounds for the optimal solution. Instances obtained from the literature are used to evaluate and compare the different methodologies presented.
Juan A. Díaz, Dolores E. Luna, María G. Sandoval

Chapter 6. Mathematical Programming Formulations for Practical Political Districting

Political districting is a very well-known technical problem related to electoral systems in which the transformation of votes into seats depends on the subdivision of the national electoral body into a given number of smaller territorial bodies. After a proper discretization of the territory, the problem consists of partitioning the territory into a prefixed number of regions which satisfy a set of geographic and demographic criteria. The problem structure falls back into one of the more general territory design problems, which arises also in other types of applications, such as school and hospital districting, sales districting, etc. In the application to political elections, the aim is to prevent districts’ manipulation which may favor the electoral outcome of some specific party (Gerrymandering). Many political districting models and procedures have been proposed in the literature since the 1960s following different optimization strategies. Among them, many exploit mathematical programming which is one of the most used tools to solve problems in practice. The attractive feature of mathematical programming is that the model is easy-to-read, its resolution can be automated, and good compromise solutions can be computed in reasonable computational time for small and medium size problems.
Federica Ricca, Andrea Scozzari

Chapter 7. Multi-Period Service Territory Design

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.
Matthias Bender, Jörg Kalcsics

Chapter 8. Designing Ambulance Service Districts Under Uncertainty

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.
Shakiba Enayati, Osman Y. Özaltın, Maria E. Mayorga

Applications and Case Studies


Chapter 9. Spatial Optimization Problem for Locating Polling Facilities and Stations and Policy Implications

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.
Hyun Kim, Kamyoung Kim

Chapter 10. Territory Design for Sales Force Sizing

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.
Juan G. Moya-García, M. Angélica Salazar-Aguilar


Additional information

Premium Partner

    Image Credits