Keywords

1 Motivation

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 area of districting or territory design can be seen as a subfield of discrete optimization related to partitioning decisions. In a typical districting problem, a collection of basic or geographic units must be divided into districts or territories. This partition is not arbitrary but must meet a series of planning requirements depending on the specific application or context.

Although there is no such thing as “the Districting Problem” because each problem is different and has its own particular requirements that make it unique, there are certainly some criteria or requirements that are common to an important class of districting problems. For instance, criteria such as compactness, unique assignment, and balance are common to many districting problems. Other criteria such as contiguity, similarity with existing plan often appear as well. Territory compactness has to do with having territories formed by basic units that are close as possible from each other. This is typically achieved by minimizing a dispersion function. In application such as political districting, dispersion functions that take into account the actual shape of the units are often used. Unique assignment means that each basic unit must be assigned to a single district. In other words, this feature assures a partition of the set of basic units. Exceptions to this rule can be found, for instance, in Fernández et al. [2] or Ríos-Mercado and Bard [10]. Territory balance implies that the total amount of “work” must be fairly distributed among districts. By “work” we mean whatever particular attribute or attributes are measured in each basic unit. Examples of this are population size, product demand, number of customers, workload, and so on. Territory contiguity or connectivity appears when there is an underlying graph representing adjacency between basic units, and assures that each territory must induce a connected subgraph. One example of this arises in political districting applications. Similarity with existing plan has to do with redistricting a current partition in such a way that is as similar as possible as the existing one. In commercial or distribution districting, for instance, keeping existing customer-driver relationships is often deemed as very important. Naturally, there is not a unique way of representing or modeling each of these aspects, thus a significant amount of research has been done studying different ways of dealing with these issues. Just to give an example, there are different ways of modeling territory connectivity. Some models are based on polynomial flow-based formulations [12], others are based on exponential amount of explicit connectivity constraints, handled by cut-generation algorithms [11]. Naturally, there are trade-offs that would depend on the particular districting application.

During the 1960–1980s, the main areas of work were dominated by mainly political districting and sales territory design. In the past 30 years or so, aside from these applications we have seen more studies on service-related districting, distribution/commercial territory design, and, more recently, districting in health care applications such as designing districts for location of emergency medical service (Chap. 3) or designing districts for efficient organ transplantation [3].

Now, in terms of solution methodologies, given the inherent computational complexity of most problems, it is not surprising that most of the research done for solving districting problems has been on heuristic and metaheuristic approaches. There is a clear practical impact that requires quick solutions implemented in practice. Nevertheless, some problems have special structure and properties that make them attractive for exact optimization schemes.

The reader can find a number of excellent surveys discussing many aspects of modeling, assumptions, solution methodologies, and applications of territory design and districting. For instance, Zoltners and Sinha [13] present a survey of models, solution approaches, and managerial insights for sales districting problems (1974–2004). They pay special attention to the economical impact that good territory alignment practices and processes have had over the years. Kalcsics et al. [6] present the first extensive literature review on models, methods, and applications for general districting problems. They discuss common features to a large class of districting problems and present a basic territory design model. They discuss in detail two approaches for this basic model: a classical location-allocation approach combined with optimal split resolution techniques and a new method based on computational geometry. They discuss extensions to the basic model and its integration into geographic information systems. Duque et al. [1] review almost four decades (1960s–2000s) of contributions on districting or supervised regionalization methods with main focus on spatially contiguous districts. The authors present a taxonomic scheme that classifies a wide range of regionalization methods into eight groups, based on the strategy applied for satisfying the spatial contiguity constraint. The paper includes a qualitative comparison of these groups in terms of a set of certain features, and a discussion of future lines of research for extending and improving these methods. Ricca et al. [9] present a complete literature survey on political districting highlighting modeling aspects from classical to current approaches. More recently, Kalcsics and Ríos-Mercado [5] present a wide overview and detailed discussion of typical criteria and requirements arising in territory design and how these have been modeled. The discussion includes an overview of many different application areas and the most relevant solution methodologies. Finally, in this book, Chaps. 2 and 3 present up-to-date literature reviews in two very hot areas such as police patrolling and health care districting, respectively, and Chap. 4 reviews computational geometry approaches for continuous-based districting.

2 Research Contributions

2.1 Part I: Introduction and Literature Reviews

