This thesis deals with the problem of the design of the minimum-cost centralized network with multipoint linkage where options are available as to discrete link capacities.
In this thesis, the concept of the 'main path' which is the path from a node to the center is introduced. Information requests, link capacity, and link cost are considered as important factors. It is assumed that the rate and manner in which information is requested at terminals is fixed. It is shown that the problem can be formulated as a mixed integer program.
Many heuristic methods as well as the optimization technique for one capacity were developed, of which Esau-Williams algorithm is known to be the best.
This thesis develops a heuristic algorithm for the case of capacity options, based on Esau-Williams algorithm. This algorithm essentially applies the link exchange technique, and in each link exchange, the flow change with the associated capacity change on the main path is checked.
The motivation for such efforts also stems from a need of an advanced procedure that can be applied to the case of discrete cost functions.
본 연구에서는 중앙 집중식 전산망의 설계에 있어서 회선의 용량이 여러 개인 경우에 대하여 발견적 해법을 개발 하였다.
본 연구에서 취급한 모형은 각 터미널에서 발생하는 정보량과 그 발생형태가 시간에 관계없이 일정하고 전산망의 모양이 나무 형태인 경우이다. 여기서는 정보량, 회선용량, 회선비용을 주요 변수로 삼았으며, 정보량이 주어졌을때 이를 처리할 수 있는 회선의 용량을 얼마로 하면 회선의 총 설치 비용이 최소화 되겠는가 하는 것이 본 연구의 목적 함수이다. 이 모형은 혼합 정수 계획으로도 정식화될 수 있겠으나, 계산 시간이 좀 더 효율적인 해법이 필요하다 하겠다.
회선의 용량이 하나 뿐인 경우에 대해서는 최적 기법은 물론이고 효율적인 발견적 기법이 다수 개발 되었는데 그 중에서 Esau-Williams 의 해법이 가장 좋다고 알려져 있다. 본 연구에서는 Esau-Williams 의 해법이 기본 구조를 응용하여 회선의 용량이 여러 개인 경우에 대해서 발견적 기법을 개발하였다. 즉 설치 계획이 되어 있는 하나의 링크와 아직 설치 계획이 없는 하나의 링크를 서로 교환한다고 할 때의 비용 절감을 구해 본다. 이러한 여러개의 쌍 중에서 비용 절감이 가장 큰 한쌍의 링크를 골라 서로 교환하는 방법인데, 이는 근본적으로 링크 교환 기법의 일종이다.
이렇게 개발된 해법은 그 계산 시간의 한계가 만족할만 하며 목적 함수의 값도 별로 나쁘지 않음을 알 수 있었다. 또한 본 연구의 모형은 전화선 설치 문제, 상품 분배 통로문제, 상하수도 설치문제등에도 적용시킬수 가 있다. 본 연구의 확장으로서 최적 기법의 개발이 필요하며, 전산망의 모양이 나무형태라는 가정이 없는 모형에 대해서도 연구가 진행 되어야 할 것이다.
