Fast and Effective Redistricting Optimization via Composite-Move Tabu Search

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.

📋 한 줄 요약

**[조합 최적화/공간 분할]** 연결성(contiguity) 제약을 유지하면서 후보 이웃 공간을 합성 이동(composite move)으로 확장한 새로운 Tabu 탐색 CM-Tabu로 정치적 선거구 재획정 문제를 빠르고 안정적으로 해결.

🎯 핵심 기여도

단일 단위가 개별적으로 이동 불가할 때 함께 이동/교환 가능한 최소 단위 집합을 찾아 합성 이동으로 정의
각 구역의 연결성 그래프를 articulation point와 biconnected component로 분석해 후보 이동을 선형 시간에 생성
Philadelphia 사례에서 인구 균등의 이론적 전역 최적해를 지속적으로 달성
다목적 거래(multi-criteria trade-off)와 대화형 정제 워크플로우를 지원하는 실용적 최적화 도구 제공

💡 핵심 아이디어

선거구 재획정의 연결성 제약은 정수계획법이나 휴리스틱 탐색의 이웃 공간을 극도로 좁혀 탐험 능력을 약화시킨다. 단일 단위 이동만 보면 막히는 지점에서, "함께 움직여야 연결이 끊기지 않는 최소 단위 집합"을 합성 이동으로 자동 식별해 탐색 공간을 본질적으로 확장한다.

🔬 기술적 접근법

**모델/방법론**: Composite-Move Tabu Search(CM-Tabu) — 전통 Tabu 검색에 합성 이동을 결합
**핵심 기법**: (1) 구역의 connectivity graph에서 articulation point/biconnected component 분석, (2) 연결성 보존을 만족하는 최소 단위 그룹 이동·교환 식별, (3) 후보 단일/합성 이동을 선형 시간에 생성

📊 주요 결과

전통 Tabu 검색 및 다양한 베이스라인 대비 해 품질·반복 간 일관성·계산 효율 모두 개선
Philadelphia 사례에서 인구 균등 측면 전역 최적해 일관 달성
다목적 트레이드오프·대화형 의사결정 워크플로우에 적합한 응답성 확보

💭 의의 및 한계

**의의**: 연결성 제약이 핵심인 다양한 공간 분할 문제(학군, 응급 서비스 구역, 영업 구역)에 일반화 가능한 메타 휴리스틱 기법을 제시한다. **한계**: 정치적 공정성·게리맨더링 방지와 같은 규범적 기준에 대한 직접 최적화는 별도 다목적 가중치 설계가 필요하며, 매우 큰 규모 인스턴스에서 합성 이동 후보 생성의 메모리 비용이 증가할 수 있다.

🚀 실용적 활용

선거구 재획정 의사결정 지원 도구
학교·소방·응급 의료 구역 설정
영업 지역 분할 등 공간 운영 최적화 일반