提出新型禁忌搜索方法,高效解决选区划分中连通性难题。
Fast and Effective Redistricting Optimization via Composite-Move Tabu Search

- 通过复合移动策略扩展可行解空间,保持选区连通性。
- 在费城案例中稳定达到人口均衡理论最优解。
- 适合需要多目标权衡与交互优化的现实决策场景。
空间选区划分是需高质量解、快速响应且支持多目标灵活调整的组合优化问题。核心挑战在于连通性约束:传统整数规划或启发式搜索中强制连通会严重压缩可行邻域,削弱探索能力并陷入局部最优。本文提出复合移动禁忌搜索(CM-Tabu),系统扩大禁忌搜索的可行邻域,同时保持连通性。当边界单元无法单独重分配而不破坏其所在选区连通时,该方法识别最小移动单元集或可交换的单元对(或集合),作为保持连通性的复合移动。通过分析各选区的连通图,利用割点和双连通分量,在线性时间内生成候选单单元与复合移动。大量实验表明,相比传统禁忌搜索及其他基线方法,本方法显著提升解质量、运行鲁棒性和计算效率。例如,在费城案例中,该方法能持续达到人口均等的理论全局最优,并支持多目标权衡。CM-Tabu具备满足实际应用与决策支持流程的优化性能。
原文摘要 · Abstract (English)
Spatial redistricting is a practical combinatorial optimization problem that demands high-quality solutions, rapid turnaround, and flexibility to accommodate multi-criteria objectives and interactive refinement. A central challenge is the contiguity constraint: enforcing contiguity in integer-programming or heuristic search can severely shrink the feasible neighborhood, weaken exploration, and trap the search in poor local optima. We introduce a composite-move Tabu search (CM-Tabu) that systematically expands the feasible neighborhood space in Tabu search while preserving contiguity. When a boundary unit cannot be reassigned individually without disconnecting its district, our method identifies a minimal set of units that can move together, or a pair of units (or sets of units) that can be switched, as a contiguity-preserving composite move. Candidate single-unit and composite moves are generated in linear time by analyzing each district's contiguity graph using articulation points and biconnected components. Extensive experiments demonstrate that the proposed approach substantially improves solution quality, run-to-run robustness, and computational efficiency relative to traditional Tabu search and other baselines. For example, in the Philadelphia case, the approach can consistently attain the theoretical global optimum in population-equality and support multi-criteria trade-offs. CM-Tabu delivers optimization performance suitable for real-world practices and decision-support workflows.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。