Heuristic Search and Information Visualization Methods for School Redistricting

Marie desJardins, Blazej Bulka, Ryan Carr, Andrew Hunt, Priyang Rathod, Penny RheingansAAAI 2006

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.
The capacity penalty function ($f_1$) uses a scaled arctan function to penalize school utilization outside the target 90-110% range.

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.

Tree-ring visualizations allow for the direct comparison of two redistricting plans by showing school assignments as nested rings within each planning polygon.

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

BibTeX
@inproceedings{desjardins2006heuristic,
  author = {Marie desJardins and Blazej Bulka and Ryan Carr and Andrew Hunt and Priyang Rathod and Penny Rheingans},
  title = {{Heuristic Search and Information Visualization Methods for School Redistricting}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
}
Figure