확률 네트워크에서 신뢰할만한 최단경로 탐색은 여행 신뢰도가 교통시스템의 중요한 성과 척도로서 인식이 증가하면서 최근 교통부문 연구자들로 많은 관심을 끌고 있음.
여행자들은 아래와 같은 이유로 노선 선택함으로서 여행신뢰도를 고려한다고 가정하곤 함.

 

 - 평균 여행비용 합의 최소화 및 안전도의 표준 편차 관련 안전도 마진
 - 선택 노선이 최단 경로일 확률 극대화
 - 여행시간의 평균 및 분산의 파레토 최적(pareto optimal)화
 - 모든 가능한 시나리오 중 최대(최악의 경우)여행 시간의 최소화
 - 가능한 최소 여행시간 달성

 

신뢰할만한 최단 경로는 지정된 시간 또는 그 시간 이전에 최종 종착지에 도착할 기대 확률을 보장하는 최소한의 사간 배분을 요구하는 경로로 정의
RASP(Reliable a priori Shortest Paht)를 찾는 문제는 Nei and We(1976)의 연구를 통해 조성되었는데, 이 문제는 FSD(First-order Stochastic Dominance) 하에서의 모든 비우월적 경로를 열거함으로서 찾을수 있음을 보임.
신뢰할만한 노선 문제에 관한 대부분의 연구는 도로 여정(운행)시간 분포가 시간독립적(time independent)이라고 가정
그러나 도로 운행 시간의 동적 특성을 상기하는 것이 보다 용이함.
특히 여행시간 분포는 피크시간대 통행량의 영향에 따라 상당히 변화하기 쉬움.
선행연구(Nie and Wu, 2009)에서는 RASP 문제의 공식(formulation)이 시간 종속적(time dependent)인 경우에 쉽게 들어맞을 수 있음을 발견
동 연구는 나아가 위와 같은 가정에서 RASP문제를 푸는 알고리듬을 제안
해찾기 방법론은 모든 연계노선 여행시간 분포가 동일한(identical) 이산 간격(discrete interval) 및 동일한 수의 지원 지점(support point)을 갖는다고 가정
대형 도로 네트워크에 대해서 장거리 여행시간은 짧은 연계도로의 여행시간보다 더 길 수 있음.
따라서 극단적인 경우(최장거리 경로 및 최단 노선의 연계) 종종 짧은 이산 간격 선택을 통해 매우 많은 수의 지점 간격을 선택하게 되기도 함.
대부분의 사례에서 위와 같이 극단적인 경우는 불필요한 분석 사례이며, 이와 같은 경로 산정방식은 특히 대형 네트워크 시에 비효율적임.

선형 연구(Nie and Wu, 2009)의 수치적 사례(Numerical example) 분석에서는 이미 이와 같은 비효율성이 제기됨.
단순화를 위해 동 연구는 연계 여행시간의 분포가 공간적으로 상호 상관관계가 없다고 가정
Nie and Wu(2009)는 연계 여행시간 분포가 서로 상관관계에 있는 경우 동적 확률 네트워크 상에서 신뢰할만한 최단경로 찾기를 시도
그들은 모형 상관관계에 마코비안(Markovian) 이행확률(transition probability)을 적용하고 동적 프로그래밍이 문제를 풀수 있도록 하기 위한 이행 확률 상의 몇가지 제약조건을 부과
그러나 대형 네트워크 상에서 신뢰할만한 최단 경로 문제에 대한 알고리듬 적용에 어려움 존재
상관관계는 공분산 행렬을 이용해 고려되기도 함(Sen et al,2001; Sivakumar et al, 1994).
여전히 동적 프로그래밍은 위와 같음 모형에 일반적으로 적용하기 어려움.
대신 비선형 또는 정수 프로그래밍 기법 및 해찾기 기술이 사용되어야 함.
그러나 이와 같은 방식 적용은 어떤 실제적 교통 네트워크에의 적용을 어렵게 하는 문제를 야기

본 연구의 목적은 시간 종속적 RASP 문제를 푸는데 있어서 치명적인 제약조건을 해결하기 위한 보다 효율적 해차직 접근방식을 개발하고자 함
본 연구는 알고리듬 수립에서 다음의 두 가지 점에 중점을 두고 있음.

 

 - 노선 여행시간 분포 계산에 컨볼류션 기법(convolution method) 사용
 - 동 방법론을 비우월적 경로 결정에 사용

 

Wu and Nie(2009)는 시간 독립적 RASP 알고리듬에 대해 몇몇 컨볼루션 기법을 이용한 비교 연구를 수행
그들의 연구 결과는 ADA(Adaptive Discretization Approach)이 정확성과 효율성 간의 최우선 균형을 깨뜨린다고 제안
그러나 시간 종속적인 경우는 각각의 출발시간에 대응한 다중 연계 분포를 포함하기 때문에 노선도가이 더욱 복잡해짐.
본 연구의 일차적 목적은 따라서 정태 네트워크에서 이미 사용되고 있는 현존 컨볼루션 기법이 동적 네트워크에서의 노선 분포도 시행에 적절한지 살펴보고 만일 그렇지 않다면 더 나은 대안과 문제점을 제시하고자 함. 