The first part of this book contains a literature review and discussion on two very important areas of districting, namely police districting and healthcare districting. In Chap. 2, Liberatore, Camacho-Collados, and Vitoriano present a systematic literature review on police districting problems. They classify the main contributions in terms of model attributes and solution techniques employed. The chapter includes an annotated bibliography discussing the most relevant works on this area.

Chapter 3, by Yanık and Bozkaya, presents a review of literature of districting problems arising in health care. The health care districting problems are classified into three main areas: home care services, primary and secondary health care services, and emergency health care services. The chapter highlights modeling approaches, assumptions, and solution methods for each problem. The chapter ends with a discussion of several avenues of opportunity for future research areas.

Chapter 4, by Behroozi and Carlsson, presents a review of districting algorithms based on computational geometry. These algorithms contrast with other algorithms that are based on discrete network-based models. The chapter includes a discussion on how and when these type of algorithms can be applied and be more useful.

2.2 Part II: Theory, Models, and Algorithms

The second part of the book highlights recent advances on theory, modeling, and algorithms including mathematical programming and heuristic approaches. Chapter 5, by Díaz, Luna, and Sandoval, presents lower and upper bound procedures for a class of territory design problems that consider the minimization of a p-median problem dispersion function subject to planning requirements such as connectivity and balance with respect to one or more activity measures. The chapter also presents exact methods that use different linear programming relaxations.

Chapter 6, by Ricca and Scozzari, addresses political districting problems. The main focus of this chapter is on particular modeling aspects arising on several classes of political districting problems. Special care is given to the district connectivity requirement, which is essential in political districting applications. The chapter includes a discussion of the main contributions in the literature addressing this feature.

In Chap. 7, by Bender and Kalcsics, a multi-period service districting problem is addressed. This considers an important, but not commonly studied feature of many service districting applications consisting of customers requiring service under different frequencies. A consequence of this is that, in addition to the districting decisions, visiting schedules within the planning horizon must be decided as well. These decisions must take into account a fair workload balance for each service provider across all time periods and territory compactness. The chapter presents a MILP model, a discussion of its properties, and a development of a branch-and-price framework for solving the problem.

In Chap. 8, by Enayati, Özaltın, and Mayorga, an ambulance service districting subject to uncertainty is addressed. A two-stage stochastic mixed-integer programming model is presented. The proposed model suggests 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. The 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. The model maximizes the expected number of covered calls, while restricting the workload of each ambulance. An interesting feature is that the proposed model can be optimized offline. The chapter includes an empirical assessment of the model through a discrete-event simulation and comparison with two baseline policies. The results indicate significant improvements in many related metrics.

2.3 Part III: Applications and Case Studies

The third part of the book contains successful applications in real-world districting cases. Chapter 9, by Kim and Kim, highlights the need of determining the location of polling facilities and polling stations tailored to the regulations of the voting process of South Korea by means of a spatial optimization approach. In the spatial model, a utility cost function that captures the effects of distance and preference, such as that based on pre-knowledge of or experience with existing facilities, is formulated. The chapter includes a case study with real-world data in Seoul, Korea. The numerical results indicate 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.

Chapter 10, by Moya-García and Salazar-Aguilar, focuses on a sales territory design application. In this particular problem, a sales force team is in charge of performing recurring visits to customers, where each territory is assigned to a sales representative with the aim of establishing long-term personal relationship with the customers. At the strategic level, the decision maker must partition the set of customers into sales territories and at the tactical level, the daily routes (schedule of visits) of the sales representatives must be planned. Balanced territories allow better customer coverage and balanced workload. Additionally, efficient routes allow to perform more visits and to reduce travel time. The chapter presents a heuristic approach for this problem. The method is applied and assessed in two case studies arising in a Mexican firm. Computational findings indicate the effectiveness of the proposed heuristic, producing high-quality solutions.

3 Closing Remarks

Although the models and techniques presented in this book are applied to specific situations, it is evident that many of these techniques and ideas can be applied or adapted to other more complex problems.

Just as an example, there are a few works that consider districting under uncertainty [4, 7, 8]. Many of the scenario-based and/or decomposition approaches rely on knowing how to efficiently solve or handle deterministic subproblems. The ideas exposed in this volume can certainly be of very high value when devising such approaches.

There are also applications where districting decisions (which are essentially tactical decisions) must be taken along with operational decisions (such as scheduling, routing, and so forth). Chapter 7 is a good example of this. Again, efficient decomposition approaches that rely on effective districting solution algorithms can be studied under these ideas.