선거구 구획문제는 선거구를 인구등분, 인접성, 공간적 조밀도 등의 일정한 기준에 따라서 나누는 작업을 말한다. 미국의 경우 의회 선거구는 필수불가결한 요소로 완벽한 인구 등분과 인접성을 헌법으로 요구하고 있다. 그러나 기존의 휴리스틱은 여러 가지 선거구 선정요인들을 동시에 만족시키는데 주력하고 있어 의회선거구에 맞는 완벽한 인구등분을 가진 선거구 플랜을 찾는데 한계를 보이고 있다. 그리하여, 이 논문에서는 의회선거구 구성 요건에 맞는 선거구 구획 연구를 하고자 최적화 연구방법 중 시뮬레이티드 어닐링(모의 담금질 기법) 휴리스틱 기법을 기본 바탕으로 선거구를 구획하였다. 또한 새로운 인접성 방법을 제시하여, 구획연구를 하는데 있어 하나의 접근법으로 제시하고자 한다. 연구 결과 이 논문에서 이용된 기법은 실제 이용 중인 선거구 플랜보다 훨씬 더 인구등분에 가까운 선거구 플랜을 찾아내며, 효과적으로 인접성 문제를 해결하고 있음을 알 수 있었다. 또한, 새로 개발한 휴리스틱은 다양한 선거구 플랜을 제시하고 있어, 의사결정자들로 하여금 선택의 용이성을 제공하고 있음을 알 수 있었다. 이러한 시도는 의회 선거구를 구성하는데 있어서 새로운 대안으로 제시될 수 있을 것이다. 또한, 이러한 선거구 선정 연구는 한국의 국회의원 선거구 선정문제에서 인접성과 인구등분의 선정기준을 이용할 시 적용 할 수 있다는데 그 의의가 있다.

Political redistricting problems are the way of aggregating a set of population units into contiguous geographical area with redistricting criteria. Political redistricting problems are very difficult because they can be lead to political debate because the drafter may take part in redistricting process with subjective opinions. Also, these problems are complicated because the number of feasible redistricting plans is exponentially increased with the problem size. Especially, US constitution requires that the congressional district should be redrawn to make populations strictly equal and make population units successfully contiguous. However, existing approaches such as transportation problems, local search based methods and metaheuristic approaches may show the difficulty to find strict population equality redistricting plans and the inefficiency to ensure contiguity. The purpose of this paper is to develop a heuristic approach to congressional redistricting using contiguity checking. Computational experiments show that the new heuristic shows various spatial configurations in a most strict equal population plan and finds a better plan than the official plan in terms of strict population equality. This new plan may be proposed as a new plan for the congressional plan. Also, it is significant that the research studied in the paper can be applied to the redrawing of member of the National Assembly in Korea in the near future.

Abstract
 I. Introduction
 II. Optimization Approaches to Political Redistricting Problems
 III. Contiguity Checking Method to Redistricting Problems
 IV. A simulated Annealing to Congressional Redistricting
  1. General process
  2. Cooling schedules in the algorithm
 V. Computational Experiments
 VI. Conclusions and Discussions
 Notes
 References

• Myung Jin Kim(Senior Researcher, Korea Gyeonggi Institute of Science & Technology Promotion) | 김명진