Introduction
School redistricting is a complex "wicked problem" for local governments, requiring the assignment of geographic planning polygons to schools while balancing numerous competing objectives. These include maintaining school capacities, minimizing transportation costs, ensuring socioeconomic and academic diversity, and preserving stable feeder patterns. Traditionally, this process is handled manually by staff using basic mapping tools—a method that is slow, politically sensitive, and often fails to explore the full range of viable alternative solutions.
This paper frames redistricting as a multi-criteria optimization task and introduces heuristic local search methods designed to discover a diverse set of high-quality plans. To assist human decision-makers in navigating these options, the authors also propose novel "tree-ring" visualizations to compare competing proposals at a glance.
Evaluation Metrics and Methodology
The authors define five quantitative criteria ($f_1$ to $f_5$), normalized to a $[0, 1]$ range where lower values indicate better performance:
- School Capacity ($f_1$): Uses a scaled arctan penalty function to heavily penalize schools falling outside the ideal 90-110% utilization range.
- Socioeconomic Distribution ($f_2$): Aims to equalize the rate of students receiving Free and Reduced Meals (FARM) across the district.
- Test Score Distribution ($f_3$): Seeks to equalize academic performance across schools.
- Busing Costs ($f_4$): Measures "excess distance" traveled beyond the geographically closest school.
- Walk Area Usage ($f_5$): Maximizes the number of students attending their "home" school if they live within walking distance.
Search Algorithms and Diversity
While basic hill climbing can find local optima, the authors' core contribution is Biased Hill Climbing with Diversity Bias. Because there is rarely a single "best" solution in political optimization, the algorithm identifies "incomparable" plans—those on the Pareto frontier where one plan cannot be improved in one metric without degrading another.
To avoid presenting nearly identical solutions, the algorithm maintains a list of incomparable plans and selects seeds for new search iterations that are maximally distant (in Euclidean space) from existing solutions. This ensures a broad menu of qualitatively different policy trade-offs for the school board to consider.
Visualization: The "Tree-Ring" Approach
To help users compare two different plans at a glance, the authors introduced "tree-ring" glyphs. On a map, each polygon is rendered with an inner and outer ring. The shades of these rings represent the school assignments for two different proposals. This allows decision-makers to immediately identify geographic areas where two plans disagree.
Case Study and Results
The methods were tested using real-world data from Howard County, Maryland, specifically focusing on the redistricting required for the opening of Marriotts Ridge High School. The automated approach consistently outperformed manual plans. For instance, a weighted hill-climbing plan achieved a combined objective score ($F$) of 0.91, significantly better than the manual "Green" plan's 1.17.
Moreover, the Diversity Bias method successfully increased the variety of options; the average pairwise distance between generated plans increased from ~0.04 in basic search to ~0.39, providing a much richer set of trade-offs for the final decision-making process. The study also highlighted the "closest-school trap": assigning every student to their nearest school optimizes busing but leads to catastrophic capacity imbalances and poor socioeconomic distribution.
Conclusion
By combining heuristic search with specialized visualization, the authors provide a toolset that acts as an automated consultant for school boards. This approach moves beyond finding a single "optimal" solution to presenting a diverse Pareto frontier of possibilities, allowing human stakeholders to make informed decisions about complex social and political trade-offs.
Summary updated