Sangam: A Confluence of Knowledge Streams

Memetic algorithms for Spatial Partitioning problems

Show simple item record

dc.creator Biswas, Subhodip
dc.creator Chen, Fanglan
dc.creator Chen, Zhiqian
dc.creator Lu, Chang-Tien
dc.creator Ramakrishnan, Naren
dc.date 2022-10-03T16:35:11Z
dc.date 2022-10-03T16:35:11Z
dc.date
dc.date 2022-10-03T07:45:04Z
dc.date.accessioned 2023-03-01T18:53:43Z
dc.date.available 2023-03-01T18:53:43Z
dc.identifier http://hdl.handle.net/10919/112056
dc.identifier https://doi.org/10.1145/3544779
dc.identifier http://hdl.handle.net/10919/112056
dc.identifier.uri http://localhost:8080/xmlui/handle/CUHPOERS/281756
dc.description 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 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, its applicability to different scenarios, and motivate future research directions.
dc.description Published version
dc.format application/pdf
dc.format application/pdf
dc.language en
dc.publisher ACM
dc.rights The author(s)
dc.title Memetic algorithms for Spatial Partitioning problems
dc.type Article - Refereed
dc.type Text


Files in this item

Files Size Format View
3544779.pdf 5.896Mb application/pdf View/Open

This item appears in the following Collection(s)

Show simple item record

Search DSpace


Advanced Search

Browse