Fast and Effective Redistricting Optimization via Composite-Move Tabu Search

# Fast and Effective Redistricting Optimization via Composite-Move Tabu Search
Source: [https://arxiv.org/html/2605.06682](https://arxiv.org/html/2605.06682)
###### Abstract

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\.

###### keywords:

Combinatorial optimization , Tabu search , Contiguity constraint , Multicriteria , Redistricting

\\affiliation

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

## 1Introduction

Many real\-world decision\-making problems rely on spatial combinatorial optimization, including political redistricting, school districting, service territory design, and facility location planning\. In practice, an optimization method is rarely judged solely by whether it can improve an objective value on a benchmark\. Instead, it must \(i\) reliably produce high\-quality solutions, \(ii\) do so with fast turnaround suitable for iterative scenario testing, and \(iii\) remain flexible so that decision makers can incorporate multiple criteria and interactive refinement\. Achieving these requirements simultaneously remains challenging for many spatial districting problems\.

Political redistricting is a representative and societally important example\. The task redraws legislative boundaries at various administrative levels—such as congressional, state legislative, or city council districts—while balancing multiple criteria including population equality, compactness, and preservation of political or community boundaries, under the hard constraint that each district must be geographically contiguous\.

A wide range of computational approaches have been proposed, including clustering and region growing, location\-allocation, space partitioning, graph partitioning, genetic algorithms, simulated annealing, Tabu search, and more recently, learning\-based methods\. A comprehensive review is provided in Section 2\. While these methods can be effective in specific settings, many struggle to meet practical requirements simultaneously: some are fast but yield limited solution quality, some can optimize objectives but require extensive runtime or sensitive parameter tuning, and others provide little support for multi\-criteria exploration or iterative human\-guided adjustment\.

A central challenge is thecontiguity constraint\. In integer\-programming formulations, contiguity is difficult to encode without introducing large numbers of auxiliary variables and constraints, which severely limits scalability and practical applicability\. In heuristic search \(e\.g\., hill climbing, simulated annealing, Tabu search\), contiguity is commonly handled in one of two ways: \(i\) allowing only moves that keep districts contiguous, or \(ii\) generating candidate solutions freely and filtering out those that violate contiguity\. The former can drastically shrink the feasible neighborhood, while the latter can waste substantial computation exploring infeasible states; both weaken exploration and make it difficult to escape poor local optima\.

This paper introduces*Composite\-Move Tabu search \(CM\-Tabu\)*, a fast and effective redistricting optimizer that addresses this bottleneck by systematically expanding the feasible neighborhood space while preserving contiguity throughout the search\. The key idea is to go beyond single\-unit reassignment or simple pair swaps\. When a boundary unit cannot be moved individually without disconnecting its district, CM\-Tabu identifies a minimal set of units that can move together as a contiguity\-preserving composite move; similarly, when beneficial, it considers switches that may involve sets of units while maintaining contiguity\. Single\-unit and composite moves are generated efficiently in linear time by analyzing each district’s contiguity graph using articulation points \(cut points\) and biconnected components\. As a result, CM\-Tabu expands the feasible neighborhood at each iteration without compromising feasibility or efficiency, substantially improving the ability to escape local optima\.

We evaluate CM\-Tabu through extensive experiments, including a large\-run study on the Iowa congressional problem and a multi\-criteria Philadelphia City Council case study, demonstrating substantial improvements in solution quality, robustness, and runtime efficiency compared with traditional Tabu search and other baselines\. For example, in the Iowa congressional case study \(grouping 99 counties into 5 districts\), 1,000\-run experiments show that our approach \(CM\-Tabu\) improves both solution quality and reliability: the median population deviation decreases by 84% \(from 2,627 to 371\) and the interquartile range shrinks by 93% \(from 2,890 to 192\), while maintaining sub\-second runtime per run\. Beyond redistricting, this contiguity\-preserving neighborhood expansion approach can be extended to a broader class of districting and spatial partitioning problems where connectivity is required, such as school districting, service territory design, and facility location planning\.

The contributions of this work include: \(1\) a contiguity\-preserving neighborhood expansion based on minimal composite moves and composite switches that substantially enlarges the feasible move set under hard contiguity constraints; \(2\) a linear\-time move\-generation algorithm using articulation points and biconnected components, enabling practical use at scale; and \(3\) an integrated CM\-Tabu optimizer and empirical evaluation showing fast, effective, and robust performance on real redistricting case studies\.

The remainder of the paper is organized as follows\. Section 2 reviews related work\. Section 3 presents CM\-Tabu, including contiguity\-preserving move generation, objective evaluation, and the Tabu search procedure\. Section 4 reports experimental results, and Section 5 concludes with discussion\.

## 2Related Work

Automated redistricting algorithms can be broadly classified into*bottom\-up agglomerative methods*,*top\-down divisive methods*,*heuristic\-based search methods, sampling\-based methods, and learning\-based methods*\. These categories differ in how they represent space, handle constraints \(especially contiguity\), and balance optimization quality against runtime and practical usability\.

### 2\.1Bottom\-up agglomerative methods

Bottom\-up agglomerative methods build districts by aggregating “similar” spatial units into regions under a contiguity constraint, often through hierarchical merging until reaching the desired number of districts\. This group includes classical location\-allocation methods\(Hesset al\.,[1965](https://arxiv.org/html/2605.06682#bib.bib25); Kalcsicset al\.,[2005](https://arxiv.org/html/2605.06682#bib.bib26); Ríos\-Mercadoet al\.,[2021](https://arxiv.org/html/2605.06682#bib.bib42)\), multi\-kernel growth techniques\(Vickrey,[1961](https://arxiv.org/html/2605.06682#bib.bib49); Gearhart and Liittschwager,[1969](https://arxiv.org/html/2605.06682#bib.bib17); Openshaw,[1977](https://arxiv.org/html/2605.06682#bib.bib39)\), and regionalization methods\(Guo,[2008](https://arxiv.org/html/2605.06682#bib.bib22); Guoet al\.,[2018](https://arxiv.org/html/2605.06682#bib.bib20)\)\. Agglomerative methods are typically fast and naturally maintain contiguity by expanding districts through adjacent units\. However, because key criteria are difficult to optimize directly during incremental growth, the resulting plans often require subsequent improvement by local or metaheuristic search\.

### 2\.2Top\-down divisive and optimization\-based methods

Top\-down divisive methods begin with the whole region and partition it into the target number of districts\. Integer programming is a representative top\-down formulation because it optimizes a global objective over a set of decision variables\. In practice, however, expressing core redistricting constraints—especially*geographic contiguity*—often requires many auxiliary variables and constraints\(Ligmann\-Zielinskaet al\.,[2008](https://arxiv.org/html/2605.06682#bib.bib34); Dugošijaet al\.,[2020](https://arxiv.org/html/2605.06682#bib.bib14); Validiet al\.,[2022](https://arxiv.org/html/2605.06682#bib.bib48); Shahmizad and Buchanan,[2025](https://arxiv.org/html/2605.06682#bib.bib43)\), which limits scalability and practical applicability\(Cova and Church,[2000](https://arxiv.org/html/2605.06682#bib.bib11)\)\. As a result, integer linear programming \(ILP\) is not commonly used when strict contiguity must be guaranteed\(Altman and McDonald,[2010](https://arxiv.org/html/2605.06682#bib.bib3)\)\. Beyond ILP, additional optimization\-based formulations include balanced centroidal power diagrams\(Cohen\-Addadet al\.,[2018](https://arxiv.org/html/2605.06682#bib.bib10)\), multi\-objective spanning tree models\(Kim,[2018](https://arxiv.org/html/2605.06682#bib.bib28)\), center\-based modeling approaches\(Konget al\.,[2019](https://arxiv.org/html/2605.06682#bib.bib30)\), hybrid algorithms for equal districting\(Kong,[2021](https://arxiv.org/html/2605.06682#bib.bib31)\), fairness\-optimized column generation methods\(Gurnee and Shmoys,[2021](https://arxiv.org/html/2605.06682#bib.bib23)\), and scalable multilevel multi\-objective optimization frameworks\(Swamyet al\.,[2023](https://arxiv.org/html/2605.06682#bib.bib44),[2024](https://arxiv.org/html/2605.06682#bib.bib45)\)\.

### 2\.3Heuristic\-based search and metaheuristics

A large body of work focuses on heuristic\-based search methods that start from an initial plan \(often generated quickly via random growth\) and iteratively improve it through local modifications such as moving units between neighboring districts\. Representative approaches include local greedy search or hill climbing\(Nagel,[1965](https://arxiv.org/html/2605.06682#bib.bib37)\), simulated annealing\(Browdy,[1990](https://arxiv.org/html/2605.06682#bib.bib7); Gutiérrez\-Andradeet al\.,[2019](https://arxiv.org/html/2605.06682#bib.bib24)\), Tabu search\(Bozkayaet al\.,[2003](https://arxiv.org/html/2605.06682#bib.bib6)\), evolutionary and genetic algorithms\(Bergeyet al\.,[2003](https://arxiv.org/html/2605.06682#bib.bib5); Xiao,[2008](https://arxiv.org/html/2605.06682#bib.bib50); Tomczyk and Kadziński,[2024](https://arxiv.org/html/2605.06682#bib.bib47)\), and dynamically weighted Voronoi diagrams\(Riccaet al\.,[2008](https://arxiv.org/html/2605.06682#bib.bib41)\)\.

Trajectory\-based methods \(e\.g\., greedy, simulated annealing, and Tabu\) differ in how they accept non\-improving moves and how they avoid cycling, which affects both runtime and solution quality\. In redistricting, Tabu search is often effective because it can continue moving through non\-improving steps while discouraging immediate reversals through a tabu list and restart strategy\. Evolutionary approaches operate on populations of plans but typically require additional procedures to enforce contiguity during mutation and crossover\(Xiao,[2008](https://arxiv.org/html/2605.06682#bib.bib50)\), and redistricting’s strict equality objectives can make feasible recombination especially challenging\.

### 2\.4Sampling\-based ensembles and learning\-based approaches

Sampling\-based approaches \(notably Markov chain Monte Carlo and related methods\) are widely used to generate large ensembles of feasible plans for statistical analysis of fairness and bias\(DeFordet al\.,[2020](https://arxiv.org/html/2605.06682#bib.bib12); Fifieldet al\.,[2020](https://arxiv.org/html/2605.06682#bib.bib15); McCartan and Imai,[2023](https://arxiv.org/html/2605.06682#bib.bib36); Dobbset al\.,[2023](https://arxiv.org/html/2605.06682#bib.bib13)\)\. These methods emphasize probabilistic exploration of the feasible plan space rather than direct objective optimization\(Kuenget al\.,[2019](https://arxiv.org/html/2605.06682#bib.bib32)\)\. More recently, learning\-based and decision\-aware optimization approaches have been proposed to incorporate fairness objectives and policy considerations into model design\(Levin and Friedler,[2019](https://arxiv.org/html/2605.06682#bib.bib33); Cho and Cain,[2020](https://arxiv.org/html/2605.06682#bib.bib9); Koet al\.,[2022](https://arxiv.org/html/2605.06682#bib.bib29); Chenet al\.,[2023](https://arxiv.org/html/2605.06682#bib.bib8); Ahmedet al\.,[2024](https://arxiv.org/html/2605.06682#bib.bib1)\)\. Such approaches often depend on high\-quality training data or large plan ensembles that can be expensive to generate, and models trained in one geographic or institutional context can be difficult to transfer directly to others due to differences in spatial structure, demographics, and legal constraints\.

### 2\.5Contiguity constraint and neighborhood bottleneck

Across these families of methods, spatial contiguity is typically handled in one of two ways\. One is to encourage contiguity indirectly through objective design \(e\.g\., distance\-based penalties\), which cannot guarantee contiguity in the final plan\. The other is to enforce contiguity throughout the optimization process\. For integer programming, enforcing contiguity generally requires many additional variables and constraints, making it difficult and inefficient at scale\. For trajectory\-based methods such as greedy search or Tabu search, contiguity is commonly enforced by permitting only those moves that do not disconnect districts\. While this strategy guarantees feasibility, it can dramatically reduce the number of allowable moves, weaken exploration, and make it difficult to escape local optima\.

This bottleneck motivates the approach developed in this paper: rather than relying exclusively on single\-unit reassignment or simple swaps, we expand the feasible search neighborhood under strict contiguity by introducing contiguity\-preserving composite moves, enabling trajectory\-based metaheuristics to explore a much larger feasible space and achieve better optimization results without sacrificing feasibility or efficiency\.

## 3Optimization under Contiguity Constraint: A New Approach

We present a systematic and efficient approach for optimization problems with a hard contiguity constraint\. Many metaheuristics—such as hill climbing, simulated annealing, and Tabu search—operate by iteratively modifying a current solution through local changes \(moves\), producing a trajectory of solutions that gradually improves objective quality\. Under contiguity constraints, however, the set of feasible local changes can become extremely limited: a large fraction of boundary units cannot be moved individually without disconnecting the source district, and many seemingly reasonable swaps also violate contiguity\. This dramatically reduces the feasible search neighborhood and weakens the search’s ability to escape local optima\.

Our approach addresses this bottleneck by explicitly analyzing within\-district connectivity structure and expanding the feasible neighborhood while preserving contiguity throughout the search\. At each iteration, we identify all candidate moves available under the current plan, including both*traditional single\-unit moves*and*new composite \(multi\-unit\) moves*\. When a boundary unit cannot be reassigned individually due to contiguity, we construct a minimal set of units that can move together such that contiguity is maintained in both the source and destination districts after the move\. Intuitively, these composite moves “unlock” boundary adjustments that are infeasible under single\-unit\-only search, substantially enlarging the feasible neighborhood at each step\.

The same contiguity\-aware framework also supports*switch operations*\. Traditional trajectory\-based methods often consider pairwise swaps to improve strict criteria such as population equality\. In our setting, a switch may also involve two composite moves \(each potentially consisting of multiple units\), enabling contiguity\-preserving exchanges that are not reachable through single\-unit swaps alone\.

The neighborhood\-expansion mechanism described above can be integrated with multiple trajectory\-based optimizers\. In principle, it can strengthen any method whose core operation is “enumerate feasible local changes → select the best move → update the plan\.” In our experiments, combining this mechanism with*Tabu search*yields the strongest overall performance, producing consistently higher\-quality solutions with strong run\-to\-run reliability\. We therefore present the integrated method asComposite\-Move Tabu search \(CM\-Tabu\)\.

In addition to improved optimization power, the proposed approach is designed for practical efficiency\. Candidate single\-unit and composite moves are generated in linear time by analyzing each district’s contiguity graph using articulation points \(cut points\) and biconnected components, allowing fast move enumeration and efficient scoring\. Because CM\-Tabu is efficient, it can also be repeated from different random initial plans to generate a collection of high\-quality alternative solutions, supporting interactive evaluation in decision\-support settings\.*Algorithm[1](https://arxiv.org/html/2605.06682#algorithm1)*summarizes the overall workflow\.

1\. Initialization:Randomly generate an initial contiguous plan \(Algorithm[2](https://arxiv.org/html/2605.06682#algorithm2)\);

2\. Optimization:repeat a–c steps until a stopping condition is met

a\.Enumerate all feasible candidate moves \(single\-unit and composite\) \(Algorithm[3](https://arxiv.org/html/2605.06682#algorithm3)\);

b\.Select the best move or switch, according to an objective function

ff;

c\.Apply the move/switch; update Tabu memory and record the best plan found;

3\. Output:Return the best plan encountered during the search;

4\. Repetition \(optional\):Repeat steps 1–3 to produce alternative high\-quality plans\.

Algorithm 1Overall Optimization Workflow of Our Approach \(CM\-Tabu\)The remainder of Section 3 details each component of CM\-Tabu: initialization under contiguity \(Section 3\.1\), candidate move generation including composite moves and valid switches \(Section 3\.2\), objective functions and efficient evaluation \(Section 3\.3\), and the full CM\-Tabu optimization procedure \(Section 3\.4\)\.

### 3\.1Initialization under Contiguity Constraint

We generate an initial redistricting plan using a simple*random seed\-growing*procedure that guarantees contiguity\. The input is a set of spatial units \(for example, counties, precincts, or wards\) together with their contiguity relationships \(who touches whom\)\. The goal is to construct a plan with a specified number of districts such that every unit is assigned to exactly one district, and every district is geographically contiguous\.

The procedure works as follows\. First, it randomly selects the required number of units as*seeds*, and each seed becomes the starting unit of one district\. Then, districts grow one unit at a time\. During growth, each district repeatedly adds one unassigned neighboring unit \(chosen at random\) from its current boundary\. This initialization method is intentionally randomized and does not attempt to optimize population equality, compactness, or any other criterion\. This is appropriate for CM\-Tabu because the optimization phase will improve the objective values\. In addition, random initialization makes it easy to run the optimizer multiple times from different starting plans, which improves robustness and produces diverse high\-quality alternatives for interactive decision support\.

Inputs :

SS: set of spatial units \(there are

nnunits in total\);

CC: contiguity structure \(for example, an adjacency list or adjacency matrix\);

rr: number of districts \(

1<r≪n1<r\\ll n\);

Output:An initial plan consisting of

rrcontiguous districts that collectively cover all units

Randomly select

rrdifferent units from

SS, each representing a district;

while*all units are not yet assigned*do

foreach*district \(in turn\)*do

if*district has unassigned neighboring units*then

Randomly select one of the district’s unassigned neighboring units and add it to the district;

Output the resulting plan as the initial plan;

Algorithm 2Initialization \(seed\-growing under contiguity\)
### 3\.2Candidate Moves under Contiguity Constraint

Given an initial plan with*r*districts, we use Tabu search to optimize an objective function\. Tabu search is a trajectory\-based method that iteratively reassigns units between neighboring districts to seek improved solutions\. We present the objective function in Section 3\.3 and the full Tabu procedure in Section 3\.4\. Here we focus on how the contiguity constraint creates major challenges for optimization and how our method addresses them\.

Most existing trajectory\-based methods consider only single\-unit moves \(moving one unit at a time\) or pairwise switches \(swapping two units\) at each iteration\. Under a hard contiguity constraint, however, the feasible neighborhood defined by such moves can be extremely limited\. Figure[1](https://arxiv.org/html/2605.06682#S3.F1)illustrates this issue using a simple example of 25 spatial units grouped into three districts: A, B, and C\. Between districts A and B, for example, only three units \(1, 5, 14\) can move from A to B and only two units \(6, 17\) can move from B to A without breaking contiguity\. Among these five units, only four pairs can be switched \(1 with 17; 5 with 6; 5 with 17; and 14 with 6\)\. Therefore, traditional methods provide only nine feasible moves \(single\-unit moves or pair switches\) between districts A and B\. By contrast, our approach identifies nineteen feasible moves between A and B, including single\-unit moves, contiguity\-preserving composite moves, and valid pair switches \(Figure[1](https://arxiv.org/html/2605.06682#S3.F1)and Table[1](https://arxiv.org/html/2605.06682#S3.T1)\)\. This doubles the number of feasible options per iteration; over T iterations, that multiplicative gain compounds into an exponential increase in the number of reachable move sequences \(roughly two to the power of T\)\.

![Refer to caption](https://arxiv.org/html/2605.06682v1/figures/Figure1.jpg)Figure 1:An example data set to demonstrate candidate moves under contiguity constraint\. See Table[1](https://arxiv.org/html/2605.06682#S3.T1)for the candidate moves with traditional methods and the new method\.Table 1:Candidate moves for the data shown in Figure[1](https://arxiv.org/html/2605.06682#S3.F1)\.Traditional MethodsOur ApproachDirectionSingle\-Unit MovesSwitchMovesSingle\-Unit and Composite Moves\(Cut points are underlined\)SwitchMovesA→BA\\rightarrow B\{1\},\{5\},\{14\}\\\{1\\\},\\\{5\\\},\\\{14\\\}4 switchmoves\{1\},\{5\},\{14\},\{2¯,1\},\{10¯,14\}\\\{1\\\},\\\{5\\\},\\\{14\\\},\\\{\\underline\{2\},1\\\},\\\{\\underline\{10\},14\\\}10 switchmovesA←BA\\leftarrow B\{6\},\{17\}\\\{6\\\},\\\{17\\\}\{6\},\{17\},\{11¯,9,17\},\{9¯,17\}\\\{6\\\},\\\{17\\\},\\\{\\underline\{11\},9,17\\\},\\\{\\underline\{9\},17\\\}A→CA\\rightarrow C\{14\}\\\{14\\\}1 switchmove\{14\},\{10¯,14\}\\\{14\\\},\\\{\\underline\{10\},14\\\}1 switchmoveA←CA\\leftarrow C\{15\}\\\{15\\\}\{15\},\{21¯,15,23\}\\\{15\\\},\\\{\\underline\{21\},15,23\\\}B→CB\\rightarrow C\{8\},\{12\},\{17\}\\\{8\\\},\\\{12\\\},\\\{17\\\}6 switchmoves\{8\},\{12\},\{17\},\{11¯,9,17\},\{9¯,17\}\\\{8\\\},\\\{12\\\},\\\{17\\\},\\\{\\underline\{11\},9,17\\\},\\\{\\underline\{9\},17\\\}18 switchmovesB←CB\\leftarrow C\{13\},\{18\}\\\{13\\\},\\\{18\\\}\{13\},\{18\},\{16¯,13\},\{21¯,15,23\}\\\{13\\\},\\\{18\\\},\\\{\\underline\{16\},13\\\},\\\{\\underline\{21\},15,23\\\},\{19¯,13,16,20,24\},\{22¯,15,21,23\}\\\{\\underline\{19\},13,16,20,24\\\},\\\{\\underline\{22\},15,21,23\\\}Total23 moves53 moves#### 3\.2\.1Single\-Unit Moves and Composite Moves

To expand the search space under a hard contiguity constraint, our approach systematically analyzes within\-district adjacency and constructscomposite movesfor boundary units that cannot move independently\.

Specifically, if a boundary unit*u*lies between two districts but cannot be reassigned by itself without breaking contiguity, our method identifies a*minimal set of units*\(including*u*\) that can be moved together so that contiguity is preserved in both the source and destination districts after the move\. For example, in Figure[1](https://arxiv.org/html/2605.06682#S3.F1), unit 10 in district A cannot move to district B as a single\-unit move, but it can move together with unit 14 as a composite move\. Similarly, eight units in Figure[1](https://arxiv.org/html/2605.06682#S3.F1)\(2 and 10 in A; 9 and 11 in B; and 16, 19, 21, and 22 in C\) cannot move under traditional single\-unit or simple\-swap methods, yet each becomes movable through a composite move in our approach\. Table[1](https://arxiv.org/html/2605.06682#S3.T1)summarizes the single\-unit and composite moves produced by our method\.

This neighborhood expansion has an immediate practical impact\. For the example in Figure[1](https://arxiv.org/html/2605.06682#S3.F1), traditional Tabu search yields 23 feasible moves \(single\-unit moves plus valid pair switch moves\), while our method yields 53 \(Table[1](https://arxiv.org/html/2605.06682#S3.T1)\)\. Because the neighborhood is evaluated repeatedly over many iterations, expanding the feasible move set at each iteration substantially improves the ability to escape poor local optima and increases run\-to\-run reliability, as demonstrated in Section 4\.

#### 3\.2\.2Efficient Identification of Composite Moves

We now present an efficient algorithm to generate all candidate moves \(single\-unit and composite\) in linear time\. We represent the contiguity relationships among units within a district as a graph, where each unit is a node and an edge connects two adjacent units \(Figure[2](https://arxiv.org/html/2605.06682#S3.F2)\)\. If removing a unit*u*from the district’s contiguity graph splits the graph into two or more disconnected components, then*u*is an*articulation point*\(also called a cut point\)\. A*biconnected component*is a maximal subgraph that cannot be disconnected by removing any single node\(Gabow,[2000](https://arxiv.org/html/2605.06682#bib.bib16)\)\. Figure[2](https://arxiv.org/html/2605.06682#S3.F2)shows the contiguity graph of district C in Figure[1](https://arxiv.org/html/2605.06682#S3.F1), which contains four cut points and five biconnected components\.

![Refer to caption](https://arxiv.org/html/2605.06682v1/figures/Figure2.jpg)Figure 2:The contiguity relationship among the spatial objects in the district C in Figure[1](https://arxiv.org/html/2605.06682#S3.F1)\. Neighbors are connected with edges, cut points are underlined, and dash\-line ellipses show five biconnected components \(bcc\)\.![Refer to caption](https://arxiv.org/html/2605.06682v1/figures/Figure3.jpg)Figure 3:Composite moves \(i\.e\., multi\-object moves\) for cut points\. Each cut point will move as a composite move to maintain contiguity\. For example, object 22 will move together with objects 15, 21, and 23 so that the remaining graph is still contiguous\.The algorithm proceeds in two stages \(Algorithm[3](https://arxiv.org/html/2605.06682#algorithm3)\)\.*First*, it finds all cut points and biconnected components in each district using a depth\-first search \(DFS\) method\(Gabow,[2000](https://arxiv.org/html/2605.06682#bib.bib16); Tarjan,[1972](https://arxiv.org/html/2605.06682#bib.bib46)\)\. The complexity of the DFS algorithm isO​\(n\)O\(n\), where*n*is the number of spatial units in each district\.

Inputs :

SdS\_\{d\}: the set of spatial objects in a district

dd;

CdC\_\{d\}: a contiguity matrix of the objects in

SdS\_\{d\};

AdA\_\{d\}: attribute vector for each object in

SdS\_\{d\};

Outputs :CompositeMoves: a list of composite moves for district

dd
Initialize CompositeMoves =

∅\\emptysetand LeafBCC =

∅\\emptyset;

Find all cut points and biconnected components using DFS \(

Sd,CdS\_\{d\},C\_\{d\}\)\(Gabow,[2000](https://arxiv.org/html/2605.06682#bib.bib16)\);

b​c​c\.C​P​Tbcc\.CPT: the set of cut points that a biconnected component

b​c​cbcccontains;

c​p​t\.B​C​Ccpt\.BCC: the set of biconnected components that a cut point

c​p​tcptbelongs to;

c​p​t\.m​a​x​C=∅cpt\.maxC=\\emptyset, which will keep the largest component for

c​p​tcpt;

c​p​t\.r​e​s​t​C=∅cpt\.restC=\\emptyset, which will keep the union of other components of

c​p​tcpt;

foreach*biconnected componentb​c​cbcc*do

if*\|bcc\.CPT\|=1\|bcc\.CPT\|=1*then

add

b​c​cbccto LeafBCC;

while*LeafBCC is not empty*do

b​c​c=next biconnected component in LeafBCCbcc=\\text\{next biconnected component in LeafBCC\};

if*b​c​c\.C​P​Tbcc\.CPTis not empty*then

Let

c​p​t=the only cut point in​b​c​c\.C​P​Tcpt=\\text\{the only cut point in \}bcc\.CPT;

if*size\(bcc\)\>size\(cpt\.maxC\)\\text\{size\}\(bcc\)\>\\text\{size\}\(cpt\.maxC\)*then

c​p​t\.r​e​s​t​C=c​p​t\.r​e​s​t​C∪c​p​t\.m​a​x​Ccpt\.restC=cpt\.restC\\cup cpt\.maxC;

c​p​t\.m​a​x​C=b​c​ccpt\.maxC=bcc;

else

c​p​t\.r​e​s​t​C=c​p​t\.r​e​s​t​C∪b​c​ccpt\.restC=cpt\.restC\\cup bcc;

Remove

b​c​cbccfrom

c​p​t\.B​C​Ccpt\.BCC;

if*\|cpt\.BCC\|=1\|cpt\.BCC\|=1andsize\(cpt\.maxC\)<size\(Sd\)−size\(cpt\.maxC∪cpt\.restC\)\+1\\text\{size\}\(cpt\.maxC\)<\\text\{size\}\(S\_\{d\}\)\-\\text\{size\}\(cpt\.maxC\\cup cpt\.restC\)\+1*then

c​p​t\.r​e​s​t​C=c​p​t\.m​a​x​C∪c​p​t\.r​e​s​t​Ccpt\.restC=cpt\.maxC\\cup cpt\.restC;

b​c​c​R=the only remaining biconnected component in​c​p​t\.B​C​CbccR=\\text\{the only remaining biconnected component in \}cpt\.BCC;

Let

c​p​t\.B​C​C=∅cpt\.BCC=\\emptysetand remove

c​p​tcptfrom

b​c​c​R\.C​P​TbccR\.CPT;

if*now\|bccR\.CPT\|=1\|bccR\.CPT\|=1*then

add

b​c​c​RbccRto LeafBCC;

if*c​p​t\.B​C​C=∅cpt\.BCC=\\emptyset*then

Aggregate the attribute vectors

AdA\_\{d\}over all units in

c​p​t\.r​e​s​t​Ccpt\.restC\(including

c​p​tcptitself\) to form the attributes of composite move

c​p​tcpt;

Add

c​p​tcpttoCompositeMovesas a new composite move;

Algorithm 3Identifying Composite Moves*Second*, for each cut point, the algorithm constructs one composite move, as illustrated in Figure[3](https://arxiv.org/html/2605.06682#S3.F3)\. By definition, biconnected components are connected only through cut points\. If we treat each biconnected component as a single “block”, the resulting block–cut graph forms a tree \(Figure[2](https://arxiv.org/html/2605.06682#S3.F2)\)\. A biconnected component is a leaf in this tree if it connects to only one cut point \(for example, bcc\_1 and bcc\_5 in Figure[2](https://arxiv.org/html/2605.06682#S3.F2)\)\. Since removing a cut point can split the district into multiple components, our strategy is to keep the largest resulting component as the main part of the district and combine the cut point with the remaining smaller components to form a composite move\. The size of a component can be measured by the number of units it contains or by other quantities such as total population; here we use the number of units\.

The algorithm starts from leaf biconnected components and traverses the tree bottom\-up to determine composite moves\. During this traversal, attribute values within each composite move are aggregated so that each composite move can be evaluated efficiently without scanning all units in it\.

The time complexity of Algorithm[3](https://arxiv.org/html/2605.06682#algorithm3)isO​\(n\)O\(n\), where*n*is the number of units in the district\. Algorithm[3](https://arxiv.org/html/2605.06682#algorithm3)is applied to each district\. Each non\-cut point produces a feasible single\-unit move, and each cut point produces a composite move\. Among these moves, those on the border between two districts are considered candidate moves between those neighboring districts\. The same unit \(for example, unit 14 in district A\) may have feasible moves to different neighboring districts \(for example, B or C\), which are treated as different candidate moves\. The list of candidate moves is updated after each accepted move \(Step 2 in Algorithm[1](https://arxiv.org/html/2605.06682#algorithm1)\)\.

#### 3\.2\.3Switch Moves: Exchanging Two Candidate Moves

Pair switches \(exchanging two candidate moves between two neighboring districts\) are often useful for improving certain criteria, such as population equality\(Nagel,[1965](https://arxiv.org/html/2605.06682#bib.bib37); Bozkayaet al\.,[2003](https://arxiv.org/html/2605.06682#bib.bib6)\)\. Compared with existing methods that consider pairwise switches, our switching operation is more general because each side of a switch may involve more than one unit\. For example, in Figure[1](https://arxiv.org/html/2605.06682#S3.F1), the composite move \{2, 1\} and the composite move \{9, 17\} can be switched between their districts while preserving contiguity\.

However, not all pairs of feasible moves can be switched while maintaining contiguity\. For example, in Figure[1](https://arxiv.org/html/2605.06682#S3.F1), unit 14 and unit 17 cannot be switched even though each can move individually\. We address this by applying the validity check\. LetM1M\_\{1\}andM2M\_\{2\}be two candidate moves,B1B\_\{1\}andB2B\_\{2\}be the boundary contacts thatM1M\_\{1\}andM2M\_\{2\}share with their respective destination districts\. LetBsB\_\{s\}be the shared boundary betweenM1M\_\{1\}andM2M\_\{2\}\. IfB1⊆BsB\_\{1\}\\subseteq B\_\{s\}orB2⊆BsB\_\{2\}\\subseteq B\_\{s\}, then we cannot switch the two moves\. Table[1](https://arxiv.org/html/2605.06682#S3.T1)shows the total number of valid pair switches \(i\.e\., switch moves\) between neighboring districts\.

### 3\.3Objective Function \(or Optimization Criteria\)

Different optimization problems can use very different objective functions \(that is, optimization criteria\)\. Because this paper uses political redistricting to present and evaluate our method, we focus on criteria commonly used in political redistricting\. In addition to the contiguity constraint,*population equality*is typically the most important criterion, as reflected in U\.S\. laws and state constitutions\. In practice, additional criteria are often considered to limit gerrymandering and improve plan quality, although the specific set varies by application\. Common examples include*compactness of district shapes*,*preservation of communities of interest*, and*respect for existing political boundaries*\. Some criteria, for example, “communities of interest”, are inherently subjective and require user input and interpretation\. In our previous work, we developed a visual analytics framework that supports interactive evaluation and iterative refinement, providing a way to incorporate subjective criteria into the optimization process\(Guo and Jin,[2011](https://arxiv.org/html/2605.06682#bib.bib21)\)\.

The focus of this paper is to introduce and evaluate the new optimization method\. Therefore, for clear comparison and visual checking of quality, we choose two commonly used, well defined, and probably also the most challenging criteria in redistricting: population equality and compactness of district shapes\.

Population equality \(PopDev\)

Population equality requires that district populations be as equal as possible to ensure the “one person one vote” principle\. We measure population equality using “population deviation” \(𝑃𝑜𝑝𝐷𝑒𝑣\\mathit\{PopDev\}\), defined as the sum, over all districts, of absolute differences between each district’s actual population \(pip\_\{i\}\) and its ideal population, which is the total population \(𝑃𝑜𝑝\\mathit\{Pop\}\) divided by the number of districtsrr\.

P​o​p​D​e​v=∑i=1r⌊\|pi−P​o​pr\|⌋PopDev=\\sum\_\{i=1\}^\{r\}\\left\\lfloor\\left\|p\_\{i\}\-\\frac\{Pop\}\{r\}\\right\|\\right\\rfloor\(1\)
Compactness \(Polsby–Popper\)

Many compactness measures have been proposed in the literature\(MacEachren,[1985](https://arxiv.org/html/2605.06682#bib.bib35)\)\. We use the Polsby\-Popper index \(𝑃𝑃𝐼\\mathit\{PPI\}\)\(Polsby and Popper,[1991](https://arxiv.org/html/2605.06682#bib.bib40)\), which is commonly used in redistricting\.𝑃𝑃𝐼\\mathit\{PPI\}measures the compactness of a district*P*as the ratio between the district area \(α\\alpha\) and the area of a circle that has the same perimeter \(ρ\\rho\) of*P*\.𝑃𝑃𝐼\\mathit\{PPI\}values range between 0 and 1, with 1 corresponding to a perfect circle\.

𝑃𝑃𝐼=4​π​αρ2\\mathit\{PPI\}=\\frac\{4\\pi\\alpha\}\{\\rho^\{2\}\}\(2\)
To combine compactness with population deviation in a single objective, we reverse and normalize𝑃𝑃𝐼\\mathit\{PPI\}to form a derived compactness penalty for each district, and then sum across districts to obtain the plan\-level compactness term\. We use the normalization described in Equation[3](https://arxiv.org/html/2605.06682#S3.E3)so that the compactness term is on a comparable scale to the population term\.

𝐶𝑜𝑚𝑝𝑎𝑐𝑡𝑛𝑒𝑠𝑠=∑i=1r𝑃𝑜𝑝1000​\(1−𝑃𝑃𝐼i\)\\mathit\{Compactness\}=\\sum\_\{i=1\}^\{r\}\{\\frac\{\\mathit\{Pop\}\}\{1000\}\\left\(1\-\{\\mathit\{PPI\}\}\_\{i\}\\right\)\}\(3\)
Overall Objective

The overall objective function*f*is a weighted sum of the selected criteria\. In this paper, the objective includes𝑃𝑜𝑝𝐷𝑒𝑣\\mathit\{PopDev\}and𝐶𝑜𝑚𝑝𝑎𝑐𝑡𝑛𝑒𝑠𝑠\\mathit\{Compactness\}, with user\-specified weights\. For other applications, the same framework can incorporate different criteria and weights as needed\.

#### 3\.3\.1Efficient Evaluation of Candidate Moves

Based on a given objective function*f*, each candidate move*m*is assigned a score,δm\\delta\_\{m\}, defined as the change in objective value caused by applying the move\. In other words,δm=f​\(P\)−f​\(Pm\)\\delta\_\{m\}=f\(P\)\-f\(P\_\{m\}\), where*P*is the current plan andPmP\_\{m\}is the new plan after making the move*m*\. The move with the largest score is the best move if the objective function is to be minimized\.

To achieve high efficiency, we calculate the score for each move using aggregated attribute values of the move and aggregated information from the two involved districts\. This strategy is known as “dynamic scoring”\(Altman and McDonald,[2011](https://arxiv.org/html/2605.06682#bib.bib2)\)\. For example, given two districts A and B and a set of candidate moves between them, we first compute aggregated attributes for each district \(such as total population and dissolved shape boundary\)\. We then compute the score of each candidate move using its aggregated attributes \(such as population and dissolved shape boundary\), which are obtained during candidate\-move generation in Section 3\.2\. As a result, we can score all candidate moves and identify the best move in linear time\.

#### 3\.3\.2Efficient Evaluation of Pair Switches

Evaluating pair switches can be time\-consuming if we enumerate and score all possible pairs\. Because pair switches are mainly used to improve population equality, we develop an efficient strategy to find the best switch without enumerating all pairs\.

Suppose there are two neighboring districts, A and B, each with a set of candidate moves\. To find the best pair to switch, we first order the moves in each district by the population they would transfer\. Then, for a given move*u*in A, using the population transfer of*u*and the current populations of A and B, we compute the target population transfer of an ideal move in B to switch with*u*\. Since the moves in B are already ordered, we can use a binary search to locate the move*m*in B whose population transfer is closest to the target value\. We then examine a small number of moves on both sides of*m*in the ordering and select the best partner move*v*for*u*according to the overall objective function\. Note that this best partner*v*is defined relative to*u*only\. Repeating this procedure for each move in A yields the best switch between A and B\.

The time complexity for evaluating pair switches isO​\(n​log⁡n\)O\(n\\log n\), where*n*is the total number of moves in A and B\. Finally, we compare the best single move identified in Section 3\.3\.1 with the best switch identified here to determine the overall best move\.

### 3\.4Optimization

So far, we have introduced an initialization method, an efficient algorithm for identifying candidate moves under the contiguity constraint, an objective function, and strategies for efficient move evaluation\. We now present the Tabu search algorithm that integrates these components to efficiently and effectively derive high\-quality redistricting plans\. Tabu search has been used in many applications and has been shown to outperform alternative approaches\(Glover and Laguna,[1997](https://arxiv.org/html/2605.06682#bib.bib18); Battiti and Bertossi,[1999](https://arxiv.org/html/2605.06682#bib.bib4); Bozkayaet al\.,[2003](https://arxiv.org/html/2605.06682#bib.bib6)\)\. Our Tabu search algorithm is shown in Figure[4](https://arxiv.org/html/2605.06682#S3.F4)\.

The optimization procedure improves an initial plan by iteratively moving units from one district to a neighboring district\. At each iteration, the algorithm evaluates all feasible single\-unit moves and composite moves \(including pair switches\) and selects the best move according to the objective function\. After the selected move is applied, the list of candidate moves is updated, and the next best move is identified\. This process repeats until a stopping condition is met\.

What makes Tabu search distinctive is its short\-term memory mechanism for avoiding recently explored paths and encouraging the search to escape local optima\. Specifically, the algorithm maintains a tabu list that records the most recent moves; moves on this list are temporarily prohibited until they expire from the list\. The tabu list length, denoted by*k*\(the number of prohibited recent moves\), is typically much smaller than the number of units*n*\. In our experiments, we setk=0\.08​nk=0\.08n\. Tabu search also allows non\-improving moves, that is, the best available move at an iteration may not reduce the objective value\. Allowing non\-improving moves helps the search move out of local optima and potentially reach better solutions later\. The search stops when the number of consecutive non\-improving moves exceeds a threshold𝑚𝑎𝑥𝑁𝐼𝑀\\mathit\{maxNIM\}\. In our experiments, we set𝑚𝑎𝑥𝑁𝐼𝑀=3​n\\mathit\{maxNIM\}=3n\.

![Refer to caption](https://arxiv.org/html/2605.06682v1/figures/Figure4.jpg)Figure 4:The Tabu search algorithm to optimize an initial redistricting plan\.By changing parameter settings, the algorithm in Figure[4](https://arxiv.org/html/2605.06682#S3.F4)can be converted to two other trajectory\-based optimization methods: local greedy search \(hill climbing\) and the Kernighan–Lin algorithm\. Ifk=0k=0\(no tabu\) and𝑚𝑎𝑥𝑁𝐼𝑀=0\\mathit\{maxNIM\}=0\(does not allow non\-improving moves\), the algorithm becomes local greedy search, which is fast but often produce poor optimization quality\. Ifk=∞k=\\inftyand𝑚𝑎𝑥𝑁𝐼𝑀=∞\\mathit\{maxNIM\}=\\infty\(i\.e\. each move can move once and the search stops when no valid move remains\), the algorithm becomes equivalent to the Kernighan–Lin \(K\-L\) procedure, originally developed for graph partitioning\(Kernighan and Lin,[1970](https://arxiv.org/html/2605.06682#bib.bib27)\)and widely used in network and graph optimization\(Newman,[2006](https://arxiv.org/html/2605.06682#bib.bib38)\)\.

Moreover, by enabling or disabling our contiguity\-preserving neighborhood expansion approach \(which introduces composite moves\), the algorithm in Figure[4](https://arxiv.org/html/2605.06682#S3.F4)can be configured into six different methods, summarized in Table[2](https://arxiv.org/html/2605.06682#S3.T2)\. Without composite moves, we have three traditional trajectory\-based optimization methods: Greedy, K–L, and Tabu\. With composite moves enabled, we obtain three enhanced variants:Greedy∗\\mathrm\{Greedy\}^\{\*\},K​–​L∗\\mathrm\{K\\text\{\-\-\}L\}^\{\*\}, andTabu∗\\mathrm\{Tabu\}^\{\*\}\(i\.e\., CM\-Tabu\), where the star \(∗\) indicates support for composite moves\. Our experiments in Section 4 show that each enhanced method substantially outperforms its traditional counterpart while by a large margin while remaining computationally efficient\.

Table 2:Different optimization methods that are implemented and compared\.CompositemovesTabu ListLength \(k\)Maximum consecutivenon\-improving movesallowedTime ComplexityGreedyNok=0k=0𝑚𝑎𝑥𝑁𝐼𝑀=0\\mathit\{maxNIM\}=0O​\(m​n​log⁡n\),m≪nO\(mn\\log n\),m\\ll nK–LNok=∞k=\\infty𝑚𝑎𝑥𝑁𝐼𝑀=∞\\mathit\{maxNIM\}=\\inftyO​\(n2​log⁡n\)O\(n^\{2\}\\log n\)TabuNok≪nk\\ll n𝑚𝑎𝑥𝑁𝐼𝑀=3​n\\mathit\{maxNIM\}=3nO​\(n2​log⁡n\)O\(n^\{2\}\\log n\)Greedy∗\\mathrm\{Greedy\}^\{\*\}Yesk=0k=0𝑚𝑎𝑥𝑁𝐼𝑀=0\\mathit\{maxNIM\}=0O​\(m​n​log⁡n\),m≪nO\(mn\\log n\),m\\ll nK​–​L∗\\mathrm\{K\\text\{\-\-\}L\}^\{\*\}Yesk=∞k=\\infty𝑚𝑎𝑥𝑁𝐼𝑀=∞\\mathit\{maxNIM\}=\\inftyO​\(n2​log⁡n\)O\(n^\{2\}\\log n\)Tabu∗\\mathrm\{Tabu\}^\{\*\}\(i\.e\.,Yesk≪nk\\ll n𝑚𝑎𝑥𝑁𝐼𝑀=3​n\\mathit\{maxNIM\}=3nO​\(n2​log⁡n\)O\(n^\{2\}\\log n\)CM\-Tabu\)We also implemented a genetic algorithm based on\(Xiao,[2008](https://arxiv.org/html/2605.06682#bib.bib50)\)for comparison\. The genetic algorithm starts with a set of initial plans generated using the method in Section 3\.1\. Readers are referred to\(Xiao,[2008](https://arxiv.org/html/2605.06682#bib.bib50)\)for additional details\. In our experiments, each generation contains 50 plans, and evolution continues for 200 generations\. The best plan found during evolution is returned as the final output\.

## 4Performance Evaluation

We evaluate the proposed methods using Iowa congressional redistricting based on the 2000 Census as a case study\. Iowa has 99 counties that must be divided into five congressional districts \(Figure[5](https://arxiv.org/html/2605.06682#S4.F5)\)\. The total population is 2,926,324, so the ideal population per district is 585,265\. In this research, two spatial units are considered contiguous if they share at least a segment of boundary\.

![Refer to caption](https://arxiv.org/html/2605.06682v1/figures/Figure5.jpg)Figure 5:The population of 99 Iowa counties from the 2000 census data\.### 4\.1Optimizing Population Equality Only

Our first experiment considers only the population\-equality criterion, measured by population deviation \(𝑃𝑜𝑝𝐷𝑒𝑣\\mathit\{PopDev\}\)\. We compare seven methods: the genetic algorithm, local greedy search \(Greedy\), Kernighan–Lin \(K–L\), Tabu search \(Tabu\), and their enhanced variants that enable composite moves \(i\.e\.,Greedy∗\\mathrm\{Greedy\}^\{\*\},K​–​L∗\\mathrm\{K\\text\{\-\-\}L\}^\{\*\}, andTabu∗\\mathrm\{Tabu\}^\{\*\}\)\. Each method is run 1,000 times to produce 1,000 plans that optimize𝑃𝑜𝑝𝐷𝑒𝑣\\mathit\{PopDev\}\. Each run begins from a different random initial plan and therefore may produce a different final plan\.

We compare the seven methods using the𝑃𝑜𝑝𝐷𝑒𝑣\\mathit\{PopDev\}scores of their 1,000 final plans\. Table[3](https://arxiv.org/html/2605.06682#S4.T3)summarizes the results, including the minimum \(best\), the 5th percentile, the 25th percentile \(first quartile,Q​1Q1\), the median, the 75th percentile \(third quartile,Q​3Q3\), the 95th percentile, and the max \(worst\)\. To assess reliability, Table[3](https://arxiv.org/html/2605.06682#S4.T3)also reports the interquartile range \(𝐼𝑄𝑅=Q​3−Q​1\\mathit\{IQR\}=Q3\-Q1\) and the standard deviation \(𝑆𝑡𝑑𝐷𝑒𝑣\\mathit\{StdDev\}\)\.

Table 3:Performance evaluation with Iowa Data\.1000 Runs,PopDev OnlyGeneticAlgorithmTrajectory\-basedoptimization methodsCombined withour approachGreedyK–LTabuGreedy∗K–L∗Tabu∗Min7,08971320577755159335%33,1332,9458072231,939459167Q​1Q1\(25%\)56,7057,3751,7034174,239915289Median \(50%\)74,15913,4612,6276297,5231,401371Q​3Q3\(75%\)93,31333,8834,5931,02512,7792,28948195%120,914343,86510,0793,57133,1934,735775Max198,0581,271,20784,30162,707617,46920,8375,997𝐼𝑄𝑅​\(Q​3−Q​1\)\\mathit\{IQR\}\(Q3\-Q1\)36,60826,5082,8906088,5401,374192𝑆𝑡𝑑𝐷𝑒𝑣\\mathit\{StdDev\}26,745147,4346,0503,33239,7961,794316Time \(s/run\)a1\.80\.0020\.020\.050\.0020\.020\.08
- aWe implemented both the traditional methods \(Greedy, K–L, Tabu\) and the enhanced methods \(Greedy∗\\mathrm\{Greedy\}^\{\*\},K​–​L∗\\mathrm\{K\\text\{\-\-\}L\}^\{\*\},Tabu∗\\mathrm\{Tabu\}^\{\*\}\) using the same efficient strategies described in this paper\. Therefore, the running times reported for the traditional methods are faster than some existing implementations in the literature or in packages such as BARD\(Altman and McDonald,[2011](https://arxiv.org/html/2605.06682#bib.bib2)\)\. The experiments were run on a MacBook Pro laptop with a 2\.66 GHz Intel processor\.

Results show that enabling our contiguity\-preserving neighborhood expansion \(composite moves\) yields substantial improvements:Greedy∗\\mathrm\{Greedy\}^\{\*\},K​–​L∗\\mathrm\{K\\text\{\-\-\}L\}^\{\*\}, andTabu∗\\mathrm\{Tabu\}^\{\*\}consistently outperform their corresponding traditional versions by a large margin \(p​\-value<2×10−16p\\text\{\-value\}<2\\times 10^\{\-16\}, Mann–Whitney–Wilcoxon test\)\. Among all methods,Tabu∗\\mathrm\{Tabu\}^\{\*\}achieves the best overall performance in both optimization quality \(lower𝑃𝑜𝑝𝐷𝑒𝑣\\mathit\{PopDev\}\) and reliability \(smaller𝐼𝑄𝑅\\mathit\{IQR\}and standard deviation\), as illustrated in Figure[6](https://arxiv.org/html/2605.06682#S4.F6)\. Although the Iowa case involves only 99 spatial units, it is a challenging population\-equality problem because county populations are large and severely limit how population can be redistributed while maintaining contiguity\. In the Philadelphia case study \(Section 4\.2\),Tabu∗\\mathrm\{Tabu\}^\{\*\}consistently produces plans that attain the theoretical global optimum for population equality \(𝑃𝑜𝑝𝐷𝑒𝑣=0\\mathit\{PopDev\}=0\), which is very difficult for existing methods to achieve\(Gopalanet al\.,[2013](https://arxiv.org/html/2605.06682#bib.bib19)\)\.

![Refer to caption](https://arxiv.org/html/2605.06682v1/figures/Figure6.jpg)Figure 6:Comparing the performance of Tabu andTabu∗\\mathrm\{Tabu\}^\{\*\}\(see Table[3](https://arxiv.org/html/2605.06682#S4.T3)\)\. The whiskers show the 5th and 95th percentiles\.
### 4\.2Optimizing Both Population Equality and Shape Compactness

Our second experiment considers both population deviation \(𝑃𝑜𝑝𝐷𝑒𝑣\\mathit\{PopDev\}\) and compactness\. We use Philadelphia City Council redistricting based on the 2010 Census to demonstrate joint optimization of population equality and compactness\. In this case, 1,687 ward divisions are partitioned into 10 districts\. The total population is 1,526,006\.

![Refer to caption](https://arxiv.org/html/2605.06682v1/figures/Figure8.jpg)Figure 7:Selected Philadelphia City Council redistricting plans generated byTabu∗\\mathrm\{Tabu\}^\{\*\}*using 1,687 ward divisions*\. \(a\) Optimizing population equality only under the contiguity constraint—global optimum attained \(𝑃𝑜𝑝𝐷𝑒𝑣=0\\mathit\{PopDev\}=0\)\. \(b\) Optimizing population equality and compactness with greater weight assigned to population equality—global optimum also attained\. \(c\) Optimizing population equality and compactness with equal weights\.Figure[7](https://arxiv.org/html/2605.06682#S4.F7)shows representative plans produced byTabu∗\\mathrm\{Tabu\}^\{\*\}under three configurations: \(a\) optimizing𝑃𝑜𝑝𝐷𝑒𝑣\\mathit\{PopDev\}only; \(b\) optimizing𝑃𝑜𝑝𝐷𝑒𝑣\\mathit\{PopDev\}and compactness with greater weight assigned to population equality; and \(c\) optimizing both criteria with equal weights\. The plans in \(a\) and \(b\) both achieve the theoretical global optimum \(𝑃𝑜𝑝𝐷𝑒𝑣=0\\mathit\{PopDev\}=0\)\. Plan \(c\) maintains a small𝑃𝑜𝑝𝐷𝑒𝑣\\mathit\{PopDev\}of 844 while achieving improved compactness\. As noted in\(Gopalanet al\.,[2013](https://arxiv.org/html/2605.06682#bib.bib19)\)for this same Philadelphia data, it is a remarkable achievement to find a global optimum solution on population equality, let alone to consistently finding many different solutions of the global optimum\.

![Refer to caption](https://arxiv.org/html/2605.06682v1/figures/Figure9.jpg)Figure 8:Two representative plans generated byTabu∗\\mathrm\{Tabu\}^\{\*\}using*66 wards*\(instead of ward divisions\) to preserve ward boundaries\.If preserving ward boundaries is preferred, Figure[8](https://arxiv.org/html/2605.06682#S4.F8)shows two plans generated byTabu∗\\mathrm\{Tabu\}^\{\*\}using the 66 wards as the basic units, thereby fully preserving ward boundaries\. As expected, this coarser aggregation reduces the flexibility for achieving perfect population equality; however, the total population deviation of both plans remains within 1\.5 percent of the total population, which is generally acceptable in practice\. The method can generate hundreds of plans within a minute; for clarity, we present only representative examples here\.

In practice, the same framework can also incorporate additional criteria and interactive controls—such as drawing communities of interest, locking specific districts, or manually editing selected boundaries to incorporate local knowledge and considerations\. However, this paper focuses on the core optimization algorithm and therefore does not present or evaluate these interactive features for human\-computer collaboration\.

Overall, these results indicate that, with its optimization power, the approach can optimize multi\-criteria objectives to a fine level, allowing practitioners to focus more on interactive refinement to incorporate hard\-to\-quantify local knowledge and domain expertise, thereby enabling public participation and practical decision\-support workflows\.

## 5Conclusion and Discussion

This paper presents an efficient and effective approach for strengthening the optimization power of combinatorial methods for practical spatial problems with hard contiguity constraints\. Using redistricting as an illustrative application, we show that contiguity constraints can severely restrict the feasible neighborhood of trajectory\-based search methods, limiting exploration and trapping searches in poor local optima\. We address this bottleneck by introducing a contiguity\-preserving neighborhood expansion based on composite moves and valid switches, which can be integrated into standard trajectory\-based optimizers\.

When combined with local greedy search, the Kernighan–Lin procedure, and Tabu search, the proposed approach substantially improves both solution quality and run\-to\-run reliability, with the Tabu\-based integration, i\.e\.,*Composite\-Move Tabu search*\(CM\-Tabu\), achieving the strongest overall performance\. Experiments on Iowa congressional redistricting demonstrate large and consistent gains in population\-equality optimization, while the Philadelphia City Council case study illustrates effective multi\-criteria optimization that balances population equality and compactness and supports interactive exploration of trade\-offs\. Across these studies, the approach can generate many diverse high\-quality plans efficiently, making it well suited for real\-world decision\-support workflows\.

Although this paper focuses on redistricting and trajectory\-based optimization, the underlying framework is broadly applicable to other spatial combinatorial problems that require contiguity constraint and multi\-criteria optimization, including school redistricting, location\-allocation, traffic zone design, and service\-territory planning\. Adapting the framework to new applications may require problem\-specific objective functions or constraints, but the core idea remains the same: explicitly leveraging contiguity structure to expand the feasible neighborhood search without violating hard constraints\.

Several directions for future work follow naturally\. First, the framework can be integrated with additional heuristic families, including population\-based methods such as genetic algorithms, to further improve exploration and diversify solution sets\. Second, richer practical constraints and preferences, including user\-defined criteria and policy constraints, can be incorporated within the same move\-evaluation framework to support interactive refinement\. Overall, our results suggest that prioritizing optimization power within a flexible, constraint\-respecting framework can help bridge the gap between theoretical algorithms and practical spatial decision\-support systems\.

## Software Download

The software package implementing the proposed approach, iRedistrict, will be made publicly available at[www\.urbanxai\.com](https://arxiv.org/html/2605.06682v1/www.urbanxai.com)\.

## References

- C\. Ahmed, A\. Forel, A\. Parmentier, and T\. Vidal \(2024\)DistrictNet: Decision\-aware learning for geographical districting\.Advances in Neural Information Processing Systems37,pp\. 128574–128602\.External Links:[Document](https://dx.doi.org/10.52202/079017-4084)Cited by:[§2\.4](https://arxiv.org/html/2605.06682#S2.SS4.p1.1)\.
- M\. Altman and M\. P\. McDonald \(2011\)BARD: Better Automated Redistricting\.Journal of Statistical Software42,pp\. 1–28\.External Links:ISSN 1548\-7660,[Document](https://dx.doi.org/10.18637/jss.v042.i04)Cited by:[§3\.3\.1](https://arxiv.org/html/2605.06682#S3.SS3.SSS1.p2.1),[item a](https://arxiv.org/html/2605.06682#S4.I1.ix1.p1.3)\.
- M\. Altman and M\. McDonald \(2010\)The Promise and Perils of Computers in Redistricting\.Duke Journal of Constitutional Law & Public Policy5\(1\),pp\. 69–111\.External Links:ISSN urn:ISSN:1937\-9439Cited by:[§2\.2](https://arxiv.org/html/2605.06682#S2.SS2.p1.1)\.
- R\. Battiti and A\.A\. Bertossi \(1999\)Greedy, prohibition, and reactive heuristics for graph partitioning\.IEEE Transactions on Computers48\(4\),pp\. 361–385\.External Links:ISSN 1557\-9956,[Document](https://dx.doi.org/10.1109/12.762522)Cited by:[§3\.4](https://arxiv.org/html/2605.06682#S3.SS4.p1.1)\.
- P\. K\. Bergey, C\. T\. Ragsdale, and M\. Hoskote \(2003\)A simulated annealing genetic algorithm for the electrical power districting problem\.Annals of Operations Research121\(1\),pp\. 33–55\.Cited by:[§2\.3](https://arxiv.org/html/2605.06682#S2.SS3.p1.1)\.
- B\. Bozkaya, E\. Erkut, and G\. Laporte \(2003\)A tabu search heuristic and adaptive memory procedure for political districting\.European Journal of Operational Research144\(1\),pp\. 12–26\.External Links:ISSN 0377\-2217Cited by:[§2\.3](https://arxiv.org/html/2605.06682#S2.SS3.p1.1),[§3\.2\.3](https://arxiv.org/html/2605.06682#S3.SS2.SSS3.p1.1),[§3\.4](https://arxiv.org/html/2605.06682#S3.SS4.p1.1)\.
- M\. H\. Browdy \(1990\)Simulated annealing: An improved computer model for political redistricting\.Yale Law & Policy Review8,pp\. 163\.Cited by:[§2\.3](https://arxiv.org/html/2605.06682#S2.SS3.p1.1)\.
- F\. Chen, S\. Biswas, Z\. Chen, S\. Lei, N\. Ramakrishnan, and C\. Lu \(2023\)Exploring Tradeoffs in Automated School Redistricting: Computational and Ethical Perspectives\.Proceedings of the AAAI Conference on Artificial Intelligence37\(13\),pp\. 15912–15920\.External Links:ISSN 2374\-3468,[Document](https://dx.doi.org/10.1609/aaai.v37i13.26889)Cited by:[§2\.4](https://arxiv.org/html/2605.06682#S2.SS4.p1.1)\.
- W\. K\. T\. Cho and B\. E\. Cain \(2020\)Human\-centered redistricting automation in the age of AI\.Science369\(6508\),pp\. 1179–1181\.External Links:[Document](https://dx.doi.org/10.1126/science.abd1879)Cited by:[§2\.4](https://arxiv.org/html/2605.06682#S2.SS4.p1.1)\.
- V\. Cohen\-Addad, P\. N\. Klein, and N\. E\. Young \(2018\)Balanced centroidal power diagrams for redistricting\.InProceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems,SIGSPATIAL ’18,New York, NY, USA,pp\. 389–396\.External Links:[Document](https://dx.doi.org/10.1145/3274895.3274979),ISBN 978\-1\-4503\-5889\-7Cited by:[§2\.2](https://arxiv.org/html/2605.06682#S2.SS2.p1.1)\.
- T\. J\. Cova and R\. L\. Church \(2000\)Exploratory spatial optimization in site search: a neighborhood operator approach\.Computers, Environment and Urban Systems24\(5\),pp\. 401–419\.External Links:ISSN 0198\-9715,[Document](https://dx.doi.org/10.1016/S0198-9715%2800%2900015-6)Cited by:[§2\.2](https://arxiv.org/html/2605.06682#S2.SS2.p1.1)\.
- D\. DeFord, M\. Duchin, and J\. Solomon \(2020\)Recombination: A Family of Markov Chains for Redistricting\.Harvard Data Science Review3\(1\)\.External Links:ISSN 2644\-2353, 2688\-8513,[Document](https://dx.doi.org/10.1162/99608f92.eb30390f)Cited by:[§2\.4](https://arxiv.org/html/2605.06682#S2.SS4.p1.1)\.
- K\. W\. Dobbs, D\. M\. King, and S\. H\. Jacobson \(2023\)Redistricting optimization with recombination: A local search case study\.Computers & Operations Research160,pp\. 106369\.External Links:ISSN 0305\-0548,[Document](https://dx.doi.org/10.1016/j.cor.2023.106369)Cited by:[§2\.4](https://arxiv.org/html/2605.06682#S2.SS4.p1.1)\.
- D\. Dugošija, A\. Savić, and Z\. Maksimović \(2020\)A new integer linear programming formulation for the problem of political districting\.Annals of Operations Research288\(1\),pp\. 247–263\.External Links:ISSN 1572\-9338,[Document](https://dx.doi.org/10.1007/s10479-020-03559-y)Cited by:[§2\.2](https://arxiv.org/html/2605.06682#S2.SS2.p1.1)\.
- B\. Fifield, M\. Higgins, K\. Imai, and A\. Tarr \(2020\)Automated Redistricting Simulation Using Markov Chain Monte Carlo\.Journal of Computational and Graphical Statistics29\(4\),pp\. 715–728\.External Links:ISSN 1061\-8600,[Document](https://dx.doi.org/10.1080/10618600.2020.1739532)Cited by:[§2\.4](https://arxiv.org/html/2605.06682#S2.SS4.p1.1)\.
- H\. N\. Gabow \(2000\)Path\-based depth\-first search for strong and biconnected components\.Information Processing Letters74\(3\),pp\. 107–114\.External Links:ISSN 0020\-0190Cited by:[§3\.2\.2](https://arxiv.org/html/2605.06682#S3.SS2.SSS2.p1.1),[§3\.2\.2](https://arxiv.org/html/2605.06682#S3.SS2.SSS2.p2.1),[3](https://arxiv.org/html/2605.06682#algorithm3.10.10)\.
- B\. C\. Gearhart and J\. M\. Liittschwager \(1969\)Legislative districting by computer\.Behavioral Science14\(5\),pp\. 404–417\.External Links:ISSN 1099\-1743,[Document](https://dx.doi.org/10.1002/bs.3830140510)Cited by:[§2\.1](https://arxiv.org/html/2605.06682#S2.SS1.p1.1)\.
- F\. Glover and M\. Laguna \(1997\)Tabu Search\.Kluwer Academic Publishers\.Cited by:[§3\.4](https://arxiv.org/html/2605.06682#S3.SS4.p1.1)\.
- R\. Gopalan, S\. O\. Kimbrough, F\. H\. Murphy, and N\. Quintus \(2013\)The Philadelphia Districting Contest: Designing Territories for City Council Based Upon the 2010 Census\.Interfaces43\(5\),pp\. 477–489\.External Links:ISSN 0092\-2102,[Document](https://dx.doi.org/10.1287/inte.2013.0697)Cited by:[§4\.1](https://arxiv.org/html/2605.06682#S4.SS1.p3.9),[§4\.2](https://arxiv.org/html/2605.06682#S4.SS2.p2.5)\.
- D\. Guo \(2008\)Regionalization with dynamically constrained agglomerative clustering and partitioning \(REDCAP\)\.International Journal of Geographical Information Science22\(7\),pp\. 801–823\.External Links:ISSN 1365\-8816,[Document](https://dx.doi.org/10.1080/13658810701674970)Cited by:[§2\.1](https://arxiv.org/html/2605.06682#S2.SS1.p1.1)\.
- D\. Guo, H\. Jin, P\. Gao, and X\. Zhu \(2018\)Detecting spatial community structure in movements\.International Journal of Geographical Information Science32\(7\),pp\. 1326–1347\.External Links:ISSN 1365\-8816,[Document](https://dx.doi.org/10.1080/13658816.2018.1434889)Cited by:[§2\.1](https://arxiv.org/html/2605.06682#S2.SS1.p1.1)\.
- D\. Guo and H\. Jin \(2011\)iRedistrict: Geovisual Analytics for Redistricting Optimization\.Journal of Visual Languages & Computing22\(4\),pp\. 279–289\.External Links:ISSN 1045\-926X,[Document](https://dx.doi.org/10.1016/j.jvlc.2011.03.001)Cited by:[§3\.3](https://arxiv.org/html/2605.06682#S3.SS3.p1.1)\.
- W\. Gurnee and D\. B\. Shmoys \(2021\)Fairmandering: A column generation heuristic for fairness\-optimized political districting\.InProceedings of the 2021 SIAM Conference on Applied and Computational Discrete Algorithms \(ACDA21\),Proceedings,pp\. 88–99\.External Links:[Document](https://dx.doi.org/10.1137/1.9781611976830.9)Cited by:[§2\.2](https://arxiv.org/html/2605.06682#S2.SS2.p1.1)\.
- M\. Á\. Gutiérrez\-Andrade, E\. A\. Rincón\-García, S\. G\. de\-los\-Cobos\-Silva, P\. Lara\-Velázquez, R\. A\. Mora\-Gutiérrez, and A\. Ponsich \(2019\)Simulated Annealing and Artificial Bee Colony for the Redistricting Process in Mexico\.INFORMS Journal on Applied Analytics49\(3\),pp\. 189–200\.External Links:ISSN 2644\-0865,[Document](https://dx.doi.org/10.1287/inte.2019.0992)Cited by:[§2\.3](https://arxiv.org/html/2605.06682#S2.SS3.p1.1)\.
- S\. W\. Hess, J\. B\. Weaver, H\. J\. Siegfeldt, J\. N\. Whelan, and P\. A\. Zitlau \(1965\)Nonpartisan political redistricting by computer\.Operations Research13\(6\),pp\. 998–1006\.Cited by:[§2\.1](https://arxiv.org/html/2605.06682#S2.SS1.p1.1)\.
- J\. Kalcsics, S\. Nickel, and M\. Schröder \(2005\)Towards a unified territorial design approach\-Applications, algorithms and GIS integration\.Top13\(1\),pp\. 1–56\.Cited by:[§2\.1](https://arxiv.org/html/2605.06682#S2.SS1.p1.1)\.
- B\. W\. Kernighan and S\. Lin \(1970\)An efficient heuristic procedure for partitioning graphs\.Bell System Technical Journal49\(2\),pp\. 291–307\.Cited by:[§3\.4](https://arxiv.org/html/2605.06682#S3.SS4.p4.4)\.
- M\. J\. Kim \(2018\)Multiobjective spanning tree based optimization model to political redistricting\.Spatial Information Research26\(3\),pp\. 317–325\.External Links:ISSN 2366\-3294,[Document](https://dx.doi.org/10.1007/s41324-018-0171-5)Cited by:[§2\.2](https://arxiv.org/html/2605.06682#S2.SS2.p1.1)\.
- S\. Ko, E\. Taylor, P\. Agarwal, and K\. Munagala \(2022\)All Politics is Local: Redistricting via Local Fairness\.Advances in Neural Information Processing Systems35,pp\. 17443–17455\.Cited by:[§2\.4](https://arxiv.org/html/2605.06682#S2.SS4.p1.1)\.
- Y\. Kong, Y\. Zhu, and Y\. Wang \(2019\)A center\-based modeling approach to solve the districting problem\.International Journal of Geographical Information Science33\(2\),pp\. 368–384\.External Links:ISSN 1365\-8816,[Document](https://dx.doi.org/10.1080/13658816.2018.1474472)Cited by:[§2\.2](https://arxiv.org/html/2605.06682#S2.SS2.p1.1)\.
- Y\. Kong \(2021\)A Hybrid Algorithm for the Equal Districting Problem\.InSpatial Data and Intelligence,G\. Pan, H\. Lin, X\. Meng, Y\. Gao, Y\. Li, Q\. Guan, and Z\. Ding \(Eds\.\),Cham,pp\. 110–120\.External Links:[Document](https://dx.doi.org/10.1007/978-3-030-85462-1%5F9),ISBN 978\-3\-030\-85462\-1Cited by:[§2\.2](https://arxiv.org/html/2605.06682#S2.SS2.p1.1)\.
- R\. Kueng, D\. G\. Mixon, and S\. Villar \(2019\)Fair redistricting is hard\.Theoretical Computer Science791,pp\. 28–35\.External Links:ISSN 0304\-3975,[Document](https://dx.doi.org/10.1016/j.tcs.2019.04.004)Cited by:[§2\.4](https://arxiv.org/html/2605.06682#S2.SS4.p1.1)\.
- H\. A\. Levin and S\. A\. Friedler \(2019\)Automated Congressional Redistricting\.ACM J\. Exp\. Algorithmics24,pp\. 1\.10:1–1\.10:24\.External Links:ISSN 1084\-6654,[Document](https://dx.doi.org/10.1145/3316513)Cited by:[§2\.4](https://arxiv.org/html/2605.06682#S2.SS4.p1.1)\.
- A\. Ligmann\-Zielinska, R\. L\. Church, and P\. Jankowski \(2008\)Spatial optimization as a generative technique for sustainable multiobjective land\-use allocation\.International Journal of Geographical Information Science22\(6\),pp\. 601–622\.External Links:ISSN 1365\-8816,[Document](https://dx.doi.org/10.1080/13658810701587495)Cited by:[§2\.2](https://arxiv.org/html/2605.06682#S2.SS2.p1.1)\.
- A\. M\. MacEachren \(1985\)Compactness of Geographic Shape: Comparison and Evaluation of Measures\.Geografiska Annaler: Series B, Human Geography67\(1\),pp\. 53–67\.External Links:ISSN 0435\-3684,[Document](https://dx.doi.org/10.1080/04353684.1985.11879515)Cited by:[§3\.3](https://arxiv.org/html/2605.06682#S3.SS3.p7.5)\.
- C\. McCartan and K\. Imai \(2023\)Sequential Monte Carlo for sampling balanced and compact redistricting plans\.The Annals of Applied Statistics17\(4\),pp\. 3300–3323\.External Links:ISSN 1932\-6157, 1941\-7330,[Document](https://dx.doi.org/10.1214/23-AOAS1763)Cited by:[§2\.4](https://arxiv.org/html/2605.06682#S2.SS4.p1.1)\.
- S\. S\. Nagel \(1965\)Simplified bipartisan computer redistricting\.Stanford Law Review17\(5\),pp\. 863–899\.Cited by:[§2\.3](https://arxiv.org/html/2605.06682#S2.SS3.p1.1),[§3\.2\.3](https://arxiv.org/html/2605.06682#S3.SS2.SSS3.p1.1)\.
- M\. E\. J\. Newman \(2006\)Modularity and community structure in networks\.Proceedings of the National Academy of Sciences103\(23\),pp\. 8577–8582\.External Links:ISSN 0027\-8424Cited by:[§3\.4](https://arxiv.org/html/2605.06682#S3.SS4.p4.4)\.
- S\. Openshaw \(1977\)Optimal zoning systems for spatial interaction models\.Environment and Planning A9\(2\),pp\. 169–184\.Cited by:[§2\.1](https://arxiv.org/html/2605.06682#S2.SS1.p1.1)\.
- D\. D\. Polsby and R\. D\. Popper \(1991\)Partisan gerrymandering: harms and a new solution\.Heartland Policy Study34\.Cited by:[§3\.3](https://arxiv.org/html/2605.06682#S3.SS3.p7.5)\.
- F\. Ricca, A\. Scozzari, and B\. Simeone \(2008\)Weighted Voronoi region algorithms for political districting\.Mathematical and Computer Modelling48\(9\-10\),pp\. 1468–1477\.External Links:ISSN 0895\-7177,[Document](https://dx.doi.org/10.1016/j.mcm.2008.05.041)Cited by:[§2\.3](https://arxiv.org/html/2605.06682#S2.SS3.p1.1)\.
- R\. Z\. Ríos\-Mercado, A\. M\. Álvarez\-Socarrás, A\. Castrillón, and M\. C\. López\-Locés \(2021\)A location\-allocation\-improvement heuristic for districting with multiple\-activity balancing constraints and*p*\-median\-based dispersion minimization\.Computers & Operations Research126,pp\. 105106\.External Links:ISSN 0305\-0548,[Document](https://dx.doi.org/10.1016/j.cor.2020.105106)Cited by:[§2\.1](https://arxiv.org/html/2605.06682#S2.SS1.p1.1)\.
- M\. Shahmizad and A\. Buchanan \(2025\)Political Districting to Minimize County Splits\.Operations Research73\(2\),pp\. 752–774\.External Links:ISSN 0030\-364X,[Document](https://dx.doi.org/10.1287/opre.2023.0094)Cited by:[§2\.2](https://arxiv.org/html/2605.06682#S2.SS2.p1.1)\.
- R\. Swamy, D\. M\. King, and S\. H\. Jacobson \(2023\)Multiobjective Optimization for Politically Fair Districting: A Scalable Multilevel Approach\.Operations Research71\(2\),pp\. 536–562\.External Links:ISSN 0030\-364X,[Document](https://dx.doi.org/10.1287/opre.2022.2311)Cited by:[§2\.2](https://arxiv.org/html/2605.06682#S2.SS2.p1.1)\.
- R\. Swamy, D\. M\. King, I\. G\. Ludden, K\. W\. Dobbs, and S\. H\. Jacobson \(2024\)A practical optimization framework for political redistricting: A case study in Arizona\.Socio\-Economic Planning Sciences92,pp\. 101836\.External Links:ISSN 0038\-0121,[Document](https://dx.doi.org/10.1016/j.seps.2024.101836)Cited by:[§2\.2](https://arxiv.org/html/2605.06682#S2.SS2.p1.1)\.
- R\. Tarjan \(1972\)Depth\-first search and linear graph algorithms\.SIAM journal on computing1\(2\),pp\. 146–160\.External Links:ISSN 0097\-5397Cited by:[§3\.2\.2](https://arxiv.org/html/2605.06682#S3.SS2.SSS2.p2.1)\.
- M\. K\. Tomczyk and M\. Kadziński \(2024\)Evolutionary algorithms for solving single\- and multiple\-objective political redistricting problems: The case study of Poland\.Applied Soft Computing152,pp\. 111258\.External Links:ISSN 1568\-4946,[Document](https://dx.doi.org/10.1016/j.asoc.2024.111258)Cited by:[§2\.3](https://arxiv.org/html/2605.06682#S2.SS3.p1.1)\.
- H\. Validi, A\. Buchanan, and E\. Lykhovyd \(2022\)Imposing Contiguity Constraints in Political Districting Models\.Operations Research70\(2\),pp\. 867–892\.External Links:ISSN 0030\-364X,[Document](https://dx.doi.org/10.1287/opre.2021.2141)Cited by:[§2\.2](https://arxiv.org/html/2605.06682#S2.SS2.p1.1)\.
- W\. Vickrey \(1961\)On the prevention of gerrymandering\.Political Science Quarterly76\(1\),pp\. 105–110\.Cited by:[§2\.1](https://arxiv.org/html/2605.06682#S2.SS1.p1.1)\.
- N\. Xiao \(2008\)A Unified Conceptual Framework for Geographical Optimization Using Evolutionary Algorithms\.Annals of the Association of American Geographers98\(4\),pp\. 795–817\.Cited by:[§2\.3](https://arxiv.org/html/2605.06682#S2.SS3.p1.1),[§2\.3](https://arxiv.org/html/2605.06682#S2.SS3.p2.1),[§3\.4](https://arxiv.org/html/2605.06682#S3.SS4.p6.1)\.