In countries like the US, public school systems function through school districts, which are geographical areas where schools share the same administrative structure and are often coterminous with the boundary of a city or a county. School districts play an important role in the functioning of society. In a well-run school district with safe and well-functioning schools, graduating enough students can enhance the quality of life in its area. Conversely, a poorly run district may cause growth in the area to be far less than surrounding areas, or even a decline in population over time. To promote the efficient functioning of the school district, the boundaries of public schools are redrawn from time to time by the school board/planning officials. In the majority of the cases, this process of redrawing the school boundaries, also called school redistricting or school boundary formation, is done manually by the planners and involves hand-drawn maps. Given the rapid advancements in GIS made in the last decade and the availability of high-quality geospatial data, we opine that an objective treatment of the school redistricting problem by a data-driven model can assist the school board/ decision-makers by providing them with automated plans. These automated plans may serve as possible suggestions to the planners, who can adapt them to prepare their own plans in the way they see fit based on their subjective knowledge and expertise. In this dissertation, we propose algorithmic techniques for solving the problem of (school) redistricting, which is an NP-hard problem. We primarily investigate optimization-based algorithms for solving the problem. Our approaches include (i) clustering, (ii) local search, and (iii) memetic algorithms. We also propose ways of solving the problem using exact methods and fair redistricting techniques based on ethical considerations. The techniques developed here are generic enough to be applied to other redistricting problems with some degree of modification in the objective function and constraint-handling techniques. The source code and corresponding datasets are available at https://github.com/subhodipbiswas/schoolredistricting. / Doctor of Philosophy / In many countries, public school systems function through school districts, which are geographical areas where schools share the same administrative structure and are often coterminous with the boundary of a city or a county. To promote efficient functioning of the school district, the boundaries of public schools are redrawn from time to time by the school board/planning officials. In the majority of the cases, this process of redrawing the school boundaries, also called school redistricting, is done manually by the planners and involves hand-drawn maps. Given the rapid advancements in GIS made in the last decade and the availability of high-quality geospatial data, we opine that an objective treatment of the school redistricting problem by a data-driven model can assist the school board/ decision-makers by providing them with automated plans. In this presentation, we propose algorithmic techniques for solving the school redistricting problem. Our approaches include (i) clustering, (ii) local search, and (iii) memetic algorithms. We also show that MCMC-based techniques can aid in enabling exact methods to operate on this problem. Lastly, we briefly highlight ethical considerations involved in the process of school redistricting and throw light on some ways to devise more ethically-aware strategies for doing school redistricting. The results indicate that the proposed methods could be a valuable decision-making tool for school officials.
| Identifer | oai:union.ndltd.org:VTETD/oai:vtechworks.lib.vt.edu:10919/110433 |
| Date | 03 June 2022 |
| Creators | Biswas, Subhodip |
| Contributors | Computer Science, Ramakrishnan, Narendran, Lu, Chang Tien, North, Christopher L., Karpatne, Anuj, Davidson, Ian |
| Publisher | Virginia Tech |
| Source Sets | Virginia Tech Theses and Dissertation |
| Language | English |
| Detected Language | English |
| Type | Dissertation |
| Format | ETD, application/pdf |
| Rights | Creative Commons Attribution 4.0 International, http://creativecommons.org/licenses/by/4.0/ |
Page generated in 0.0023 seconds