Verallgemeinerte Gebietsplanungsprobleme, neue Anwendungsbereiche und die algorithmische Umsetzung.
Final Report Abstract
Territory design or districting is the problem of grouping small geographic areas, called basic areas, into larger geographic clusters, called territories or districts, such that the latter are balanced, contiguous, and compact. Balance describes the desire for districts of equitable size. A district is called contiguous if it has no isolated parts and is called geographically compact if it is round-shaped and undistorted. Typical examples for basic areas are customers addresses, streets, or zip code areas. Districting problems are motivated by applications ranging from political districting over the design of districts for schools, social facilities, waste collection, or winter services, to sales and service territory design. Despite, or probably because of this wide range of applications, there is no common framework or model for districting problems that has been established in the literature. Moreover, there is often no consensus on which criteria are eligible and important in the first place. And even then, a rigid and concise definition of them is often difficult and strongly depends on the available data, especially with respect to compactness and contiguity. Therefore, we first combined existing measures for balance, compactness, and contiguity from the literature into a common algorithmic framework. Moreover, we developed new measures; some of them based on existing concepts in Graph Theory and Computational Geometry that have not been applied to districting before, like proximity graphs or χ-shapes, and others developed by ourselves, e.g., for measuring the overlap of districts if contiguity is not a hard criterion. We compared them using real-world problem instances and tried to detect correlations. Although we could identify some measures that performed better than others on average, there was no clear “winner”. However, the algorithmic library we developed enables practitioners to easily test different combinations of measures and identify the ones best suited for his or her application. This also will be a main feature in the re-development of the optimization component of our industrial partner. In addition to this basic analysis, we worked on several new variants of districting problems that are often encountered in practice, but for which no (suitable) models and solution methods existed. These include time-dynamic districting problems which are especially relevant for political districting, problems with an incomplete coverage of basic areas that frequently occur in sales districting, arc districting problems that have to be addressed when designing, for example, mail & leaflet delivery districts, or the problem of adding one or more districts to a given layout. We also worked on interdisciplinary applications of districting problems, for example, for the design of emergency response areas in health-care management and the creation of study groups in education. For all these we formulated new mathematical models or extended existing ones. To solve these problems, we developed exact methods based on mathematical programming, e.g., for the time-dynamic and the study group problem, as well as heuristics, e.g., for arc districting or emergency response area design. Whenever possible, we extended our geometric recursive partitioning algorithm to solve these problems, e.g., for the time-dynamic and the incomplete coverage problem or for emergency response area design. If not, we developed new methods, e.g., for the study group problem, or adapted meta heuristics, for example, for the arc districting problem. These extensions opened up a large range of new applications that can now be solved. Several of these extensions are going to be implemented by our project partner and made available to companies, increasing the awareness and practical use of districting methods. Finally, by implementing an easy-to-use interface for a Geographical Information System, we can use the library to accompany lectures and tutorials in order to help students get a better intuition of the algorithms and their outcomes.
Publications
-
The Maximum Dispersion Problem, Omega 41, 721-730, 2013
E. Fernandez, J. Kalcsics, S. Nickel
-
Districting for arc routing, INFORMS Journal on Computing, 26(4): 809-824, 2014
A. Butsch, J. Kalcsics, G. Laporte
-
Districting Problems. In: Laporte G., Nickel S., Saldanha da Gama F. (eds) Location Science. Springer, Cham, 2015, 595-622. - 978-3-319-13110-8
J. Kalcsics
