기존의 링크기반의 Frank-Wolfe 통행배정 기법은 구현의 용이성과 결과의 안정성 등으로 인해 널리 사용되어 왔으나, 교통분석을 위해 사용하는 기초자료의 크기와 정밀도가 향상됨에 따라 수렴성에 대한 논란이 제기되었다. 본 연구에서는 개별링크기반의 통행배정 기법 외에 경로기반, 출발지기반 알고리즘을 이용한 분석결과의 안정성, 적용가능성에 대한 검토를 수행하였다. 분석결과 각각의 상용프로그램 및 통행배정기법별로 결과의 차이가 일부 존재하지만 수렴성이 어느 정도 확보된 이후부터는 안정된 결과를 도출하는 것으로 나타났다. 특히 대규모 교통망에서 통행배정 모형이 충분히 수렴되지 않은 상태에서는 수렴성 및 종료기준에 따라 분석결과의 안정성에 관한 문제가 제기될 가능성이 존재하였다. 따라서 실무적으로 적정한 수준의 수렴성 확보 및 안정된 결과 값을 도출하고자 하는 노력이 요구된다.
기존의 링크기반의 Frank-Wolfe 통행배정 기법은 구현의 용이성과 결과의 안정성 등으로 인해 널리 사용되어 왔으나, 교통분석을 위해 사용하는 기초자료의 크기와 정밀도가 향상됨에 따라 수렴성에 대한 논란이 제기되었다. 본 연구에서는 개별링크기반의 통행배정 기법 외에 경로기반, 출발지기반 알고리즘을 이용한 분석결과의 안정성, 적용가능성에 대한 검토를 수행하였다. 분석결과 각각의 상용프로그램 및 통행배정기법별로 결과의 차이가 일부 존재하지만 수렴성이 어느 정도 확보된 이후부터는 안정된 결과를 도출하는 것으로 나타났다. 특히 대규모 교통망에서 통행배정 모형이 충분히 수렴되지 않은 상태에서는 수렴성 및 종료기준에 따라 분석결과의 안정성에 관한 문제가 제기될 가능성이 존재하였다. 따라서 실무적으로 적정한 수준의 수렴성 확보 및 안정된 결과 값을 도출하고자 하는 노력이 요구된다.
Existing link-based Frank-Wolfe algorithm has been widely used, thanks to its ease of simulation and stable results; however, it comes with low convergence issue towards near the optimum value. Such issue was not considered as a major drawback in the past. However, in the present, some arguments hav...
Existing link-based Frank-Wolfe algorithm has been widely used, thanks to its ease of simulation and stable results; however, it comes with low convergence issue towards near the optimum value. Such issue was not considered as a major drawback in the past. However, in the present, some arguments have occurred over the method's stability, analysis time, and other limits as the size and details of the fundamental data for traffic analysis have vastly improved. Therefore, this paper compared the theoretical attributes and the pros and cons between the Frank-Wolfe algorithm and the Origin-based algorithm and Path-based algorithm newly being developed. As a result of this paper, there is possibility that a problem of stability may arise depending on the convergence and exit criteria. Thus, In practice, this effort to derive the appropriate level of convergence is required to secure and stable results.
Existing link-based Frank-Wolfe algorithm has been widely used, thanks to its ease of simulation and stable results; however, it comes with low convergence issue towards near the optimum value. Such issue was not considered as a major drawback in the past. However, in the present, some arguments have occurred over the method's stability, analysis time, and other limits as the size and details of the fundamental data for traffic analysis have vastly improved. Therefore, this paper compared the theoretical attributes and the pros and cons between the Frank-Wolfe algorithm and the Origin-based algorithm and Path-based algorithm newly being developed. As a result of this paper, there is possibility that a problem of stability may arise depending on the convergence and exit criteria. Thus, In practice, this effort to derive the appropriate level of convergence is required to secure and stable results.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
최근 일부 연구들은 Frank-Wolfe algorithm의 통행배정 기법이 최적해 근처에서 수렴성이 저하되는 문제를 갖고 있다고 발표하였다. 따라서 본 연구는 교통량 및 편익산출을 위한 통행배정모형의 수렴성을 판단하고 종료기준에 대한 연구를 수행하고자 한다. 구체적으로 먼저 통행배정모형의 이론적 검토 및 수렴성판단과 관련된 기존연구를 검토하고, Toy-Network 및 실제 대규모 네트워크를 기반으로 사례분석을 실시하여, 통행배정 알고리즘별 알고리즘 종료조건에 따른 교통량, 편익의 수렴성을 검토하였다.
따라서 본 연구에서는 우선 통행배정 단계에서 사용되어 온 기존의 FWA 기반모형과 새롭게 개발되고 있는 모형간의 이론적 특징 및 장·단점을 비교하고, 국내·외에서 널리 사용하고 있는 상용프로 그램(EMME, TransCAD, CUBE)의 적용 알고리즘에 따른 수렴성 검토를 수행하였다.
본 연구에서는 개별링크기반(Link-Based)의 통행 배정 기법 외에 새로운 통행배정기법(경로기반, 출발지기반)을 대상으로 통행배정알고리즘의 수렴성을 검토하고 적정수준의 종료기준을 제시하고자 하였다. 분석결과 수렴성이 어느 정도 확보된 이후부터는 비교적 안정된 결과를 도출하는 것으로 나타났다.
본 연구에서는 기존에 주로 사용하여왔던 개별 링크기반(Link-Based)의 통행배정 기법 외에 새로운 통행배정기법(경로기반, 출발지기반)을 이용한 분석 결과의 안정성, 적용가능성 등에 대한 검토를 수행하고자 한다. 구체적으로는 먼저 개별 알고리즘의 교통량 수렴정도의 차이를 비교하기 위해서 통행배정 결과의 참값을 직접 계산할 수 있는 가상의 toy-network 구축하고, 실제 계산상의 값과 국내외에서 널리 사용되고 있는 상용프로그램인 EMME, TransCAD, Cube의 적용 알고리즘별 산출값과 비교하여 개별 알고리즘이 정확성, 수렴성에 대해서 검토하하였다.
가상의 교통망 (Toy-Network)에서, 알고리즘들이 계산된 최적해에 수렴할 수 있는지 확인 할 수 있다. 이 논문은 link 기반 알고리즘과 path 기반 알고리즘 또는 출발지 기반 알고리즘(Origin-Based Algorithm)의 기법별을 통하여 안정한 유일한 해를 찾을 수 있을지 확인할수 있다. 대규모 네트워크에서는, 각 프로그램 및 통행배정 기법별로 가상의 사업시행 전후에 따른 주요 통행배정 결과값이 합리적인 가를 확인 할 수 있다.
다음으로 대규모 네트워크에 각 상용프로그램의 적용 알고리즘별로 수렴성, 배정된 교통량, 수렴정도에 따른 편익 변화 분석을 수행한다. 이를 통해서각 프로그램의 적용 알고리즘별로 수렴성에 대한 검토를 수행하고, 안정화단계에 이르는 통행배정 종료조건을 제시하고자 한다.
이에 본 연구에서는 알고리즘의 유형을 크게 Link-Based Algorithm(Frank-Wolfe Algorithm), Path-Based Algorithm, Origin-Based Algorithm의 3가지로 구분하여 접근하고자 하였다.
가설 설정
본 분석의 경우 평균 V/C에 따라 시나리오를 선정하였으며 이는 비혼잡 상황과 혼잡상황, 극심한 혼잡상황으로 구분할 수 있다. 따라서 본 분석에서는 V/C에 따라 시나리오를 설정하였으며, 구체적으로 시나리오 1의 경우 V/C 0.4, 시나리오 2의 경우 V/C 1.0, 시나리오 3의 경우 V/C 2.0로 설정하였다.
제안 방법
Toy-network를 교통수요 프로그램으로 통행배정 종료조건에 따라 통행배정을 수행한 결과를 분석해 보았다. 교통수요 분석 프로그램별 목적함수 값은 다르지 않은 것으로 판단 할 수 있다.
교통 분석 프로그램별 알고리즘에 따른 수렴정도 분석에 앞서 본 연구에서는 Toy-network를 설정 하여 각 알고리즘별 안정성 및 기능을 파악하려 한다. 이를 위해 총 16개 링크로 구성된 toy-network을 구성하고 평균 V/C에 따른 통행량(O/D)를 구성하여각 링크별 통행량과 통행시간, 목적함수 값을 실제 계산상의 값과 교통분석 프로그램의 알고리즘 별 값과 비교하였다.
따라서 본 연구는 교통량 및 편익산출을 위한 통행배정모형의 수렴성을 판단하고 종료기준에 대한 연구를 수행하고자 한다. 구체적으로 먼저 통행배정모형의 이론적 검토 및 수렴성판단과 관련된 기존연구를 검토하고, Toy-Network 및 실제 대규모 네트워크를 기반으로 사례분석을 실시하여, 통행배정 알고리즘별 알고리즘 종료조건에 따른 교통량, 편익의 수렴성을 검토하였다. 마지막으로 타당성조사 단계에서 안정적인 결과를 도출하기 위한 주요 기준에 대해서 제언하고자 한다.
본 연구에서는 기존에 주로 사용하여왔던 개별 링크기반(Link-Based)의 통행배정 기법 외에 새로운 통행배정기법(경로기반, 출발지기반)을 이용한 분석 결과의 안정성, 적용가능성 등에 대한 검토를 수행하고자 한다. 구체적으로는 먼저 개별 알고리즘의 교통량 수렴정도의 차이를 비교하기 위해서 통행배정 결과의 참값을 직접 계산할 수 있는 가상의 toy-network 구축하고, 실제 계산상의 값과 국내외에서 널리 사용되고 있는 상용프로그램인 EMME, TransCAD, Cube의 적용 알고리즘별 산출값과 비교하여 개별 알고리즘이 정확성, 수렴성에 대해서 검토하하였다.
다음으로 대규모 네트워크에 각 상용프로그램의 적용 알고리즘별로 수렴성, 배정된 교통량, 수렴정도에 따른 편익 변화 분석을 수행한다. 이를 통해서각 프로그램의 적용 알고리즘별로 수렴성에 대한 검토를 수행하고, 안정화단계에 이르는 통행배정 종료조건을 제시하고자 한다.
다음으로, 각 교통수요 분석프로그램의 미시행 시나리오에 대하여 각 링크의 평균 교통량을 추정하고, 프로그램별 편차를 추정해 봄으로서, 교통수요분석 프로그램에 따른 추정 교통량의 차이를 비교하였다. 각각의 프로그램의 편차는 FWA의 경우, -2.
둘째로, TransCAD는 반복연산횟수를 10,000번으로 설정하였으며 Relative-Gap = 0을 종료조건으로 적용하였다. 반복연산 횟수가 증가함에 따라 출발지 기반 알고리즘(Origin Based Algorithm)은 링크기반 알고리즘(Frank Wolfe algorithm)보다 빠르게 Relative-Gap이 감소하였지만 더 이상 Relative-Gap 이 감소하지 않았다.
먼저 분석을 위해서 사업미시행시 각 교통수요 분석 프로그램별 통행배정 결과가 필요하다. 따라서 모든 프로그램에 대하여 경험적으로 FWA는 10-4의 Relative Gap을 종료조건으로 설정하였고, PBA, OBA는 EMME는 10-6 , 나머지 프로그램은 10-10을 종료조건으로 설정하였다. 그 외의 다른 종료조건은 동일하게 설정하였으며 최대 연산횟수를 10,000회를 설정하였다.
교통혼잡상황을 가정하여 토이네트워크 시나리오 설정에 따른 교통수요 분석 프로그램의 분석결과, FWA의 분석결과와 수학적 계산결과와의 차이는 PBA, OBA의 분석 결과 차이보다 조금 더 큰 값이 계산 되는 것으로 분석되었다. 또한 동일한 Toy-network에 통행량이 다를 때의 통행배정 결과를 비교해 보았다. 교통수요 분석 프로그램에 관계없이 동일한 목적함수 값을 도출해보면, V/C와 교통수요 분석 프로그램에 관계없이 분석 결과는 동일한 것을 확인 할 수 있었다.
먼저 일부 특정링크를 중심으로 미시행과 시행 시의 차이를 검토하였다. FWA의 경우, 프로그램별로 미시행과 시행시의 교통량 차이는 약 0.
본 분석의 경우 평균 V/C에 따라 시나리오를 선정하였으며 이는 비혼잡 상황과 혼잡상황, 극심한 혼잡상황으로 구분할 수 있다. 따라서 본 분석에서는 V/C에 따라 시나리오를 설정하였으며, 구체적으로 시나리오 1의 경우 V/C 0.
통행배정 모형은 크게 각 기·종점간에 시간 등의 비용이 최소가 되는 경로를 찾는 부분과 통행량을 교통망에 부하(Loading)하는 부분으로 나누어진다. 본 연구의 초점이 되는 통행량을 교통망에 부하하는 방법은 우선적으로 시간적 요소의 고려에 따라 동적(Dynamic) 모형과 정적(Static) 모형으로 구분된다. 다음으로는 용량과 확률요소의 고려에 따라 크게 네 가지로 구분되며, 그 동안 확률적 요소를 고려하지 않되 용량제약은 고려하는 Wardrop의 이용자 균형원리에 기반 한 모형이 가장 널리 적용되어왔다.
교통 분석 프로그램별 알고리즘에 따른 수렴정도 분석에 앞서 본 연구에서는 Toy-network를 설정 하여 각 알고리즘별 안정성 및 기능을 파악하려 한다. 이를 위해 총 16개 링크로 구성된 toy-network을 구성하고 평균 V/C에 따른 통행량(O/D)를 구성하여각 링크별 통행량과 통행시간, 목적함수 값을 실제 계산상의 값과 교통분석 프로그램의 알고리즘 별 값과 비교하였다.
토이네트워크 분석에서는 평균 V/C에 따라 시나리오를 적용하고자, O/D 통행량을 각 존pair별로 10,000, 30,000, 50,000통행으로 구성하였으며 내부 통행량을 제외한 존별 통행량은 동일한 것으로 설정하여 분석을 수행하였다.
프로그램별, 알고리즘별로 시나리오1, 시나리오2의 편익결과에 대해서 비교하였다. 시나리오1의 경우, 92백만원/일~97백만원/일로 산출되어서 약 4%의 차이를 보이고 있어서 유사하게 산정되는 것을 알 수 있다.
대상 데이터
대규모 네트워크에서는 한국의 Korea regional O/D/Network를 이용하여 분석을 수행하였다. Korea regional O/D/Network은 250개의 존, 27,654개의 node, 64,378link를 포함하는 대규모 네트워크로써, 한국 지역간 통행을 분석할 수 있는 데이터 이다.
분석사례는 다음과 같이 설정되었다. 시나리오 1의 경우 경부고속도로 [남이JCT~비룡 JCT]의 32.1km구간의 고속도로를 확장하는 사업으로 대규모 사업에 해당하고, 시나리오 2의 경우 영동고속도로[서창~안산]간 14.9km를 확장하는 중소규모 사업으로 시나리오를 설정하였다.
이론/모형
Toy-network을 분석하기 위해 EMME, TransCAD, CUBE의 교통수요 프로그램을 활용하였다. 교통수요 프로그램의 통행배정결과를 산출하기 위한 통행 배정 종료조건은 다음과 같다.
이후 1994년에는 Jayakrishnan et al. 등에 의하여 현재 CUBE에 적용 되는 Gradient Projection(GP) algorithm형태로 개선되었다.
먼저, EMME를 이용한 분석 결과 총 반복연산 횟수 2,000번에 대하여 링크기반 알고리즘(Frank wolfe algorithm)은 10-4 수준의 Relative-Gap을 추정하였으며, 경로 기반 알고리즘(Path Based Algorithm)은 10-6 수준의 Relative-Gap을 추정하였다. 링크기반 알고리즘에서는 2000번 연산을 통하여 Relative Gap 10-4 까지 수렴하였다.
이용자 균형원리는 1952년 Wardrop에 의해 최초 제안된 이후, 4년 뒤 Beckmann(1956)에 의해 수학적모형으로 구성되었다. 이후 Beckmann의 모형을 풀기위한 효율적 해법은 Leblanc(1973)에 의해 제시되었으며, Leblanc은 이때 1956년 Frank & Wolfe가 최초로 제안한 볼록결합(convex combination) 알고리즘을 적용하였다.
통행배정에서는 전량 통행배정기법, 용량제약 통행배정기법, 확률선택모형을 이용한 통행배정기법, 이용자균형(User Equilibrium) 통행배정기법이 있다. 이중에서 주로 이용자균형(User Equilibrium)이 주로 사용되고 있으며, 본 연구에서도 이용자균형 통행 배정기법을 기준으로 분석 하였다.
이후 Beckmann의 모형을 풀기위한 효율적 해법은 Leblanc(1973)에 의해 제시되었으며, Leblanc은 이때 1956년 Frank & Wolfe가 최초로 제안한 볼록결합(convex combination) 알고리즘을 적용하였다.
성능/효과
CUBE의 사례 분석결과는 PBA가 BCFW, FW보다 월등히 빠른 수렴속도를 나타내는 것으로 분석되었다. 수렴하는데 있어 연산횟수 또한 46회 만에 10-6까지 수렴하는 것을 알 수 있다.
BCFW와 FW 는 10-4 이하에서 연산속도가 현저히 낮아지는 현상이 발생하고 있다. EMME와 TransCAD, CUBE 모두 FWA의 연산속도는 비슷한 것으로 분석되었으며 프로그램에 따라 BCFW, OUE, PBA에 대한 분석을 수행하였고 각각 FWA보다 빠른 속도와 높은 수렴성을 나타내는 것을 알 수 있다.
교통분석 프로그램별로 분석하여 비교한 사례결과는 다음과 같다. EMME의 FWA와 PG(PBA)를 분석해본 결과 PG의 연산속도가 FWA보다 빠르게 나타났다. Relative Gap도 PG(PBA)는 10-6까지 수렴 하였지만, FWA는 10-4까지 수렴하고 있는 것을 알수 있다.
Path-based algorithm과 Origin-based algorithm의 경우 Frank-wolfe algorithm보다 빠른 속도로 Relative Gap이 감소하는 것으로 분석되었다. PBA는 CUBE가 EMME보다 연산횟수와 Relative Gap 측면에서 빠른 것으로 분석되었으며, OBA의 경우 빠르게 연산이 종료되는 것을 알 수 있다.
프로그램별로 차이는 있지만, Relative Gap을 만족시키기 위한 연산횟수는 약 3,800번 정도로 추정할 수 있다. Path-based algorithm과 Origin-based algorithm의 경우 Frank-wolfe algorithm보다 빠른 속도로 Relative Gap이 감소하는 것으로 분석되었다. PBA는 CUBE가 EMME보다 연산횟수와 Relative Gap 측면에서 빠른 것으로 분석되었으며, OBA의 경우 빠르게 연산이 종료되는 것을 알 수 있다.
TransCAD의 FWA, BCFW, OUE에 대한 사례를 분석한 결과, 프로그램 연산속도는 OUE, BCFW, FW순으로 빠르다. OUE는 10-6까지 가장 먼저 도달 한 것을 알 수 있다.
분석 모형별로 편익분석을 살펴보면, 우선 EMME의 경우, Relative Gap이 10-1~10-6을 살펴보면, 10-4 이후에 편익값이 안정화 되어 가는 것을 알 수 있다. TransCAD의 경우에도 FWA는 10-4 까지 도출되며, 수렴성이 높아질수록 편익값이 안정화 되었으며, Cube의 경우에도 FWA는 Relative Gap이 10-4 까지 분석하였고 편익이 약 92백만원/일로 산정되고 있다. PBA의 경우에는 10-10까지 분석되었고 편익이 92백만원/일로 분석되어서 FWA와 유사한 것으로 나타났다.
경로기반(Path-Based) 통행배정기법은 EMME, TransCAD, Cube 프로그램에서 지원하고 있으며, EMME와 Cube를 이용한 분석결과 링크기반 (Link-Based) 통행배정기법에 비해 목적함수값과 수렴지표(Relative Gap 등)가 빠르게 감소하는 것으로 나타났다. 다만, 각 프로그램별로는 조금씩 차이가 존재하였는데, EMME의 경우 수렴정도를 나타내는 Relative Gap 값이 10-6 , Cube에서는 10-10까지 도출될 수 있지만, 일정수준 이하에서는 투입된 시간 대비 결과의 차이는 크지 않는 것으로 분석되었다.
또한 동일한 Toy-network에 통행량이 다를 때의 통행배정 결과를 비교해 보았다. 교통수요 분석 프로그램에 관계없이 동일한 목적함수 값을 도출해보면, V/C와 교통수요 분석 프로그램에 관계없이 분석 결과는 동일한 것을 확인 할 수 있었다. 수학적 계산 방법의 한계로 인하여 보다 복잡한 구조에 대한 분석을 수행하지 못하였다.
Toy-network의 V/C별 목적함수 값은 교통수요 분석 프로그램에 관계없이 동일한 수준을 나타내는 것으로 분석할 수 있다. 교통혼잡상황을 가정하여 토이네트워크 시나리오 설정에 따른 교통수요 분석 프로그램의 분석결과, FWA의 분석결과와 수학적 계산결과와의 차이는 PBA, OBA의 분석 결과 차이보다 조금 더 큰 값이 계산 되는 것으로 분석되었다. 또한 동일한 Toy-network에 통행량이 다를 때의 통행배정 결과를 비교해 보았다.
출발지 기반 알고리즘은 경로기반 알고리즘 보다 목적함수 값에 빨리 수렴하고, 연산시간은 더 오래 걸리는 것을 확인할 수 있었다. 구체적으로, TransCAD의 분석결과 FWA는 10-4 , OBA는 10-10까지 수렴하였다. 목적함수 값은 OBA가 FWA보다더 작은 값을 찾았으며, OBA가 FWA보다 빠른 속도로 연산을 종료하는 것으로 분석되었다.
다만, 다른 기법들에 비해 보다 많은 시간이 소요되며 모형의 수렴정도가 일정 수준, 예를 들어 Relative Gap값이 10-4까지 도출된 이후부터는 아무리 많은 시간이 걸리더라도 결과값의 개선효과가 극히 미미한 것으로 나타나고 있다. 그럼에도 불구하고 수렴정도를 나타내는 지표 중 Relative Gap값이 10-4에 도달하는 경우 다른 결과와 유사한 결과를 도출하는 것으로 검토되어, EMME, TranCAD, Cube의 3개 프로그램에서 링크기반(Link-Based) 통행배정 기법을 이용할 경우 최소한 Relative Gap값이 10-4까지는 낮아지도록 하는 것이 바람직할 것으로 판단된다.
경로기반(Path-Based) 통행배정기법은 EMME, TransCAD, Cube 프로그램에서 지원하고 있으며, EMME와 Cube를 이용한 분석결과 링크기반 (Link-Based) 통행배정기법에 비해 목적함수값과 수렴지표(Relative Gap 등)가 빠르게 감소하는 것으로 나타났다. 다만, 각 프로그램별로는 조금씩 차이가 존재하였는데, EMME의 경우 수렴정도를 나타내는 Relative Gap 값이 10-6 , Cube에서는 10-10까지 도출될 수 있지만, 일정수준 이하에서는 투입된 시간 대비 결과의 차이는 크지 않는 것으로 분석되었다. 따라서 다른 결과값들과 비교하였을 때 경로기반 (Path-Based) 통행배정기법을 적용할 경우 EMME의 경우에는 최소한 Relative Gap값이 10-5 , CUBE의 경우에는 10-7까지는 낮아지도록 하는 것이 바람직할 것으로 판단된다.
그 외의 다른 종료조건은 동일하게 설정하였으며 최대 연산횟수를 10,000회를 설정하였다. 단, CUBE는 3,000회로 설정하였는데, 분석 프로그램에 대한 모의 Iteration 수행결과 3,000회의 분석시간이 오래 걸리고 Relative GAP의 변화도 없는 것으로 판단하여 3,000회 이상의 분석은 의미가 없는 것으로 판단하였다.
다만, 각 프로그램별로는 조금씩 차이가 존재하였는데, EMME의 경우 수렴정도를 나타내는 Relative Gap 값이 10-6 , Cube에서는 10-10까지 도출될 수 있지만, 일정수준 이하에서는 투입된 시간 대비 결과의 차이는 크지 않는 것으로 분석되었다. 따라서 다른 결과값들과 비교하였을 때 경로기반 (Path-Based) 통행배정기법을 적용할 경우 EMME의 경우에는 최소한 Relative Gap값이 10-5 , CUBE의 경우에는 10-7까지는 낮아지도록 하는 것이 바람직할 것으로 판단된다.
반복연산 횟수가 증가함에 따라 출발지 기반 알고리즘(Origin Based Algorithm)은 링크기반 알고리즘(Frank Wolfe algorithm)보다 빠르게 Relative-Gap이 감소하였지만 더 이상 Relative-Gap 이 감소하지 않았다. 링크기반 알고리즘은 출발지 기반 알고리즘보다 연산속도는 느렸지만 10-4까지 Relative-Gap이 감소하는 것을 확인할 수 있었다. 출발지 기반 알고리즘은 경로기반 알고리즘 보다 목적함수 값에 빨리 수렴하고, 연산시간은 더 오래 걸리는 것을 확인할 수 있었다.
마지막으로 CUBE의 경우 분석결과, 링크기반 알고리즘에서는 10-4 수준의 Relative-Gap으로 수렴하였으나, 경로기반 알고리즘에서는 10-10 수준의 Relative-Gap까지 분석되었지만, 수렴하지 못하는 결과를 나타내었다. CUBE에서는 목적함수가 제시되지 않고 총통행비용, 총 통행거리, 총 통행시간에 대한 분석결과를 제시한다.
구체적으로, TransCAD의 분석결과 FWA는 10-4 , OBA는 10-10까지 수렴하였다. 목적함수 값은 OBA가 FWA보다더 작은 값을 찾았으며, OBA가 FWA보다 빠른 속도로 연산을 종료하는 것으로 분석되었다.
“Computational Experience on Advanced Algorithms for User Equilibrium Traffic Assignment Problem and Its Convergence Error”의 연구에서 주요 통행배정 알고리즘별 결과 값을 보여준다. 바르셀로나와 위니팩 에 대한 통행배정 결과 FWA의 수렴속도가 가장 낮은 것으로 분석되었으며 TAPAS의 수렴속도가 가장 빠른 것을 확인할 수 있었다. 다른 ASD, DSD(Disaggregate Simplicial Decomposition), Bargera’s algorithm 들은 유사한 연산속도를 나타내는 것으로 분석되었다.
Relative Gap별 편익분석결과를 살펴보면, 최종수렴결과와 달리 알고리즘별로 편익값이 상이한 것을 알 수 있다. 분석 모형별로 편익분석을 살펴보면, 우선 EMME의 경우, Relative Gap이 10-1~10-6을 살펴보면, 10-4 이후에 편익값이 안정화 되어 가는 것을 알 수 있다. TransCAD의 경우에도 FWA는 10-4 까지 도출되며, 수렴성이 높아질수록 편익값이 안정화 되었으며, Cube의 경우에도 FWA는 Relative Gap이 10-4 까지 분석하였고 편익이 약 92백만원/일로 산정되고 있다.
04%로 차이가 미미한 것을 알 수 있다. 분석결과 교통량이 증가함에 따라 통행배정량의 차이가 증가하는 것으로 분석되었으며, PBA가 OBA 보다 교통량의 분산이 높게 나타났다.
본 연구에서는 개별링크기반(Link-Based)의 통행 배정 기법 외에 새로운 통행배정기법(경로기반, 출발지기반)을 대상으로 통행배정알고리즘의 수렴성을 검토하고 적정수준의 종료기준을 제시하고자 하였다. 분석결과 수렴성이 어느 정도 확보된 이후부터는 비교적 안정된 결과를 도출하는 것으로 나타났다.
수렴지표(Relative Gap 등) 는 가장 낮게 나타나고 있어 기존 기법들에 비해 빠르다고 볼 수 있으나, 최종적인 통행배정 결과는큰 차이가 없는 것으로 나타났다. 앞서 분석한 결과들과 비교하였을 때 출발지기반(Origin-Based) 통행 배정 기법의 경우 최소한 Relative Gap 값이 10-6수준까지 낮아지도록 하는 것이 바람직할 것으로 판단된다.
01%(10-4 )정도 되어야 한다는 결론 도출하였으며 Relative Gap이 10-11에 도달했을 때의 결과 값을 참값으로 가정하였다. 이러한 연구를 통해 FWA에 비해 OBA을 적용했을 때 수렴 속도가 훨씬 빠르다는 점을 보여주었다. “The Equilibrium Assignment”, Bloy(2004)는 남아프리카 공화국 가우탱 지역을 대상으로 32개 서로 다른 사업에 대하여 Relative Gap 의 변화에 따른 B/C의 변화를 분석하여 교통량 추정시보다 편익 추정시에 더 많은 통행배정 횟수가 필요하며, 경제성 평가를 위한 Relative Gap은 0.
링크기반 알고리즘은 출발지 기반 알고리즘보다 연산속도는 느렸지만 10-4까지 Relative-Gap이 감소하는 것을 확인할 수 있었다. 출발지 기반 알고리즘은 경로기반 알고리즘 보다 목적함수 값에 빨리 수렴하고, 연산시간은 더 오래 걸리는 것을 확인할 수 있었다. 구체적으로, TransCAD의 분석결과 FWA는 10-4 , OBA는 10-10까지 수렴하였다.
출발지기반(Origin-Based) 통행배정 기법은 TransCAD프로그램에서 지원하고 있으며, 링크기반 (Link-Based) 및 경로기반(Path-Based) 기법 보다 목적함수값과 수렴지표(Relative Gap 등)가 빠르게 감소하는 것으로 나타났다. 수렴지표(Relative Gap 등) 는 가장 낮게 나타나고 있어 기존 기법들에 비해 빠르다고 볼 수 있으나, 최종적인 통행배정 결과는큰 차이가 없는 것으로 나타났다.
Relative GAP의 수렴 속도나 수렴 범위에 대하여 큰 차이를 나타내지 않았다. 하지만 PBA 분석 결과는 CUBE의 PBA와 다른 수렴성을 나타내었으며, Trans CAD의 OBA와도 상이한 특성을 나타내었다. EMME의 PBA는 FWA의 수렴성이 증가한 정도로 분석할 수 있다.
후속연구
본 연구에서 실무적으로 사용되는 여러 교통분석 프로그램과 통행배정 기법들을 달리하여 분석한결과 국가교통DB와 같은 교통망을 이용하여 분석할 경우 통행배정 모형이 충분히 수렴되지 않은 상태에서는 어떠한 결과값을 적용하는가에 따라 차이가 클 수 있어 조사결과의 안정성에 관한 문제가 제기될 가능성이 존재한다. 따라서 비용/편익 분석을 수행하는데 있어서 각 연구진들은 이에 대한 인식과 더불어 주의를 기울일 필요가 있으며, 본 연구에서 분석된 결과를 참조하여 각 분석프로그램 및 통행배정 기법별로 적정한 수준의 수렴성 확보 및 안정된 결과값을 도출하여야 할 것이다.
구체적으로 먼저 통행배정모형의 이론적 검토 및 수렴성판단과 관련된 기존연구를 검토하고, Toy-Network 및 실제 대규모 네트워크를 기반으로 사례분석을 실시하여, 통행배정 알고리즘별 알고리즘 종료조건에 따른 교통량, 편익의 수렴성을 검토하였다. 마지막으로 타당성조사 단계에서 안정적인 결과를 도출하기 위한 주요 기준에 대해서 제언하고자 한다.
본 연구에서 실무적으로 사용되는 여러 교통분석 프로그램과 통행배정 기법들을 달리하여 분석한결과 국가교통DB와 같은 교통망을 이용하여 분석할 경우 통행배정 모형이 충분히 수렴되지 않은 상태에서는 어떠한 결과값을 적용하는가에 따라 차이가 클 수 있어 조사결과의 안정성에 관한 문제가 제기될 가능성이 존재한다. 따라서 비용/편익 분석을 수행하는데 있어서 각 연구진들은 이에 대한 인식과 더불어 주의를 기울일 필요가 있으며, 본 연구에서 분석된 결과를 참조하여 각 분석프로그램 및 통행배정 기법별로 적정한 수준의 수렴성 확보 및 안정된 결과값을 도출하여야 할 것이다.
질의응답
핵심어
질문
논문에서 추출한 답변
기존의 FWA 기반의 이용자 균형 통행배정 모형에 관한 논란이 제기되기 시작한 이유는?
그러나 교통수요 분석을 위해 사용하는 기초자료의 크기(Size)와 정밀도(Detail)가 향상됨에 따라 기존에 사용하던 FWA 기반의 이용자 균형 통행배정 모형의 정확도 및 한계에 관한 논란이 제기되기 시작하였다. 따라서 기존 방법론 대비 정밀성을 보다 향상시키고자 새로운 알고리즘(Origin-Based, Path-Based)들이 지속적으로 개발되어 왔으며, 최근 들어 이들 알고리즘이 본격적으로 교통수요분석을 위한 상용프로그램에 탑재되기 시작하고 있다.
통행경로를 선정하는 과정에서 Link 기반, Path 기반, 출발지 기반 알고리즘의 특징은?
일반적으로 통행경로를 선정하는 과정에서 Link 를 기반으로 탐색하는 Link 기반 알고리즘(대표적 으로 FWA)과 Path 기반으로 탐색하는 경로 기반 알고리즘(Path-Based Algorithm), 그리고 Path의 중첩 되는 구간을 제외하고 비교하는 출발지 기반 알고 리즘(Origin-Based Algorithm)으로 구분하여 분류할수 있다. Link 기반 알고리즘 (FWA)은 연산과정에서 적은 메모리를 필요로 하고 최적해에 도달하는 과정에서의 안정성(stability)을 확보하지만, 반복연산에 의해 일정수준 이상에서 연산효율이 점차 떨어지는 단점을 보이며, 경로기반 알고리즘(Path-Bas ed Algorithm: PBA)은 최적해에 도달하기 위한 연산 속도가 빠르지만, 많은 메모리를 필요로 하여 다수의 경로 및 노드로 구성되는 대규모 네트워크에 적용이 쉽지 않다. 또한 출발지기반 알고리즘 (OriginBased Algorithm : OBA)은 가장 적은 메모리를 필요로 하며 연산에 필요한 시간이 가장 작은 장점이 있으나, Local optimum을 사용하여 최적해에 도달하기 때문에 불안정성(unstability)을 가지며 수렴성 측면에서 문제점이 존재한다고 알려져 있다.
도로부문 타당성조사에서 경제성 분석을 위해 어떤 분석 모형을 사용해오고 있나요?
도로부문 타당성조사에서는 사업의 경제성 분석을 위하여 교통수요 분석 모형을 사용해오고 있으며, 현재 대부분의 경우 4단계 모형을 적용하고 있다. 4단계 모형 중 마지막 단계로서 도로부문 사업의 교통수요 추정에 있어 링크 교통량을 결정하는 중요한 역할을 하는 통행배정 단계에서는 Frank-Wolfe Algorithm(이하 FWA)을 기반으로 한 이용자 균형(User Equilibrium) 모형이 그동안 대표적으로 사용되어 왔다.
참고문헌 (25)
Beckmann, M.J., McGuire,C.B., and C.B.Winston, Studies in the Economics of Transportation. Yale University Press, Connecticut, 1956.
LeBlanc, L.J., Mathematical Programming Algorithms for Large Scale Network Equilibrium and Network Design Problems. PhD thesis, Northwestern Univ, Evanston, Illinois, USA. 1973
Fukushima, M., "On the Convergence of a Class of Outer Approximation Algorithms for Convex Programs," Journal of Computational and Applied Mathematics, vol. 10, pp.147-156, 1984.
Weintraub, A., and C. Ortiz. Accelerating "Convergence of the Frank-Wolfe Algorithm," Transportation Research Part B: Methodological, vol. 19, pp.113-122, 1985.
Hendrickson, C. T., and Janson, B. N., "Expert Systems and Pavement Management," Presented at 2nd North America Conference on Managing Pavements, Toronto, Ontario, USA. 1987.
Arezki., Y. and D. Van Vliet., "A Full Analytical Implementation of the PARTAN/Frank-Wolfe Algorithm for Equilibrium Assignment," Transportation Science, vol. 24, pp.58-62, 1990.
Dafermos, S. C., Traffic Assignment and Resource Allocation in Transportation Networks, PhD thesis, Operations Research, Johns Hopkins University, Baltimore, USA, 1968.
Jayakrishnan, R., Tsai, Wei T., Prashker, Joseph N., and Rajadhyaksha, Subodh. A Faster Path-Based Algorithm for Traffic Assignment. Working Paper, University of California Transportation Center, 1994
Bar-Gera H., Origin-based Algorithms for Transportation Network Modeling. PhD thesis, University of Illinois at Chicago, USA, 1999.
Robert B. Dial., "A Path-Based User-Equilibrium Traffic Assignment Algorithm That Obviates Path Storage and Enumeration," Transportation Research Part B : Methodological, vol. 40, pp.917-936. 2006.
Hearn, D.W., Lawphongpanich, S., and J.A. Ventura. Computation Mathematical Programming : Restricted Simplicial Decomposition : Computation and Extensions. Springer Berlin Heidelberg, USA, 1987.
Larsson, T., M. Patriksson, and C. Rydergren. Network Optimization : Applications of Simplicial Decomposition with Nonlinear Column Generation to Nonlinear Network Flows. Springer Berlin Heidelberg, Sweden, 1997.
Daneva, M., and P. O. Lindberg. "A Conjugate Direction Frank-Wolfe Method with Applications to the Traffic Assignment," Operations Research Proceedings, Springer Berlin Heidelberg, Sweden, 2002.
Larsson, T., and M. Patriksson., "Simplicial Decomposition with Disaggregated Representation for the Traffic Assignment Problem," Transportation Science, vol. 26, pp.4-17, 1992.
Bar-Gera H., and A. Luzon., "Differences among Route Flow Solutions for the User-Equilibrium Traffic Assignment Problem," Journal of Transportation Engineering, vol. 133, pp.232-239, 2007.
Zhang, H. M., Nie, Y., and Z. Qian, "Estimating Time-Dependent Freeway Origin-Destination Demands with Different Data Coverage: Sensitivity Analysis," Transportation Research Record: Journal of the Transportation Research Board, Vol. 2047, Transportation Research Board of the National Academies, Washington, D.C., pp.91-99, 2008.
Inoue, S., and Maruyama. T., "Computational Experience on Advanced Algorithms for User Equilibrium Traffic Assignment Problem and Its Convergence Error". at 8th International Conference on Traffic and Transportation Studies, Changsha, China, 2012.
Florian, M., and S. He., Changing Assignment Al gorithms : The Price of Better Convertgence(2009), from http://teachamerica.com/APP09/APP09S14Florian/player.html
Caliper Mapping Software, New Empirical Study of Alternative Traffic Equilibrium Algorithms(2010), from http://www.caliper.com/press/what_transcad_users_should_know_about_traffic_assignment.pdf,
Zhong, Z., and M. Matthew., What TransCAD Users Should Know about New Static Traffic Assignment Methods(2010), from https://www.google.co.kr/url?sat&rctj&q&esrcs&sourceweb&cd2&ved0CCMQFjAB&urlhttp%3A%2F%2F.
Boyce, D., Ralevic-Dekic, B., and H. Bar-Gera., "Convergence of Traffic Assignments: How Much is Enough?," Journal of Transportation Engineering, vol. 130, pp.49-55, 2004.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.