基于复合移动禁忌搜索的快速高效选区重划优化

# 基于复合移动禁忌搜索的快速高效选区重划优化

来源: https://arxiv.org/html/2605.06682

###### 摘要
空间选区重划是一个实际中的组合优化问题，需要高质量解、快速响应以及适应多目标标准和交互式调整的灵活性。核心挑战在于连通性约束：在整数规划或启发式搜索中强制实施连通性可能会严重缩小可行邻域，削弱探索能力，并使搜索陷入较差的局部最优解。我们提出了一种**复合移动禁忌搜索**（CM-Tabu），它在保持连通性的同时系统地扩展了禁忌搜索中的可行邻域空间。当边界单元无法单独重新分配以免断开其选区时，我们的方法识别出一个可以一起移动的最小单元集，或者一对（或多组）可以交换的单元，作为保持连通性的复合移动。通过分析每个选区的连通性图并使用割点（articulation points）和双连通分量（biconnected components），候选的单单元移动和复合移动在线性时间内生成。大量实验表明，与传统禁忌搜索和其他基线相比，所提出的方法在解质量、运行间鲁棒性和计算效率方面都有显著提升。例如，在费城案例中，该方法能够一致地达到人口均等性的理论全局最优解，并支持多目标权衡。CM-Tabu 提供了适合实际应用和决策支持工作流程的优化性能。

###### 关键词：组合优化，禁忌搜索，连通性约束，多目标，选区重划

\affiliation organization=Department of Land Surveying and Geo-Informatics, addressline=The Hong Kong Polytechnic University, Kowloon, city=Hong Kong, country=China

## 1 引言

许多现实世界的决策问题依赖于空间组合优化，包括政治选区重划、学区划分、服务区域设计和设施选址规划。在实践中，优化方法很少仅仅根据其在基准测试中是否能改进目标值来评判。相反，它必须 (i) 可靠地产生高质量解，(ii) 以适合迭代场景测试的快速响应速度完成，以及 (iii) 保持灵活性，以便决策者可以纳入多个标准和进行交互式调整。同时满足这些要求对于许多空间分区问题仍然具有挑战性。

政治选区重划是一个具有代表性的且对社会重要的例子。该任务在各个行政层级——如国会选区、州立法机构选区或市议会选区——重新绘制立法边界，同时在多个标准之间取得平衡，包括人口均等性、紧凑性以及保留政治或社区边界，并受到每个选区必须在地理上连通的硬约束。

人们提出了各种计算方法，包括聚类与区域生长、位置分配、空间划分、图划分、遗传算法、模拟退火、禁忌搜索，以及最近基于学习的方法。第 2 节提供了全面的回顾。虽然这些方法在特定环境中可能有效，但许多方法难以同时满足实际要求：有些速度快但解质量有限，有些可以优化目标但需要大量运行时间或敏感的参数调整，还有一些对多目标探索或交互式人工调整的支持很少。

核心挑战是**连通性约束**。在整数规划公式中，如果不引入大量辅助变量和约束，很难编码连通性，这严重限制了可扩展性和实际适用性。在启发式搜索（如爬山法、模拟退火、禁忌搜索）中，连通性通常通过两种方式处理：(i) 仅允许保持选区连通的移动，或 (ii) 自由生成候选解并过滤掉违反连通性的解。前者可能会大幅缩小可行邻域，而后者可能会浪费大量计算资源探索不可行状态；两者都削弱了探索能力，使得难以逃脱较差的局部最优解。

本文介绍了**复合移动禁忌搜索（CM-Tabu）**，这是一种快速有效的选区重划优化器，它通过在搜索过程中系统地扩展可行邻域空间同时保持连通性来解决这一瓶颈。核心思想是超越单单元重新分配或简单的成对交换。当边界单元无法单独移动以免断开其选区时，CM-Tabu 识别出一个可以一起移动的最小单元集作为保持连通性的复合移动；同样，在有益时，它考虑涉及多组单元的交换，同时保持连通性。单单元移动和复合移动通过分析每个选区的连通性图并使用割点（cut points）和双连通分量，在线性时间内高效生成。因此，CM-Tabu 在每次迭代中扩展可行邻域，而不损害可行性或效率，显著提高了逃脱局部最优解的能力。

我们通过大量实验评估了 CM-Tabu，包括对爱荷华州国会选区问题的大规模运行研究以及费城市议会案例的多目标研究，展示了与传统禁忌搜索和其他基线相比，在解质量、鲁棒性和运行时间效率方面的实质性改进。例如，在爱荷华州国会选区案例研究（将 99 个县划分为 5 个选区）中，1,000 次运行实验表明，我们的方法（CM-Tabu）提高了解质量和可靠性：中位人口偏差降低了 84%（从 2,627 降至 371），四分位距缩小了 93%（从 2,890 降至 192），同时保持每次运行亚秒级的运行时间。

除了选区重划，这种保持连通性的邻域扩展方法可以扩展到更广泛的分区和空间划分问题，如学区划分、服务区域设计和设施选址规划，其中需要连通性。本工作的贡献包括：(1) 基于最小复合移动和复合交换的保持连通性的邻域扩展，在硬连通性约束下大幅扩大了可行移动集；(2) 使用割点和双连通分量的线性时间移动生成算法，实现了大规模的实际应用；(3) 集成的 CM-Tabu 优化器和实证评估，展示了在真实选区重划案例研究中快速、有效且鲁棒的性能。

论文的其余部分组织如下。第 2 节回顾相关工作。第 3 节介绍 CM-Tabu，包括保持连通性的移动生成、目标评估和禁忌搜索过程。第 4 节报告实验结果，第 5 节总结并讨论。

