A stocastic flow network is a useful structure for representing various transmission systems(e.g., power transmission, pipeline, traffic, communication systems) in which the flow capacity of each element can be described by a random variable. An important performance measure for such systems is the so called 'flow network reliability' which is defined as the probability that a required amount of flow can be transmitted from a source to a terminal.
The minimal upper vector approach is an exact and general method for calculating the flow network reliability of a network with discrete random element capacities. It consists of two steps, namely, determination of minimal upper vectors(or minimal upper paths for a binary-state network) and calculation of the desired reliability. Although extensive research has been conducted for the second step, little work has been concerned with developing efficient methods for the first.
This thesis develops an algorithm for determining the minimal upper paths of a binary-state planar flow network. The proposed method constructs a tree of subnetworks generated by combining minimal paths, and eliminates unnecessary subnetworks from the tree based upon four elimination criteria developed. Computational results indicate that the criteria are effective in reducing the number of explicitly considered subnetworks, and thereby, in reducing the amount of computational effort required.
The minimal upper vectors can be used to identify the most reliable path for sending a required amount of flow from a source to a terminal in a stochastic flow network. An algorithm for determining the most reliable path of a binary-state planar flow network is also developed in this thesis. The proposed method constructs a tree of subnetworks in a similar way as in determining minimal upper paths. Additional criteria are developed to eliminate unnecessary subnetworks from the enumeration tree. Computational results indicate that the elimination criteria are effective in reducing the amount of computational effort required for determining the most reliable path.
확률적 흐름 네트워크는 각 원소의 흐름 용량이 랜덤한 값으로 주어지는 네트워크로서 다양한 전송시스템(예를들어 전력전송, 파이프라인, 트래픽, 통신시스템)을 표현하기 위한 유용한 구조로 사용되고 있다. 흐름 네트워크 신뢰도는 이러한 시스템의 중요한 성능척도로서 한 출발점에서 한 도착점까지 주어진 요구량을 전송할 수 있는 확률로 정의된다.
최소상위벡터방법은 네트워크 각 원소의 흐름 용량이 이산적 확률변수로 주어질 때 흐름 네트워크의 신뢰도를 계산하기 위한 일반적이며 정확한 방법이다. 이 방법은 2가지 단계, 즉 최소상위벡터(각 원소의 상태가 두가지인 네트워크일 때는 최소상위경로)를 구하는 방법과 신뢰도를 구하는 방법으로 구성된다. 비록 두번째 단계에 대해서는 폭넓은 연구가 되어 있으나, 첫번째 단계를 위한 효율적인 방법의 개발에 관한 연구는 별로 이루어져 있지 않다.
본 논문에서는 플래너 흐름 네트워크에서 최소상위경로를 구하는 알고리듬을 개발하였다. 제안된 방법은 최소경로들을 조합한 서브네트워크의 나무를 만들고, 개발된 4가지 제거기준에 의하여 이 나무에 서 불필요한 서브네트워크들을 제거시킨다. 전산실험의 결과, 본 연구에서 개발된 제거기준이 고려대상이 되는 서브네트워크의 수와 계산시간을 줄이는 데 효과적임을 확인할 수 있었다.
최소상위경로는 확률적 흐름 네트워크의 한 출발점에서 한 도착점까지 어떤 흐름양을 보내기 위한 최대신뢰도 경로를 구하는 데 활용 될 수 있다. 본 논문에서는 플래너 흐름 네트워크의 최대신뢰도경로 를 구하기 위한 알고리듬도 아울러 개발하였다. 제안된 방법에서는 최소상위경로를 구하는 방법과 마찬가지로 서브네트워크의 나무를 만들고, 이 나무로부터 불필요한 서브네트워크들을 제거하기 위해 추가로 제거기준을 개발하였다. 전산실험의 결과, 개발된 제거기준이 최대신뢰도경로를 구할 때 요구되는 계산량을 줄이는 데 효과적임을 확인하였다.