동적 네트워크에서 RASP문제를 풀기위해 동적(Dynamic) ADA 방법론과 b-discrete 방법론 활용
DADA(Dynamic Adaptive Discretization Approach)의 투입값은 연계 여행 시간 분포합수 집합, 여행시간 분포 경로, 이산적 출발시간이며 결과값은 동 노선에서의 여행시간 분포값임.
b-discrete 방법론은 아래와 같은 방식으로 산정

where
u: 여행자가 만일 경로 k를 이용해 i지점에서 s(종착지)까지 간다면 시간 배분 b 이내에 도착할 확률
L: 이산 여행 시간 간격, t=0, phi, ...
phi: 여행시간 해상도(resolution), 충분히 작게 설정
b: 0, phi, 2phi,...L*phi
T=L*phi, 최후 출발 시간 또는 가장 긴 시간 배분,
P(lphi): 출발시간 T-b일 때 ij연계 노선 상 여행시간 lphi의 확률 함수(probability mass)

자료출처: Transportation Research Record 2333, TRB(2013), Finding Reliable Shortest Paths in Dynamic Stochastic Networks, p.82

연계 여행시간 분포는 감마(gamma) 또는 균일 분포(uniform distribution)를 갖는다고 가정
비록 실제 여행 시간이 두 분포가 아닐지라도 본 연구 목적은 이산 방법론의 성과에 관한 분포함수의 형태별 영향을 살펴볼 수 있으므로 의미를 가질 수 있음.
시간 간격 체계는 다음과 같이 4개로 구분

 

 SectionI) phi-0.1, L=1000
 Section II) phi-0.2, L=500
 Section III) phi-0.4, L=250
 Section IV) phi-1, L=100

 

위 시나리오별로 두 가지 컨볼루션 기법을 적용한 계산 결과는 그림 1과 같다.

a) 감마 분포, 10 연계노선, b) 감마 분포, 20 연계노선, c) 균일 분포, 10 연계노선, d) 균일 분포, 20 연계노선
자료출처:Transportation Research Record 2333, TRB(2013), Finding Reliable Shortest Paths in Dynamic Stochastic Networks, pp.86-87.

 

 

그림 1 결과에 의하면 b-discrete 방법에 의해 생성된 컨볼루션 결과가 기대했던 대로 여행 시간 분해간격 phi에 더 민감한 것으로 나타남.
예를 들면 20개 경로에 대해 만일 phi가 0.1에서 1로 증가하면 평균 오차는 감마분포에서 109%, 균일분포에서 105%로 나타남.
반면 DADA방법의 경우 phi에 상대적으로 덜 민감하여 평균 오차가 각 분포에 대해 4%, 5%에 불과
그러므로 DADA방법을 적용할 경우 phi가 충분히 작은지에 대한 고려를 통해 각각의 연계노선 여행시간 분포를 확인할 필요성이 없음.

본 연구의 수치해석 분석결과 결론은 다음과 같이 요약할 수 있음.

 

수치분석 결과는 DADA가 비록 b-discrete방법보다 계산시간 면에서는 더 오래 소요될 수 있지만 그 차이는 무시할만함.
또한 DADA방법은 여행시간 간격에 대해 b-discrete기법에 상대적으로 훨씬 안정적인 해를 도출

 

동적 네트워크에서 RASP문에의 최적 해는 FSD(1계 확률 우월: 1st-order stochastic dominance) 규칙 하에 비우월적 경로로 나타나야만 함.
수치 실험 결과 SSD는 훌륭한 근사 해를 생산하고 이러한 근사치 해가 최적해와 동일하지 않다면 보다 보수적인 산정수치라 할 수 있으며, 위험회피형(risk-averse) 여행자라면 채택가능

 

동적 네트워크에서 신뢰할만한 최단경로 문제를 찾는데 소요되는 계산시간은 SSD(second order stochastic dominance) 규칙 하에서 최소 50% 절감(비록 TSD-third order stochastic dominance 방식의 해가 SSD와 동일한 결과를 산출하나 시간소요가 더 크게 나타남)

 

본 연구의 분석 결과는 RASP를 동적 네트워크에서 풀 때 DADA가 b-discrete방식에 비해 보다 나은 결과를 도출하는 컨볼루션 기법임을 제안하고 있음.
그러나 DADA기법 적용 시 여전히 최후 출발시간 T가 주어져야 하며 이것은 결정하기 어려운 문제임.
만일 T가 너무 작을 경우 DADA기법은 적절히 시행될 수 없음.
가장 이상적인 기법은 T와 독립적인 적용이 가능해야 할 것이며 이것은 앞으로도 더 조사, 연구가 필요