Political redistricting problems are to divide a region into several districts with respect to several redistricting criteria so that political representatives are elected. These problems are difficult because the number of feasible redistricting plans is exponentially increased with the problem size. Also, several redistricting criteria must be satisfied at the same time, and it is difficult to formulate essential contiguity requirement in a mixed integer programming. A strict equal populated redistricting plan is intractable to solve.
The main purpose of this dissertation is to develop optimization approaches to political redistricting focusing on a strict equal population and contiguity and is to compare them with the existing researches. This dissertation develops two types of exact optimization models to political redistricting based on recent advances in solving land acquisition problems. The new exact models successfully formulate contiguity requirement and satisfy a strict equal population. They are compared with the existing exact model. Computational experiments show that the exact models face computational challenges for large data even though contiguity and a strict equal population are successfully formulated in a mixed integer program. Then, this dissertation moves to implement two different heuristic optimization models, which efficiently finds high-quality solutions. They are evaluated using existing data sets for comparisons. Throughout computational experiments, it is clearly known that all of the heuristics efficiently find near-optimal solutions, and among them the Give-And-Take greedy algorithm shows such efficiency even for the large size problems. Also, all of the heuristics show higher population equality than the existing plan of Iowa in 2000 and Give-And-Take greedy algorithm finds a plan with the highest population equality.