## 2 相关工作

自动化选区重划算法大致可分为**自底向上的聚合方法**、**自顶向下的分割方法**、**基于启发的搜索方法**、**基于采样的方法**和**基于学习的方法**。这些类别在如何表示空间、处理约束（尤其是连通性）以及在优化质量与运行时间和实际可用性之间取得平衡方面存在差异。

### 2.1 自底向上的聚合方法

自底向上的聚合方法通过将“相似”的空间单元聚合到区域内来构建选区，通常在连通性约束下通过分层合并直到达到所需的选区数量。这一组包括经典的位置分配方法（Hess et al., 1965; Kalcsics et al., 2005; Ríos-Mercado et al., 2021）、多核生长技术（Vickrey, 1961; Gearhart and Liittschwager, 1969; Openshaw, 1977）和区域化方法（Guo, 2008; Guo et al., 2018）。聚合方法通常速度较快，并通过相邻单元扩展选区自然地保持连通性。然而，由于关键标准在增量生长过程中难以直接优化，生成的计划通常需要通过局部或元启发式搜索进行后续改进。

### 2.2 自顶向下的分割和基于优化的方法

自顶向下的分割方法从整个区域开始，将其划分为目标数量的选区。整数规划是一种代表性的自顶向下公式，因为它在一组决策变量上优化全局目标。然而，在实践中，表达核心选区重划约束——尤其是**地理连通性**——通常需要大量辅助变量和约束（Ligmann-Zielinska et al., 2008; Dugošija et al., 2020; Validi et al., 2022; Shahmizad and Buchanan, 2025），这限制了可扩展性和实际适用性（Cova and Church, 2000）。因此，当必须保证严格连通性时，整数线性规划（ILP）并不常用（Altman and McDonald, 2010）。

除了 ILP 外，其他基于优化的公式包括平衡质心幂图（Cohen-Addad et al., 2018）、多目标生成树模型（Kim, 2018）、基于中心的建模方法（Kong et al., 2019）、平等分区混合算法（Kong, 2021）、公平优化列生成方法（Gurnee and Shmoys, 2021）以及可扩展的多级多目标优化框架（Swamy et al., 2023, 2024）。

### 2.3 基于启发的搜索和元启发式

大量工作侧重于基于启发的搜索方法，这些方法从初始计划（通常通过随机快速生成）开始，并通过局部修改（如在相邻选区之间移动单元）迭代改进它。代表性方法包括局部贪心搜索或爬山法（Nagel, 1965）、模拟退火（Browdy, 1990; Gutiérrez-Andrade et al., 2019）、禁忌搜索（Bozkaya et al., 2003）、进化和遗传算法（Bergey et al., 2003; Xiao, 2008; Tomczyk and Kadziński, 2024）以及动态加权 Voronoi 图（Ricca et al., 2008）。基于轨迹的方法（如贪心、模拟退火和禁忌）在接受非改进移动和避免循环的方式上有所不同，这影响运行时间和解质量。在选区重划中，禁忌搜索通常有效，因为它可以通过禁忌列表和重启策略阻止立即反转，同时继续通过非改进步骤移动。进化方法在计划种群上操作，但通常需要额外的程序来在变异和交叉期间强制实施连通性（Xiao, 2008），并且选区重划的严格均等目标使得可行重组特别具有挑战性。

### 2.4 基于采样的集成和基于学习的方法

基于采样的方法（尤其是马尔可夫链蒙特卡洛及相关方法）广泛用于生成大量可行计划的集成，以对公平性和偏差进行统计分析（DeFord et al., 2020; Fifield et al., 2020; McCartan and Imai, 2023; Dobbs et al., 2023）。这些方法强调对可行计划空间的概率探索，而不是直接的目标优化（Kuehn et al., 2019）。最近，提出了基于学习和决策感知的优化方法，将公平性目标和政策考量纳入模型设计（Levin and Friedler, 2019; Cho and Cain, 2020; Ko et al., 2022; Chen et al., 2023; Ahmed et al., 2024）。此类方法通常依赖于高质量的训练数据或大型计划集成，生成成本高昂，并且由于空间结构、人口统计和法律约束的差异，在一个地理或机构背景下训练的模型很难直接转移到其他背景。

### 2.5 连通性约束和邻域瓶颈

在这些方法家族中，空间连通性通常通过两种方式处理。一种是通过目标设计间接鼓励连通性（例如，基于距离的惩罚），这不能保证最终计划的连通性。另一种是在整个优化过程中强制实施连通性。对于整数规划，强制实施连通性通常需要许多额外的变量和约束，使得大规模实施变得困难且低效。对于基于轨迹的方法（如贪心搜索或禁忌搜索），通常只允许不使选区断开的移动来强制实施连通性。虽然这种策略保证了可行性，但它可能会大幅减少允许的移动数量，削弱探索能力，并使难以逃脱局部最优解。这一瓶颈激发了本文开发的方法：而不是完全依赖单单元重新分配或简单交换，我们通过引入保持连通性的复合移动，在严格连通性下扩展可行搜索邻域，使基于轨迹的元启发式能够探索大得多的可行空间，在不牺牲可行性或效率的情况下实现更好的优化结果。

## 3 连通性约束下的优化：一种新方法

我们提出了一种针对具有硬连通性约束的优化问题的系统且高效的方法。许多元启发式——如爬山法、模拟退火和禁忌搜索——通过通过局部更改（移动）迭代修改当前解来运行，产生一个逐渐改进目标质量的解轨迹。然而，在连通性约束下，可行局部更改的集合可能变得极其有限：很大一部分边界单元无法单独移动而