Automated Congressional Redistricting

Every 10 years, when states are forced to redraw their congressional districts, the process is intensely partisan, and the outcome is rarely fair and democratic. In the past few decades, the growing capabilities of computers have offered the promise of objective, computerized redistricting. Unfortunately, the redistricting problem can be shown to be NP-Complete, but there are a number of heuristics that are effective. We specifically define the redistricting problem and analyze several variations of a new divide and conquer algorithm, comparing the compactness and population deviation of our new algorithm to existing algorithms and the actual districts. We offer a comparative component-based analysis that demonstrates the strengths and weaknesses of each algorithm component and the type of input. The comparative analysis shows that there are several ways to produce valid redistricting plans, but each approach has benefits and consequences.
Our new algorithm produces valid results to the redistricting problem in almost every state that undergoes congressional redistricting, offering a new solution to this challenging real-world problem. In one version, the algorithm produces plans with the optimal population deviation in 42 out of 43 multi-district states, which is better than most algorithms in the literature. While compactness scores vary, this approach offers new opportunities to improve population deviation. Our output files comply with the accepted format at most government hearings and redistricting competitions, so the results would be compatible with most public participation efforts in 2020.