Example: Districting

Districting or Territory Design is the problem of grouping small geographic areas (so called basic areas) into larger clusters (so called districts or territories), in a way that the latter are acceptable according to relevant planning criteria. Typical examples for basic areas are cities, counties, zip code areas, streets etc. 


Partitioning based on zip code areas.

 

Examples

There are several different applications of districting.

Political Districting
The aim of political districting is to divide a governmental area (for example a state, federal state or city) into subareas from which political candidates are elected to a parliamentary assembly.  To respect the principle of “one man-one vote”, i.e., every vote should have the same power, all subareas should contain (approximately) the same number of voters. In this case a city, suburb, or neighborhood often should be assigned completely to a subarea. Hence, cities, suburbs, or neighborhoods are the basic areas. Other designated planning criteria are contiguity and compactness. These criteria should prevent “Gerrymandering” – a degenerated districting beneficial for a certain party or candidate.

Left: State senate electoral districts at Massachusetts in 1812. Right: German Bundestag electoral districts in 2005.

Sales Districting
The task of designing sales districts is to divide the market area in regions of responsibility for every salesperson or office. Every salesperson should have (approximately) the same workload. To minimize the (expensive and nonproductive) travel time, the regions should be contiguous and compact. Other planning criteria could require the same sales potential to every region or a good accessibility (e.g. highways, public traffic) within the district. Typical basic areas in this case are cities or zip code areas, but also smaller sales districts or single costumers. Often the desired number of regions and the locations of the salesperson are given by the company, but both could also be part of the planning process. Especially for sales companies, profit maximization is another important criterion for the planning process.

Left: Partitioning of a market area into four regions of responsibility and the locations of the salesperson. Right: Partitioning of a market area into 16 regions of responsibility without the locating salesperson.

School Districting
School districting is the problem of assigning residential neighbourhoods (for example streets, blocks, or quarters) to existing schools. Here capacity limitations, like the number of rooms in the school buildings, are important planning criteria. Other criteria could require a balanced capacity utilization of the schools, a minimization of the unproductive travel time or a good accessibility of the schools by public traffic.  Especially in the U.S., racial balance is often another important design criterion – the rate of students, which belong to a racial minority, should be (approximately) equal for all schools to offer all students the same opportunities.

Assigning of streets to existing schools.

Winter services and solid waste collection districting
The objective of this districting problem is an assignment of streets, street segments, blocks or quarters to areas of responsibility for one vehicle depot or one collection/spreading vehicle. Possible constraints are the balance of workload and travel time between the different depots. Furthermore the areas should be contiguous and compact to reduce the needless travel time. Additionally the areas should allow the planning of “good” routes.

Areas of responsibility for different collection vehicles.

Electrical waste recycling districting
This problem is motivated by the recycling directive WEEE (Waste Electrical and Electronic Equipment) of the EU. The core of this directive is that each company which sells electrical or electronic equipment in a European country has the obligation to recollect and recycle an amount of returned items which is proportional to its market share. For one group of products, the so-called “white goods”, i.e., household appliances, each regional collection station is assigned to one company for a given period of time. Whenever a collection device at this station is full, this company is responsible for the waste treatment. However, in contrast to other problems of districting, the collection stations of one company should be geographically as dispersed as possible. This criterion should avoid that a company gains a monopoly in some region.

An Assignment of collection stations to companies that fulfill the requirement that the territories should be geographically as dispersed as possible.

Other applications
There are more applications, like the planning of districts for social facilities, the planning of areas of responsibility for home health care teams, the planning of streets for paperboys, etc.

Planning Criteria

The considered planning criteria are depending on the application and can be placed under the three general headings: demographic, geographic and political:

  • Balance: Every district should have (approximately) the same “size” or “weight” with respect to one (or more) activity measure(s), for example inhabitant, sales potential, workload etc.
  • Capacity limitations: The sum of all activity measure of one district has to respect some capacity limitations, such as the capacity of a school is limited by the number of existing rooms.
  • Compactness: Figuratively a district is said to be compact if it is nearly round-shaped and undistorted. This criterion is useful to reduce the travel time inside the district. In the case of political districting it helps to prevent „Gerrymandering“.
  • Contiguity: The district should be continuous, due to administrative reasons and especially in the context of political districting to complicate „Gerrymandering“.
  • Accessibility: Inside the district there should be a good accessibility of the central point (for example the school) or between the basic areas. Depending on the application a good accessibility by bus, train, car is desired.
  • Exclusive and total assignment: Every basic area is assigned to exactly one district.
  • Number of districts: Often the desired number of districts is given, but it could also be part of the planning process.
  • Location: Often the central location is given (e.g. existing schools), but it could also be part of the planning process (e.g. location for a new office).
  • Profit maximization: Especially for sales companies, profit maximization is another important criterion for the planning process. The districts should be chosen in a way that the estimated profit is as big as possible.

Left: Balanced / Unbalanced with respect to the green points. Middle: The districts in the first partitioning seem to be more compact than in the second partitioning. Right: Contiguous / Uncontiguous districts.

Research Work and Goals

A variety of research works are dealing with special applications. In contrast to this, we try to look more generally on the problem. In our group we use a generic, application independent model and a specially tailored algorithm, based on methods from Computational Geometry.

Our aims of research are to develop extensions and modifications of this generic-model to make it applicable for a broader range of practical problems.  This contains for example problems like the incomplete assignment of basic areas, overlapping districts, hierarchical partitioning or balancing over a period of time. Furthermore, it contains interdisciplinary issues, like political considerations.

Research Results

 

Contact person

​Stefan Nickel