효율적인 최적화 문제 해법을 GIS와 연계하면 입지 선정 문제에서 공간적 재현의 중요성에 관한 통찰력을 제공할 수 있다. 특히 발견적 해법 중 라그란지안 완화법에 기반한 해법은 메타휴리스틱에 비해 이론적으로 정교하며 결과해의 품질이 보장된다. 본 연구는 최소의 시설물로 전체 수요를 커버할 수 있도록 시설물 입지를 최적화하는 LSCP 문제에 초점을 두었다. 구체적으로 LSCP 문제 구조 및 특성 분석을 통해 문제의 효율적 해결을 위한 라그란지안 기법을 개발하고 이를 GIS 환경에 구현, 실세계 자료에 대해 입지선정 분석을 수행하였다. 실험을 통해 개발된 알고리즘은 고품질의 결과를 효율적으로 제공한다는 점을 확인하였다.

Incorporation of efficient solution methods into a GIS environment has the potential of providing insights into the importance of spatial representation in location modeling. Heuristic algorithms based on lagrangian relaxation have solid theoretic grounds and the quality of the solutions is guaranteed to be within bounds. This paper focuses on solving the LSCP that optimizes the locations of a minimum number of facilities that can cover all the demands. The structure and characteristics of LSCP were analyzed to develop a lagrangian heuristic, which was implemented into a GIS environment. Tests on the real world data suggest that the developed system provides high-quality solutions efficiently.

요약
 Abstract
 I. 서론
  1. 연구배경 및 목적
  2. 연구방법
 II. 수리모델
 III. 발견적 해법
  1. 완화된 수리 모델
  2. 라그란지안 발견적 해법 알고리즘 개요
  3. 상한과 하한의 연계
  4. 문제 규모 축소
  5. 축소된 LSCP의 실행가능 해 탐색
  6. 라그란지안 승수 갱신
  7. 종료조건 검사
 IV. 사례연구
  1. LSCP-GIS 시스템
  2. 실험 설계
  3. 결과 분석
 V. 결론
 참고문헌

• 김종근(서울대학교 지리교육과 강사) | Jong-Geun Kim