通过复合移动禁忌搜索快速有效地重新划分优化

arXiv:2605.06682v1 公告类型：新 摘要：空间重划是一个实用的组合优化问题，需要高质量的解决方案、快速周转以及适应多标准目标和交互细化的灵活性。一个核心挑战是连续性约束：在整数规划或启发式搜索中强制连续性可能会严重缩小可行邻域，削弱探索，并使搜索陷入较差的局部最优。我们引入了一种复合移动禁忌搜索（CM-Tabu），​​它系统地扩展了禁忌搜索中的可行邻域空间，同时保持了连续性。当边界单元无法在不断开其分区的情况下单独重新分配时，我们的方法会识别可以一起移动的最小单元集，或可以切换的一对单元（或单元集），作为连续性保留复合移动。通过使用铰接点和双连通分量分析每个区域的邻接图，可以在线性时间内生成候选的单一单元和复合移动。大量的实验表明，相对于传统的 Tabu 搜索和其他基线，所提出的方法大大提高了解决方案质量、运行间的鲁棒性和计算效率。例如，在费城的案例中，该方法可以始终如一地实现人口平等的理论全局最优，并支持多标准权衡。 CM-Tabu 提供适合实际实践和决策支持工作流程的优化性能。