空間的な選挙区割り（redistricting）は、高品質な解、迅速なターンアラウンド、そして多基準の目的（人口均等、地理的コンパクト性、政治的正義など）や対話的な調整への柔軟性が求められる実用的な組合せ最適化問題です。中心的な課題は接続性制約（contiguity constraint）です。整数計画法やヒューリスティック探索において接続性を強制すると、実行可能な近傍が極端に縮小し、探索が弱まって貧弱な局所最適解に陥りやすくなります。
この課題に対処するため、Hai Jin氏とDiansheng Guo氏は2026年4月24日にarXivに提出した論文で、複合移動タブー探索（CM-Tabu）を導入しました。これは接続性を維持しながら、タブー探索の実行可能近傍空間を体系的に拡大する手法です。CM-Tabuの核心は、境界単位を個別に再割り当てすると選挙区が非接続になる場合に、一緒に移動できる最小単位セット、または交換可能な単位（またはセット）のペアを特定し、接続性を保持する複合移動として扱う点にあります。候補となる単位移動と複合移動は、各選挙区の接続性グラフを関節点（articulation points）と二重連結成分（biconnected components）を用いて解析することで線形時間で生成されます。このメカニズムにより、探索中の実行可能な近傍が大幅に拡大され、従来の接続性制約による探索停滞を回避できます。
広範な実験により、CM-Tabuは従来のタブー探索や他のベースラインと比較して、解の質、実行間のロバスト性、計算効率を大幅に向上することが示されました。特にフィラデルフィアの事例では、人口均等（population equality）の理論的全局最適解を一貫して達成し、人口均等、コンパクト性、政治的正義などの多基準トレードオフをサポートします。これらの結果は、CM-Tabuが現実の実務や意思決定支援ワークフローに適した最適化性能を提供することを示しています。
本研究は選挙区割りに効率的なアルゴリズムを提供するだけでなく、施設配置や地域計画など接続性制約のある他の空間最適化問題にも応用可能な一般的な枠組みを提示しています。論文はarXivに提出され、人工知能（cs.AI）およびコンピュータと社会（cs.CY）のカテゴリに収録されています。DOIは10.48550/arXiv.2605.06682、提出日は2026年4月24日です。