Two-Level Hierarchical Network Design Problem with Surviability Constraints

Abstract

본 논문은 생존제약식을 갖는 2계위 망의 설계 문제를 다루었다. 생존제약식을 갖는 망의 설계문제는 기간망의 각 마디에서 중심마디까지의 연결되는 경로가 최소한 2개 이상이 되도록 기간망을 설계하는 것으로 기간망의 가지를 전송용량이 매우 큰 光電線으로 설치할 때 발생되는 문제이다. 본 논문에서는 이 문제를 0-1 정수계획모형으로 모형화 하였다. 또한 모형의 雙對構造의 특수성을 이용하여 이 문제를 매우 효과적으로 풀 수 있는 雙對基般 探索法(Dualbased Heuristic)을 개발하였고 기간망의 크기가 50개이고 수요마디의 수가 200개 정도까지의 약 100여개의 문제에 대한 컴퓨터 계산결과를 통하여 해법의 효율성을 입증하였다.

This paper deals with the topological design problem of a hierarchical two-level network with two-connected survivability constraints. As a means to widen the real-world applicability over the existing network design studies, a backbone node not opened is allowed to be included in the backbone tree for transhipment purpose. The problem is modelled as a mixed 0-1 linear programming, whose special structure is exploited for the development of a dual-based heuristic procedure. The effectiveness of the solution procedure is well demonstrated by the computaional experiments conducted with a variety of problems ranging up to 50 backbone nodes and 200 demand points.

This paper deals with the topological design problem of a hierarchical two-level network with two-connected survivability constraints. As a means to widen the real-world applicability over the existing network design studies, a backbone node not opened is allowed to be included in the backbone tree for transhipment purpose. The problem is modelled as a mixed 0-1 linear programming, whose special structure is exploited for the development of a dual-based heuristic procedure. The effectiveness of the solution procedure is well demonstrated by the computaional experiments conducted with a variety of problems ranging up to 50 backbone nodes and 200 demand points.