내부 기저형성법을 이용한 Fixed Charge Network Flow Problem의 해법에 관한 연구 = Vertex Search Algorithms for the Fixed Charge Network Flow Problem

국문 초록 (Abstract)

본 논문은 Fixed Charge Network Flow Problem(FCNFP)에 대한 해법을 제시하고, 제안된 해법에 대한 수행도의 비교·평가를 목적으로 한다. FCNFP는 다수의 수요지에서 요구되는 물량을 다수의 공급지로부터 가장 효율적으로 공급하는 해를 찾는 네트워크 디자인 문제이다. 이 문제는 통신망 디자인 문제, 스타이너 트리 문제, 롯트 사이즈 결정 문제 등과 같이 다양한 분야로 응용될 수 있다.
그러나, 이 문제는 NP-hard 문제로써 다항시간 내에 최적해를 찾을 수 있는 해법이 아직 개발되어 있지 않다. 뿐만 아니라, 이 문제를 위한 휴리스틱 해법 역시 이 문제의 다양한 적용성을 고려할 때 충분히 연구되지 않은 실정이며, 따라서 FCNFP의 효율적인 해법 개발이 필요하다.
본 논문에서는 FCNFP의 해법으로 Block Pivot을 이용한 다중 기저형성법을 제안한다. Block Pivot을 이용한 다중 기저형성법은 선형계획법에서 사용되는 단체법의 Block Pivot 개념을 FCNFP의 기저 형성 및 변화에 적용한 방법이다. 한편, 본 논문에서 제안하는 Block Pivot을 이용한 다중 기저형성법은 기존의 단일 기저형성법과 같이 내부 기저형성법으로 분류된다.
본 논문에서는 FCNFP의 다양한 예제들을 통해 제안된 다중 기저형성법에 의한 결과와 기존의 단일 기저형성법 및 CPLEX 7.0을 이용한 실험 결과를 비교·분석한다. 여기에서 CPLEX 7.0을 이용한 실험은 FCNFP를 혼합 정수계획법(Mixed Integer Programming)으로 모형화한 후, CPLEX 7.0 SOLVER가 자동으로 선택하는 분지한계법(Branch and Bound) 및 분지절단법(Branch and Cut)에 의한 실험을 의미한다.
제안된 다중 기저형성법의 결과는 비교되는 두 가지 방법에 비해 수행도 측면에서 우수한 결과를 나타낸다. 특히 소규모 문제(노드 70개 이하, 호 300개 이하)의 수행시간은 3.5초를 넘지 않았다. 따라서, 본 논문에서 제안하는 Block Pivot을 이용한 다중 기저형성법은 FCNFP의 해법으로써 효율적인 대안이 될 수 있다. 또한, Block Pivot을 이용한 다중 기저형성법으로 형성된 다양한 트리는 향후 메타 휴리스틱의 효율적인 이웃 구조 형성에 이용될 수 있다.

목차 (Table of Contents)

• Abstract = ⅰ
• 목차 = ⅲ
• 그림 목차 = ⅳ
• 표 목차 = ⅵ
• 제1장 서론 = 1
• 제1절 연구 배경 = 1
• 제2절 연구 목적 및 내용 = 2
• 제3절 논문 구성 = 3
• 제2장 문제 정의 및 FCNFP의 해법을 위한 배경지식 = 4
• 제1절 문제 정의 및 기존 연구 고찰 = 4
• 제2절 네트워크 단체법과 내부 기저형성법 = 8
• 제3절 Walker의 단일/순차적 기저형성법 = 12
• 제3장 다중 기저형성법을 이용한 FCNFP의 해법 =21
• 제1절 Block Pivot을 위한 수정 할인가 = 21
• 제2절 Block Pivot을 이용한 다중 기저형성법 = 36
• 제4장 실험 및 결과 = 41
• 제1절 단일/순차적 기저형성법 = 41
• 제2절 Block Pivot을 이용한 다중 기저형성법 = 42
• 제5장 결론 및 향후 과제 = 48
• [참고 문헌] = 50