This thesis deals with the problem of finding an optimal shortest path in a stochastic path network where each arc weight is a random variable and some arcs are fixed at positive failure probabilities. In order to consider the risk attitude of a decision maker, a quadratic utility function is introduced. The problem is handled in a subpath comparison rule approach based on some dominant properties such that we may not have to enumerate all paths. Then an algorithm is exploited and illustrated with a numerical example.
A stochastic shortest path problem is also considered without arc failures and shown that it can be solved by a linear programming approach.
본 논문에서는 호의 가중치가 각각 독립인 확률변수로 주어진 네트워크, 즉 확률적 네트워크, 상에서 최단거리 경로를 탐색하는 문제를 다루었다.
첫번째로 호가 고장날 확률이 주어진 상황에서 최단거리 경로문제를 다루었다. 의사결정자의 위험기피성향을 반영하기 위하여 각 호의 평균 가중치와 분산값이 주어진 상황에서 2차 효용함수를 도입하였다. 문제 해결 방법으로는 모든 경로를 대상으로 비교하지 않도록 우월성질(dominance property)을 바탕으로 하위경로 비교법(subpath comparison rule approach)을 사용하였다. 간단한 예제를 통하여 알고리즘을 설명하였다.
두번째로 호가 고장날 확률이 주어지지 않은 확률적 네트워크상에서 최단거리 경로를 찾는 문제에 대하여, 그 해가 선형 계획법의 해법으로 찾아질 수 있음을 보였다.
