This thesis is concerned with the topological design of a facility network for broadband communications. In designing the facility network, transmission facilities such as concentrators, multiplexers and digital cross-connect systems are usually introduced to use the communication cable efficiently. In consideration of the fact that the hubbing topology is recommended as one of the economic and attractive structures for broadband communication network, we concentrate the research interest on the design of facility network with hubbing topology. To design such network, three kinds of major cost components are considered: fixed cost of establishing a hub facility, fixed cost of placing conduit and variable cost of installing cables. The tradeoffs between these major costs will be fully accounted for in this thesis. It is, however, such an immensely complicated task to optimally capture the tradeoffs between all these costs.
Owing to the serious drawback of the conventional approach of partitioning the whole problem into three subproblems, it is desired to directly deal with the problem in an integrated framework. In this respect, we will develop the unified model to design facility networks with hubbing topology having the minimal total cost, and also develop efficient solution methods.
First, we consider the design of facility network for centralized communication systems, which is commonly found in the local access communication networks. By introducing a dummy node and some dummy arcs, we formulated the problem as a variant of classical network design model, allowing the incorporation of the well-known dual-ascent solution strategy. Despite the complexity inherent on the design problem, the performance of the proposed solution heuristic is shown via the extensive computational experiments with large-scale test problems.
Second, we deal with the problem for a facility network design of large-scale communication systems with regional restrictions, which is usually applied to the inter-switching office network design problem. The whole area is partitioned into a certain number of regions, each having only one hub established. Such network structure has been implemented in many real-world communication network where the boundary of local network are dominated by some factors such as a community of interest and a geographical area. A comprehensive design model is formulated as a 0-1 linear programming problem embedding multicommodity network flow problem. Owing to the intrinsic difficulty of the problem, we concentrate on developing an heuristic method to find a good near optimal solution. Exploiting the special structure of the model, a dual based heuristic is developed for obtaining near optimal solutions.
통신기술의 발달은 다양한 통신 서비스를 하나의 통합된 망으로 부터 제공할 수 있는 종합정보통신망(ISDN)의 출현을 가져오게 되었다. 이러한 ISDN에서는 음성과 데이타 정보가 동시에 제공됨으로 인하여, 통신망의 효율성을 증대시킬 수 있을 뿐만아니라 새로운 종류의 다양한 부가가치 통신서비스의 출현을 가져오게 되어, 정보 통신에 대한 사회적인 욕구를 충족시킬 수 있다. 그러나 ISDN으로는 많은 대역폭을 요구하는 광대역 서비스(영상정보교환 등)를 제공할 수 없기 때문에, 최근들어 광대역서비스가 가능한 통신망(광대역 통신망)에 대한 연구가 활발히 진행되고 있다. 이와같은 광대역 통신망은 광섬유 케이블 및 광통신기술의 발달과, 관련 장비가격의 하락으로 급속히 확대되고 있는 추세이다.
광대역 통신망은 광섬유 케이블 및 광전송 시스템으로 구성되고 있기 때문에, 기존의 복잡한 메쉬(mesh)구조로는 경제적이고 효율적인 망을 구성할 수 없다. 이와같은 망에 대하여 효과적인 망 구조의 하나로 제시되고 있는 것이 Hubbing 구조이다. 즉, 일정한 지역의 허브노드에 전송설비(DCS, ADM)를 설치함으로써 광케이블의 효율적인 활용을 도모할 뿐만아니라, 망 운용관리 및 확장시에 효과적으로 활용될 수 있다. 광대역 통신망을 경제적으로 설계하기 위해서는 다음과 같은 3가지 주된 비용요소를 고려하여야 한다: 전송설비(허브)의 설치와 관련된 고정비용, 통신케이블 설치에 필요한 관로의 개설비용, 통신케이블 설치비용, 따라서 이들 세 비용요소간의 상충관계를 고려하는 광대역 통신망의 설비망 설계문제는 전송설비(허브)의 위치, 관로망 구성 및 관로망을 통한 케이블 설치를 최소의 비용으로 설계하기 위한 것이다.
전통적인 방법에서는 이러한 망 설계문제를 몇개의 부문제로 나누어, 반복적 해법을 통해 해결하여 왔으나, 많은 시간과 노력에도 불구하고 얻어지는 해의 정확도에 대한 객관적 평가를 할 수 없었다. 본 연구에서는 이 같은 방법과는 달리, 하나의 통합된 최적화 모형으로 해결하기 위한 접근법을 시도하였다. 본 연구에서 고려된 주요내용은 다음과 같다.
첫째, 공중통신망의 가입자 망이나, 컴퓨터 통신망에서 흔히 볼 수 있는 중앙집중식 통신망에 대한 설비망 설계문제를 고려하였다. 즉, 일반 이용자를 적절한 위치에 설치된 전송설비(허브)에 연결하고, 설치된 허브를 중앙의 노드와 고속, 대용량의 통신케이블로 연결함으로써, 전체 망 구성비용을 최소화하기 위한 문제이다. 이 문제에 대하여 가상 노드와 가상 아크를 도입한 망 설계문제를 고려한 결과, 기존의 전통적 망 설계문제의 변형된 형태로 정식화되었으며, 다품목 흐름문제를 포함하는 문제 구조를 이용하여 효과적인 쌍대 기반해법을 적용할 수 있었다.
둘째, (광대역)공중통신망에서 주로 적용되는 분산된 전송설비간의 연결을 고려하는 분산된 통신망에 대한 문제를 다루었다. 이 경우에는 전체 대상 망을 지리적 여건과 행정단위에 따라 몇개의 지역으로 구분하고, 각 지역에 하나의 전송설비(허브)를 설치하는 것으로 가정하였다. 이 문제도 앞의 경우와 같은 접근방법을 통하여, 비교적 간단한 제약 조건이 추가되는 전통적 망 설계문제로 정식화 되었고, 문제의 특수한 구조를 이용한 효과적인 쌍대 기반해법을 적용할 수 있었다.
셋째, 이상의 연구 결과를 토대로 광대역 통신망에서 중요하게 고려되는 생존도 (survivability) 문제를 제약조건으로 추가한 생존도가 고려된 망 설계문제를 다루었다. 즉, 어느 하나의 아크 손실에 대하여도 허브노드간에 통신이 가능하도록 하기 위하여, 설치된 허브간에 아크를 공유하지 않는 경로를 선정하는 제약조건을 추가로 고려하였다. 이 문제에서도 앞의 두 경우와 같은 접근방법과, 품목(commodity)에 대한 적절한 정의를 통하여, 전통적인 망 설계모형의 변형된 형태로 정식화 될 수 있다. 또한, 지리적인 제약이 없는 보다 일반적인 설비망 설계문제는 문제의 복잡도 때문에 하나의 모형으로 정식화하는 것 조차 매우 힘든 일이었다. 그러나 이 문제에 대하여도 가상 노드 및 가상 아크와 적절한 품목정의를 함으로써, 통합된 설계모형의 수립이 가능할 수 있었다.
이상의 연구는 세가지 의사결정 변수간의 복잡한 상충관계를 하나의 통합된 모형으로 적절히 정식화하고, 문제의 특수한 구조를 이용하여 효과적인 쌍대 기반해법을 개발하기 위한 접근방법을 제시하고 있다. 따라서, 본 연구에서 고려된 문제를 보다 현실적인 문제로 확장하고, 망 설계 및 입지선정 문제가 결합된 복잡한 문제에 대한 연구에 많은 도움이 될 것이다.
