Fanglan Chen, Subhodip Biswas, Zhiqian Chen, Shuo Lei, Naren Ramakrishnan and Chang-Tien Lu presented work at EAAI 2023 on exploring the feasibility of automatically generating school redistricting plans. In this interview, Fanglan tells us more about this work, the difficult balancing act when drafting such plans, their methodology, and results of a case study that they carried out.
Our paper explores the feasibility of automatically generating school redistricting plans in an efficient manner and addressing tradeoffs in balancing different criteria in the process. The goal of this research is to assist school board members and urban planners in drafting qualitatively different redistricting plans that represent a variety of considerations in decision making and facilitating better utilization of educational resources.
To accommodate the changes to current student enrolment numbers or projections, the school attendance zones need to be assessed and redrawn each year. Drafting school redistricting plans is a challenging task that demands not only balancing multiple criteria but also considerable effort across the various school levels. This is our main focus of this work.
Our proposed framework can balance multiple criteria in automatically generating school redistricting plans. In the plan-making process, some criteria are conflicting. Take balance and compactness as an example: achieving optimal school attendance zones with a balanced student population will usually result in school boundaries arbitrary in shape, which potentially increase the distance students have to travel to get to school. Our framework finds a balance in optimizing both objectives, which can substantially improve the existing school district.
Another implication is that the quality of the plan can be viewed from multiple dimensions. The most common criteria in automated plan generation are population balance and boundary compactness. However, such metrics are unable to measure some important ethical considerations, for instance, the number of students impacted by the school attendance zone changes. Our work explores other dimensions to look at the quality of the plans and it is flexible to incorporate additional considerations if relevant data is available.
To generate solution plans automatically, we design a school redistricting framework which comprises two stages: initialization and improvement. The initialization stage aims to obtain a seed plan that serves as a valid initial state. Firstly, we identify anchor nodes, and assign capacity as node features only to these anchor nodes. Next, we perform a continuity check to ensure that the initial plan satisfies spatial contiguity constraints. If the initial plan fails this check, a path-linking method is adopted to repair it and modify it into a valid initial plan. Then, the improvement stage of our approach efficiently explores the search space through the use of a Markov chain by two variants of the transition proposals, flip and recombination. During the process, we check the contiguity of all subgraphs and the objective function value after each transition. The new state is saved as the updated state if it improves upon the previous one. If the proposal fails the contiguity or any other constraint check, we generate new proposed plans from the previous state until a plan passes the check.
Automated school redistricting framework.
Our proposed approach was evaluated on two U.S. school districts. Several experiments were conducted, studying the tradeoffs with different combinations of objectives. Our experimental results show that the proposed framework outperforms state-of-the-art meta-heuristic algorithms in terms of the quality of plans generated, particularly in the compactness score. One variant of the proposed framework, RecomChain, adopts the spanning tree method as its transition proposal, resulting in more balanced and compact school attendance zones. However, this requires more modifications to the existing plan, and consequently, more students will be displaced from their originally assigned schools due to changes in school attendance zones. Conversely, the other variant, FlipChain, has the advantage of generating plans that impact fewer students.
We present a case study to demonstrate how our proposed framework can improve the balance and diversity of student populations in existing school redistricting plans. The color ramps illustrate the different assignments of student planning areas in the existing plans versus the automated plans generated by our framework. Each distribution plot displays the distribution of balance and diversity scores across school attendance zones, with the x-axis representing the score values and the y-axis showing the frequency of each score value. Since we formulate school redistricting as a maximization problem with balance/diversity scores ranging from 0 to 1, a plan is more desirable when more zones at each school level achieve scores closer to 1. The distribution plots reveal improvements in both balance and diversity in the automated plans. Additionally, by adjusting the weight of the objectives, our framework can generate multiple distinct school redistricting plans that meet the desired criteria.
A comparison of the existing plans and automated plans generated by FlipChain.
Our next step is to study other metrics that measure the quality of school redistricting plans from multiple dimensions. Additional considerations, such as walking zones, student performance, feeder patterns, and so on, can broaden the scope of the study. As a possible future work, I would like to approach school redistricting as a multi-objective optimization problem and explore a hybrid deep-learning-metaheuristic framework to solve the problem. While the findings of this study are based on observations on two datasets, it would be worthwhile to conduct a study of more school districts. This would provide more general recommendations to planners when tasked with designing school boundaries.
Fanglan Chen is a PhD student in the Spatial Lab, advised by Dr. Chang-Tien Lu, at Virginia Tech. Her research focuses on graph neural networks, spatio-temporal data mining, and urban computing. She holds a MS in Computer Science and a MURP in Urban Planning from Virginia Tech. She is also a graduate student researcher at Virginia Tech’s Sanghani Center for Artificial Intelligence and Data Analytics.
Exploring Tradeoffs in Automated School Redistricting: Computational and Ethical Perspectives, Fanglan Chen, Subhodip Biswas, Zhiqian Chen, Shuo Lei, Naren Ramakrishnan, Chang-Tien Lu.