Tabreg: a tool for solving multi-criteria regionalization problems

Regionalization problems involve grouping geographical objects (often ‘zones’) into discrete or fussy spatial groups.  There are examples in many disciplines:

• Putting homes into school catchment areas to ensure that schools are used efficiently
• Putting weather monitoring stations into groups for estimating aggregated weather conditions
• Creating political districts of the voting population by grouping small census zones
• Creating health regions for administering health care resources

Solving regionalization problems can be a challenge because they often must consider multiple (at times competing) objectives simultaneously.  For example, political districts must have equal populations, but often must also include communities of people with similar political interests.  For this reason, many use multi-criteria optimization techniques where a large number of considerations can be used to calibrate an algorithm to solve a specific regionalization problem.  In political districting, it could look something like this:

• Create 10 political districts from 1000 smaller zones
• Each district must have a population between 20,000 and 25,000 voters
• Each district should be roughly compact in shape (should not appear ‘Gerrymandered’)
• No district boundaries should split a single municipality into two or more units

For all but the smallest data sets, this problem is too complex to solve properly without a computer.  Yet incorporating these criteria into a single decision making tool is not trivial.  A number of researchers have implemented these tools over the years, including several specifically for political districting, for example:

• Bozkaya B., Erkut E., Laporte G. (2003). A tabu search heuristic and adaptive memory procedure for political districting. European Journal of Operational Research 144(1): 12-26
• Altman M and McDonald (2011). BARD: Better Automated Redistricting.  Journal of Statistical Software 42(4).

Introducing Tabreg

We have implement our own general purpose regionalization tool that can be used to solve a variety of different optimization problems, including health regionalization, school catchment design, political districting and ecological zoning.  The tool is a simple multi-criteria algorithm that uses a tabu list to escape local optima while searching for good regionalization plans.  These are some features of Tabreg at present

• Non-compactness and non-connectivity (Yiannakoulias et al., 2007) penalization
• Forbidding certain zones from being in the same group
• Incorporating a zone cost matrix into the objective function (useful for transportation applications)
• Tabu and simulated annealing heuristic approaches can be parameterized to escape locally optimal regionalization plans

Some examples

We can easily use Tabreg to create groups based on maximizing or minimizing an attribute within groups.  This examples uses income data from the 2006 Canadian Census

Here we are redrawing political boundaries in an analysis of the most recent Federal redistricting plan.

Using Tabreg

While a public (and open) release of our tool is expected in the next year, if you would like to use the tool, send me an email, and I will provide you the code as is.  All Tabreg users are asked to include this citation in any publications:

Yiannakoulias N, Bland W (2016) Tabreg: Software for Regionalization Problems.  Health Geomatics Lab, School of Geography and Earth Sciences, McMaster University.