Spatial Optimization Techniques for School Redistricting

dc.contributor.authorBiswas, Subhodipen
dc.contributor.committeechairRamakrishnan, Narendranen
dc.contributor.committeememberLu, Chang Tienen
dc.contributor.committeememberNorth, Christopher L.en
dc.contributor.committeememberKarpatne, Anujen
dc.contributor.committeememberDavidson, Ianen
dc.contributor.departmentComputer Scienceen
dc.date.accessioned2022-06-04T08:01:00Zen
dc.date.available2022-06-04T08:01:00Zen
dc.date.issued2022-06-03en
dc.description.abstractIn 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.en
dc.description.abstractgeneralIn 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.en
dc.description.degreeDoctor of Philosophyen
dc.format.mediumETDen
dc.identifier.othervt_gsexam:34888en
dc.identifier.urihttp://hdl.handle.net/10919/110433en
dc.language.isoenen
dc.publisherVirginia Techen
dc.rightsCreative Commons Attribution 4.0 Internationalen
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/en
dc.subjectSpatial Optimizationen
dc.subjectRedistrictingen
dc.subjectCombinatorial Optimizationen
dc.subjectGeographic Clusteringen
dc.subjectMetaheuristicsen
dc.subjectSamplingen
dc.subjectInteger Programmingen
dc.titleSpatial Optimization Techniques for School Redistrictingen
dc.typeDissertationen
thesis.degree.disciplineComputer Science and Applicationsen
thesis.degree.grantorVirginia Polytechnic Institute and State Universityen
thesis.degree.leveldoctoralen
thesis.degree.nameDoctor of Philosophyen

Files

Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
Biswas_S_D_2022.pdf
Size:
25.89 MB
Format:
Adobe Portable Document Format