Memetic algorithms for Spatial Partitioning problems

Subhodip Biswas, Fanglan Chen, Zhiqian Chen, Chang-Tien Lu, Naren Ramakrishnan

Abstract

Spatial optimization problems (SOPs) are characterized by spatial relationships governing the decision variables, objectives, and/or constraint functions. In this article, we focus on a specific type of SOP called spatial partitioning, which is a combinatorial problem due to the presence of discrete spatial units. Exact optimization methods do not scale with the size of the problem, especially within practicable time limits. This motivated us to develop population-based metaheuristics for solving such SOPs. However, the search operators employed by these population-based methods are mostly designed for real-parameter continuous optimization problems. For adapting these methods to SOPs, we apply domain knowledge in designing spatially-aware search operators for efficiently searching through the discrete search space while preserving the spatial constraints. To this end, we put forward a simple yet effective algorithm called swarm-based spatial memetic algorithm (SPATIAL) and test it on the school (re)districting problem. Detailed experimental investigations are performed on real-world datasets to evaluate the performance of SPATIAL. Besides, ablation studies are performed to understand the role of the individual components of SPATIAL. Additionally, we discuss how SPATIAL is helpful in the real-life planning process and its applicability to different scenarios and motivate future research directions.

Introduction

Spatial Optimization Problems (SOPs) present significant challenges for standard computational methods. A prime example is school redistricting, where hundreds of small "planning units" must be grouped into districts. Each district must satisfy strict geographic constraints: it must be contiguous (no isolated islands), population-balanced relative to school capacity, and compact in shape to avoid gerrymandering.

Because these units are discrete, the number of possible configurations grows exponentially, leading to a "combinatorial explosion." Traditional exact mathematical methods, such as Mixed-Integer Linear Programming (MILP), often fail to find feasible solutions for large datasets within reasonable timeframes. Conversely, general-purpose metaheuristics often lack the spatial awareness required to handle the jagged, constraint-heavy nature of geographic data. This research introduces SPATIAL, an algorithm designed to bridge this gap by incorporating spatial relationships directly into its search logic.

The SPATIAL Algorithm

The researchers propose the Swarm-based SPAatial Memetic ALgorithm (SPATIAL). As a memetic algorithm, it synergizes a global population-based search with local refinement techniques.

Graph-based representation of spatial partitioning, illustrating center nodes, source nodes, and zone boundaries.

The framework is built upon the Artificial Bee Colony (ABC) algorithm, which simulates the foraging behavior of honeybees. To adapt this to spatial partitioning, the authors developed several key components:

  • Spatially-Aware Recombination: Unlike standard algorithms that swap random data points, SPATIAL identifies shared boundaries between two candidate solutions and swaps geographic features. A specialized repair operator then uses graph-traversal logic (Breadth-First Search) to ensure that the resulting districts remain contiguous.
  • Local Search Refinement: The algorithm employs "flips," moving individual planning units between adjacent school zones to incrementally improve balance or compactness.
  • Dual-Objective Optimization: The search process targets two primary goals: Target Balance (aligning student enrollment with school capacity) and Target Compactness (measured via the Polsby-Popper score to ensure regular, non-elongated shapes).

Experimental Evaluation

The algorithm was rigorously tested using real-world Geographic Information System (GIS) data from two anonymous U.S. school districts.

Visualization of planning units and school locations in a real-world school district dataset.
  • District X: Comprises 453 planning areas and 57 elementary schools.
  • District Y: A larger-scale problem with 1,313 planning areas and 138 elementary schools.

The study utilized data from the 2020-2021 school year, a period marked by significant enrollment shifts due to the COVID-19 pandemic. These shifts created substantial imbalances in existing districts, providing a high-difficulty benchmark for the redistricting task.

Key Results and Insights

The experimental results highlight several advantages of the SPATIAL approach:

  • Superior Performance and Scalability: SPATIAL consistently outperformed common baselines, including Simulated Annealing (SA), Tabu Search (TS), and Stochastic Hill Climbing (SHC). Notably, while exact MILP methods failed to find feasible solutions for 4 out of 6 test cases within 24 hours, SPATIAL generated high-quality plans for all scenarios.
  • Effective Search Dynamics: The combination of local "crawling" (fine-tuning) and recombination-based "jumping" (escaping local optima) proved essential. The recombination operator allows the algorithm to explore diverse regions of the search space that local search alone cannot reach.
  • Real-World Utility: In District Y, SPATIAL improved the balance score from the existing plan's ~82% to approximately 95%, demonstrating its potential to significantly reduce school overcrowding.
  • Initialization Strategy: Starting the optimization from existing school boundaries (denoted as SPATIAL*) often yielded better results for reconfiguration tasks than starting from a blank slate.

Conclusion and Future Directions

While SPATIAL demonstrates robust performance, the authors identify areas for further development. The computational cost of calculating compactness scores remains high; future iterations might explore faster proxies like "edge cuts." Furthermore, the current model primarily optimizes for numerical and geometric metrics. Future research should integrate "ethical metrics," such as socioeconomic diversity, travel times, and the minimization of student displacement, to better support the complex human elements of school redistricting.

Summary updated

Abstract

Spatial optimization problems (SOPs) are characterized by spatial relationships governing the decision variables, objectives, and/or constraint functions. In this article, we focus on a specific type of SOP called spatial partitioning, which is a combinatorial problem due to the presence of discrete spatial units. Exact optimization methods do not scale with the size of the problem, especially within practicable time limits. This motivated us to develop population-based metaheuristics for solving such SOPs. However, the search operators employed by these population-based methods are mostly designed for real-parameter continuous optimization problems. For adapting these methods to SOPs, we apply domain knowledge in designing spatially-aware search operators for efficiently searching through the discrete search space while preserving the spatial constraints. To this end, we put forward a simple yet effective algorithm called swarm-based spatial memetic algorithm (SPATIAL) and test it on the school (re)districting problem. Detailed experimental investigations are performed on real-world datasets to evaluate the performance of SPATIAL. Besides, ablation studies are performed to understand the role of the individual components of SPATIAL. Additionally, we discuss how SPATIAL~is helpful in the real-life planning process and its applicability to different scenarios and motivate future research directions.
BibTeX
@article{biswas2023memetic,
  author = {Subhodip Biswas and Fanglan Chen and Zhiqian Chen and Chang-Tien Lu and Naren Ramakrishnan},
  title = {{Memetic algorithms for Spatial Partitioning problems}},
  journal = {ACM Trans. Spatial Algorithms Syst.},
  year = {2023},
  doi = {10.1145/3544779},
}
Figure