Journal Search Engine

to

Search Advanced Search Adode Reader(link)
View PDF Download PDF Export Citation Korean Bibliography PMC Previewer
The Journal of The Korea Institute of Intelligent Transport Systems Vol.14 No.1 pp.31-45
DOI : https://doi.org/10.12815/kits.2015.14.1.031

Analysis of Convergence Level and Exit Criteria on Traffic Assignment Algorithms

Joo-young Kim*, Jae-young Kim**, Sang-jun Park**, Seung-jae Lee***

† 본 연구는 2013년 서울시립대학교 교내학술연구비에 의하여 수행하였습니다.

Corresponding author : : Seungjae Lee(University of Seoul) , sjlee@uos.ac.kr
November 20, 2014 │ January 29, 2015 │ February 3, 2015

Abstract

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.

Convergence Level , Frank-Wolfe Algorithm , Origi~-Based Algorithm , Path-Based Algorithm , Traffic Assignment

통행배정모형의 수렴성 판단 및 종료기준 설정

김 주 영*, 김 재 영**, 박 상 준**, 이 승 재***
*주저자 : 서울시립대학교 도시과학연구원 융합도시연구센터 연구교수(Unversity of Seoul)
**공저자 : 한국개발연구원 공공투자관리센터 전문위원(KDI, PIMAC)
***교신저자 : 서울시립대학교 교통공학과 교수(KDI, PIMAC)

초록

기존의 링크기반의 Frank-Wolfe 통행배정 기법은 구현의 용이성과 결과의 안정성 등으로 인해 널리 사용되어 왔으 나, 교통분석을 위해 사용하는 기초자료의 크기와 정밀도가 향상됨에 따라 수렴성에 대한 논란이 제기되었다. 본 연구 에서는 개별링크기반의 통행배정 기법 외에 경로기반, 출발지기반 알고리즘을 이용한 분석결과의 안정성, 적용가능성에 대한 검토를 수행하였다. 분석결과 각각의 상용프로그램 및 통행배정기법별로 결과의 차이가 일부 존재하지만 수렴성 이 어느 정도 확보된 이후부터는 안정된 결과를 도출하는 것으로 나타났다. 특히 대규모 교통망에서 통행배정 모형이 충분히 수렴되지 않은 상태에서는 수렴성 및 종료기준에 따라 분석결과의 안정성에 관한 문제가 제기될 가능성이 존재 하였다. 따라서 실무적으로 적정한 수준의 수렴성 확보 및 안정된 결과 값을 도출하고자 하는 노력이 요구된다.

수렴성 , 링크 기반 알고리즘 , 출발지 기반 알고리즘 , 경로 기반 알고리즘 , 통행배정

    University of Seoul

    Ⅰ서 론

    도로부문 타당성조사에서는 사업의 경제성 분석 을 위하여 교통수요 분석 모형을 사용해오고 있으 며, 현재 대부분의 경우 4단계 모형을 적용하고 있 다. 4단계 모형 중 마지막 단계로서 도로부문 사업 의 교통수요 추정에 있어 링크 교통량을 결정하는 중요한 역할을 하는 통행배정 단계에서는 Frank-Wolfe Algorithm(이하 FWA)을 기반으로 한 이용자 균형(User Equilibrium) 모형이 그동안 대표 적으로 사용되어 왔다. 이용자 균형통행배정 기법 은 Wardrop’s(1952)의 통행경로 선택원리에 기초를 두고 있다. 이것은 Beakman(1956)에 의하여 수학적 모형으로 구현되었으며, Frank 와 Wolfe에 의하여 볼록결합 알고리즘(Convex combination Algorithm)으 로 모형화 되었다.

    그러나 교통수요 분석을 위해 사용하는 기초자 료의 크기(Size)와 정밀도(Detail)가 향상됨에 따라 기존에 사용하던 FWA 기반의 이용자 균형 통행배 정 모형의 정확도 및 한계에 관한 논란이 제기되기 시작하였다. 따라서 기존 방법론 대비 정밀성을 보 다 향상시키고자 새로운 알고리즘(Origin-Based, Path-Based)들이 지속적으로 개발되어 왔으며, 최근 들어 이들 알고리즘이 본격적으로 교통수요분석을 위한 상용프로그램에 탑재되기 시작하고 있다. 따 라서 다양한 통행배정 기법의 발달과 분석프로그램 의 개발, 동시에 이에 대한 신뢰성 판단 및 검증에 대한 필요성이 대두되었다.

    일반적으로 통행경로를 선정하는 과정에서 Link 를 기반으로 탐색하는 Link 기반 알고리즘(대표적 으로 FWA)과 Path 기반으로 탐색하는 경로 기반 알고리즘(Path-Based Algorithm), 그리고 Path의 중첩 되는 구간을 제외하고 비교하는 출발지 기반 알고 리즘(Origin-Based Algorithm)으로 구분하여 분류할 수 있다. Link 기반 알고리즘 (FWA)은 연산과정에 서 적은 메모리를 필요로 하고 최적해에 도달하는 과정에서의 안정성(stability)을 확보하지만, 반복연 산에 의해 일정수준 이상에서 연산효율이 점차 떨 어지는 단점을 보이며, 경로기반 알고리즘(Path-Bas ed Algorithm: PBA)은 최적해에 도달하기 위한 연산 속도가 빠르지만, 많은 메모리를 필요로 하여 다수 의 경로 및 노드로 구성되는 대규모 네트워크에 적 용이 쉽지 않다. 또한 출발지기반 알고리즘 (Origin- Based Algorithm : OBA)은 가장 적은 메모리를 필 요로 하며 연산에 필요한 시간이 가장 작은 장점이 있으나, Local optimum을 사용하여 최적해에 도달하 기 때문에 불안정성(unstability)을 가지며 수렴성 측 면에서 문제점이 존재한다고 알려져 있다.

    따라서 본 연구에서는 우선 통행배정 단계에서 사용되어 온 기존의 FWA 기반모형과 새롭게 개발 되고 있는 모형간의 이론적 특징 및 장·단점을 비 교하고, 국내·외에서 널리 사용하고 있는 상용프로 그램(EMME, TransCAD, CUBE)의 적용 알고리즘에 따른 수렴성 검토를 수행하였다. 구체적으로 수렴 성 수행 결과는 가상의 교통망(Toy-Network)와 대규 모 네트워크에서 비교된다. 가상의 교통망 (Toy-Network)에서, 알고리즘들이 계산된 최적해에 수렴할 수 있는지 확인 할 수 있다. 이 논문은 link 기반 알고리즘과 path 기반 알고리즘 또는 출발지 기반 알고리즘(Origin-Based Algorithm)의 기법별을 통하여 안정한 유일한 해를 찾을 수 있을지 확인할 수 있다. 대규모 네트워크에서는, 각 프로그램 및 통행배정 기법별로 가상의 사업시행 전후에 따른 주요 통행배정 결과값이 합리적인 가를 확인 할 수 있다. 최근 일부 연구들은 Frank-Wolfe algorithm의 통행배정 기법이 최적해 근처에서 수렴성이 저하되 는 문제를 갖고 있다고 발표하였다. 따라서 본 연구 는 교통량 및 편익산출을 위한 통행배정모형의 수 렴성을 판단하고 종료기준에 대한 연구를 수행하고 자 한다. 구체적으로 먼저 통행배정모형의 이론적 검토 및 수렴성판단과 관련된 기존연구를 검토하 고, Toy-Network 및 실제 대규모 네트워크를 기반으 로 사례분석을 실시하여, 통행배정 알고리즘별 알 고리즘 종료조건에 따른 교통량, 편익의 수렴성을 검토하였다. 마지막으로 타당성조사 단계에서 안정 적인 결과를 도출하기 위한 주요 기준에 대해서 제 언하고자 한다.

    Ⅱ이론적 검토

    1.통행배정의 기본원리

    통행배정은 전통적인 4단계 교통수요분석 모형 의 최종단계에서 수행되며, 주어진 기·종점간 통행 량을 교통망에 배정하는 과정이라고 할 수 있다.

    통행배정의 기본원리는 교통수요와 공급의 관계 에 기초를 두고 있으며, 교통량 변화에 따른 서비스 수준의 변화를 나타내는 Link 저항함수와 서비스 수준의 변화에 따른 통행량 변화를 나타내는 수요 함수의 관계로 표현 할 수 있다.

    통행배정에서는 전량 통행배정기법, 용량제약 통 행배정기법, 확률선택모형을 이용한 통행배정기법, 이용자균형(User Equilibrium) 통행배정기법이 있다. 이중에서 주로 이용자균형(User Equilibrium)이 주로 사용되고 있으며, 본 연구에서도 이용자균형 통행 배정기법을 기준으로 분석 하였다.

    통행배정 모형은 크게 각 기·종점간에 시간 등의 비용이 최소가 되는 경로를 찾는 부분과 통행량을 교통망에 부하(Loading)하는 부분으로 나누어진다. 본 연구의 초점이 되는 통행량을 교통망에 부하하 는 방법은 우선적으로 시간적 요소의 고려에 따라 동적(Dynamic) 모형과 정적(Static) 모형으로 구분된 다. 다음으로는 용량과 확률요소의 고려에 따라 크 게 네 가지로 구분되며, 그 동안 확률적 요소를 고 려하지 않되 용량제약은 고려하는 Wardrop의 이용 자 균형원리에 기반 한 모형이 가장 널리 적용되어 왔다.Table 1, 2

    이용자균형 통행배정은 Wardrop(1952)의 첫 번째 통행경로 선택원리에 기초를 두고 있으며, ‘통행자 는 자신의 통행시간을 최소화하는 통행경로를 선택 한다’는 가정에서 출발한다. 이러한 가정에서 통행 자의 통행경로 선택원리는 Wardrop(1952)에 의해서 두 가지 가능성이 제시되었다. 첫 번째 통행경로 선 택원리는 ‘통행자는 다른 통행자의 통행경로 선택 과는 상관없이 자신의 통행시간을 최소화하는 통행 경로를 선택 한다’는 것이고, 두 번째 통행경로 선 택원리는 ‘모든 통행자들은 총 통행시간 혹은 개별 통행자들의 평균 통행시간이 최소화되도록 통행자 들은 통행경로를 선택 한다’고 정의하였다.

    2.이용자 균형 원리 구현을 위한 알고리즘 비교

    이용자 균형원리는 1952년 Wardrop에 의해 최초 제안된 이후, 4년 뒤 Beckmann(1956)에 의해 수학적 모형으로 구성되었다. 이후 Beckmann의 모형을 풀 기위한 효율적 해법은 Leblanc(1973)에 의해 제시 되었으며, Leblanc은 이때 1956년 Frank & Wolfe가 최초로 제안한 볼록결합(convex combination) 알고리 즘을 적용하였다.

    FWA에 기반한 이용자균형 통행배정모형은 수렴 성이 최적해 근처에서 저하되는 문제를 갖고 있어 이를 해결하고자 Fukushima(1984), Weintraub(1985), Lupi(1986), Janson(1987), Arezki(1990) 등에 의해 여 러 연구들이 진행되어 왔다. 그리고 수렴성의 근본 적인 향상을 위해 또 다른 알고리즘을 개발하고자 하는 시도 또한 활발하게 이루어져왔다. 대표적인 것으로는 Dafermos(1968), Jayakrishnan et al(1994)의 경로기반(Path-Based) 알고리즘과 Bar-Gera(1999), Dial(2006) 등의 출발지기반(Origin-Based) 알고리즘 등이 있다.

    이에 본 연구에서는 알고리즘의 유형을 크게 Link-Based Algorithm(Frank-Wolfe Algorithm), Path-Based Algorithm, Origin-Based Algorithm의 3가지로 구분하 여 접근하고자 하였다.

    3.통행배정 기법별 연구 및 구현 현황

    링크기반 알고리즘의 경우 1956년 Frank and Wolfe에 의하여 처음 제안되었으며, 이후 1982년 Powell and Sheffi에 의하여 개선된 형태인 Improved Frank-Wolfe algorithms을 제안하였다. 이외에도 1985년 Hearn 등에 의한 Restricted Simplicial Decomposition( RSD) algorithm 과 1997년 Larsson and Patriksson에 의한 Nonlinear Simplicial Decomposition( NSD)의 형태로 발전되었다. 최근에는 2003 년 Daneva et al.에 의하여 Conjugate FW algorithms (CFW)과 Bi-conjugate FW algorithms(BFW)가 제안되 었으며, 현재 CUBE 및 TransCAD에서 적용하여 활 용되고 있다.

    경로기반 알고리즘은 1968년 Dafemos에 의하여 제안되었으며, 1992년 Larsson and Patriksson에 의하 여 Disaggregate Simplicial Decomposition(DSD) algorithm 형태로 개선되었다. 이후 1994년에는 Jayakrishnan et al. 등에 의하여 현재 CUBE에 적용 되는 Gradient Projection(GP) algorithm형태로 개선되 었다.

    마지막으로 출발지기반 알고리즘은 가장 최근인 1999년 Bar-Gera에 의해 제안된 방법으로 같은 해 Dial에 의하여 발표된 Algorithm B와 거의 같다. 이 후 2007년 Bar-Gera and Luzon에 의해 Traffic Assignment by Paired Alternative Segments(TAPAS)로 개선되었으며 2008년 Nie et al.에 의해 Improved Origin-based Algorithm로 개선되었다.

    현재 상용화된 교통분석 프로그램 에서 적용하 고 있는 이용자균형 알고리즘은 다음과 같다. EMME는 링크기반, 경로기반 통행배정 기법을 적 용하고 있다. CUBE는 링크기반모형과 경로기반 통 행배정 기법을 적용하고 있으며, 링크기반 통행배 정기법으로는 FWA, CFWA, BCFWA, 경로기반 통 행배정 기법으로는 GPA를 적용하고 있다. TransCAD에서는 링크기반 통행배정 기법의 FWA, CFWA, BCFWA를 적용하고 있으며, 링크기반 통행 배정 기법과 출발지기반 통행배정 기법을 적용할 수 있다. 이때, 출발지기반 통행배정 기법은 Algorithm B를 적용하고 있다.

    Ⅲ기존 연구 검토 및 연구방법론 설정

    1.기존 연구 검토

    통행배정기법간의 결과를 비교한 최근 연구로는 Shin-ichi Inoue et al.(2012)에 의해서 수행되었다. “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 들은 유사한 연산속도를 나타내는 것으로 분석되었다.

    교통분석 프로그램별로 분석하여 비교한 사례결 과는 다음과 같다. EMME의 FWA와 PG(PBA)를 분 석해본 결과 PG의 연산속도가 FWA보다 빠르게 나 타났다. Relative Gap도 PG(PBA)는 10-6까지 수렴 하였지만, FWA는 10-4까지 수렴하고 있는 것을 알 수 있다.

    TransCAD의 FWA, BCFW, OUE에 대한 사례를 분석한 결과, 프로그램 연산속도는 OUE, BCFW, FW순으로 빠르다. OUE는 10-6까지 가장 먼저 도 달 한 것을 알 수 있다. BCFW는 10-5까지 가장 먼 저 도달하였지만 10-6까지 수렴하는데 오랜 시간이 소요되었다.

    CUBE의 사례 분석결과는 PBA가 BCFW, FW보 다 월등히 빠른 수렴속도를 나타내는 것으로 분석 되었다. 수렴하는데 있어 연산횟수 또한 46회 만에 10-6까지 수렴하는 것을 알 수 있다. BCFW와 FW 는 10-4 이하에서 연산속도가 현저히 낮아지는 현 상이 발생하고 있다. EMME와 TransCAD, CUBE 모 두 FWA의 연산속도는 비슷한 것으로 분석되었으 며 프로그램에 따라 BCFW, OUE, PBA에 대한 분 석을 수행하였고 각각 FWA보다 빠른 속도와 높은 수렴성을 나타내는 것을 알 수 있다.

    수렴성 검토에 관한 연구에서는 “Convergence of Traffic Assignment”, Boyce et al.(2004)는 미국 뉴저 지 지역에 두 개의 램프 건설에 따른 효과를 파악 하기 위해 EMME/2를 이용해 분석한 결과 안정된 링크 교통량을 얻기 위해서는 Relative Gap = 0.01%(10-4)정도 되어야 한다는 결론 도출하였으며 Relative Gap이 10-11에 도달했을 때의 결과 값을 참값으로 가정하였다. 이러한 연구를 통해 FWA에 비해 OBA을 적용했을 때 수렴 속도가 훨씬 빠르다 는 점을 보여주었다. “The Equilibrium Assignment”, Bloy(2004)는 남아프리카 공화국 가우탱 지역을 대 상으로 32개 서로 다른 사업에 대하여 Relative Gap 의 변화에 따른 B/C의 변화를 분석하여 교통량 추 정시보다 편익 추정시에 더 많은 통행배정 횟수가 필요하며, 경제성 평가를 위한 Relative Gap은 0.01%(10-4) 정도는 되어야 한다는 결론을 도출하 였다. “Traffic Assignment Convergence and its Effects on Selecting Network Improvements”, Blaschuk(2009) 은 캐나다 캘거리 지역에 위치한 2개의 도로 확장 사업을 대상으로 사업 시행시와 미시행시의 총 주 행시간(VHT)의 변화를 분석하여 Bloy(2004)와 비슷 한 결과를 도출하였으며, 교통량 변화를 파악하거 나 총주행시간의 변화를 파악하고자 할 때 모두 Relative Gap이 0.01%(10-4) 이하로 되어야 한다는 결론을 도출하였다. 또한 “Convergence of the Sydney strategic traffic model”, Wilson(2006)은 호주 시드니 지역의 사례를 대상으로 통행배정 횟수에 따른 도로이용자의 비용의 변화 분석 하여 통행배 정 횟수에 따라 통행시간 절감편익 변화가 크다고 제시하였다. 상기와 같은 연구들은 Relative Gap이 최소한 0.01%(10-4)가 되어야한다는 점을 도출할 수 있고, 특히나 편익을 산정할 경우에는 교통량만 추정할 때보다 더 정교해야하므로 0.01%(10-4) 이 하로 되어야하는 것을 파악할 수 있다.

    2.연구방법론 설정

    본 연구에서는 기존에 주로 사용하여왔던 개별 링크기반(Link-Based)의 통행배정 기법 외에 새로운 통행배정기법(경로기반, 출발지기반)을 이용한 분석 결과의 안정성, 적용가능성 등에 대한 검토를 수행 하고자 한다. 구체적으로는 먼저 개별 알고리즘의 교통량 수렴정도의 차이를 비교하기 위해서 통행배 정 결과의 참값을 직접 계산할 수 있는 가상의 toy-network 구축하고, 실제 계산상의 값과 국내외에 서 널리 사용되고 있는 상용프로그램인 EMME, TransCAD, Cube의 적용 알고리즘별 산출값과 비교 하여 개별 알고리즘이 정확성, 수렴성에 대해서 검 토하하였다.

    다음으로 대규모 네트워크에 각 상용프로그램의 적용 알고리즘별로 수렴성, 배정된 교통량, 수렴정 도에 따른 편익 변화 분석을 수행한다. 이를 통해서 각 프로그램의 적용 알고리즘별로 수렴성에 대한 검토를 수행하고, 안정화단계에 이르는 통행배정 종료조건을 제시하고자 한다.

    Ⅳ사례분석

    1.Toy-network 분석

    1)분석범위 설정

    교통 분석 프로그램별 알고리즘에 따른 수렴정 도 분석에 앞서 본 연구에서는 Toy-network를 설정 하여 각 알고리즘별 안정성 및 기능을 파악하려 한 다. 이를 위해 총 16개 링크로 구성된 toy-network을 구성하고 평균 V/C에 따른 통행량(O/D)를 구성하여 각 링크별 통행량과 통행시간, 목적함수 값을 실제 계산상의 값과 교통분석 프로그램의 알고리즘 별 값과 비교하였다.

    토이 네트워크 구성 내역은 순방향(101-104-107- 110-113)에 대하여 각각의 링크를 A, B, C, D, E, F, G, H 라고 정의하고, 역방향(113-110-107-104-101)에 대한 각각의 링크를 A-, B-, C-, D-, E-, F-, G-, H- 라고 정의하였다.

    링크 속성의 경우 각 링크는 동일한 거리와 용량 및 파라미터를 포함하고 있으며 각 링크별 자유통 행속도의 차이를 두어 링크의 속성값을 설정하였다.

    토이네트워크 분석에서는 평균 V/C에 따라 시나 리오를 적용하고자, O/D 통행량을 각 존pair별로 10,000, 30,000, 50,000통행으로 구성하였으며 내부 통행량을 제외한 존별 통행량은 동일한 것으로 설 정하여 분석을 수행하였다.

    2)토이네트워크 통행량 및 목적해 도출

    본 분석의 경우 평균 V/C에 따라 시나리오를 선 정하였으며 이는 비혼잡 상황과 혼잡상황, 극심한 혼잡상황으로 구분할 수 있다. 따라서 본 분석에서 는 V/C에 따라 시나리오를 설정하였으며, 구체적으 로 시나리오 1의 경우 V/C 0.4, 시나리오 2의 경우 V/C 1.0, 시나리오 3의 경우 V/C 2.0로 설정하였다.

    시나리오에 따라 각 링크별 통행량 및 통행시간, 목적함수 값을 계산하여 보면 다음과 같은 결과를 보이며, 시나리오별 총통행시간과 목적함수 값이 상이함을 보이는 것으로 나타났다.

    3)교통수요 프로그램별 simulation solution

    Toy-network을 분석하기 위해 EMME, TransCAD, CUBE의 교통수요 프로그램을 활용하였다. 교통수 요 프로그램의 통행배정결과를 산출하기 위한 통행 배정 종료조건은 다음과 같다.

    · Relative Gap : -10-5

    · iteration : 10,000회

    단, CUBE의 경우 사용자가 최대 Iteration구현을 999회까지 할 수 있도록 설정되어 있어 999회를 종 료조건으로 설정하였다.

    Toy-network를 교통수요 프로그램으로 통행배정 종료조건에 따라 통행배정을 수행한 결과를 분석해 보았다. 교통수요 분석 프로그램별 목적함수 값은 다르지 않은 것으로 판단 할 수 있다. 하지만 V/C 에 따른 목적함수 값을 비교할 경우, V/C=0.4일 때, 교통수요 분석 프로그램별 목적함수 값의 차이가 상대적으로 큰 것으로 분석 되었다.

    Toy-network의 V/C별 목적함수 값은 교통수요 분 석 프로그램에 관계없이 동일한 수준을 나타내는 것으로 분석할 수 있다. 교통혼잡상황을 가정하여 토이네트워크 시나리오 설정에 따른 교통수요 분석 프로그램의 분석결과, FWA의 분석결과와 수학적 계산결과와의 차이는 PBA, OBA의 분석 결과 차이 보다 조금 더 큰 값이 계산 되는 것으로 분석되었 다. 또한 동일한 Toy-network에 통행량이 다를 때의 통행배정 결과를 비교해 보았다. 교통수요 분석 프 로그램에 관계없이 동일한 목적함수 값을 도출해보 면, V/C와 교통수요 분석 프로그램에 관계없이 분 석 결과는 동일한 것을 확인 할 수 있었다. 수학적 계산 방법의 한계로 인하여 보다 복잡한 구조에 대 한 분석을 수행하지 못하였다. 하지만, 본 Toy-network 분석을 통하여 교통수요분석 프로그램의 분석 결과가 서로 다르지 않은 점을 확인할 수 있는 분 석 결과이다.

    2.대규모 네트워크 분석

    1)분석의 개요

    대규모 네트워크에서는 한국의 Korea regional O/D/Network를 이용하여 분석을 수행하였다. Korea regional O/D/Network은 250개의 존, 27,654개의 node, 64,378link를 포함하는 대규모 네트워크로써, 한국 지역간 통행을 분석할 수 있는 데이터 이다.

    분석사례는 다음과 같이 설정되었다. 시나리오 1 의 경우 경부고속도로 [남이JCT~비룡 JCT]의 32.1km구간의 고속도로를 확장하는 사업으로 대규 모 사업에 해당하고, 시나리오 2의 경우 영동고속 도로[서창~안산]간 14.9km를 확장하는 중소규모 사 업으로 시나리오를 설정하였다.

    먼저 분석을 위해서 사업미시행시 각 교통수요 분석 프로그램별 통행배정 결과가 필요하다. 따라 서 모든 프로그램에 대하여 경험적으로 FWA는 10-4의 Relative Gap을 종료조건으로 설정하였고, PBA, OBA는 EMME는 10-6, 나머지 프로그램은 10-10을 종료조건으로 설정하였다. 그 외의 다른 종료조건은 동일하게 설정하였으며 최대 연산횟수 를 10,000회를 설정하였다. 단, CUBE는 3,000회로 설정하였는데, 분석 프로그램에 대한 모의 Iteration 수행결과 3,000회의 분석시간이 오래 걸리고 Relative GAP의 변화도 없는 것으로 판단하여 3,000 회 이상의 분석은 의미가 없는 것으로 판단하였다.

    2)미시행시 분석결과

    전국 지역간 자료에 대한 분석 결과를 살펴보면, 반복연산횟수에 따른 Relative-Gap의 변화는 다음과 같다. Frank-wolfe algorithm의 경우, TransCAD를 기 준으로 3,783의 연산을 15분 동안 수행 후 Relative Gap을 만족하고 종료하였다. 프로그램별로 차이는 있지만, Relative Gap을 만족시키기 위한 연산횟수 는 약 3,800번 정도로 추정할 수 있다. Path-based algorithm과 Origin-based algorithm의 경우 Frank-wolfe algorithm보다 빠른 속도로 Relative Gap 이 감소하는 것으로 분석되었다. PBA는 CUBE가 EMME보다 연산횟수와 Relative Gap 측면에서 빠른 것으로 분석되었으며, OBA의 경우 빠르게 연산이 종료되는 것을 알 수 있다.Fig .4

    먼저, EMME를 이용한 분석 결과 총 반복연산 횟수 2,000번에 대하여 링크기반 알고리즘(Frank wolfe algorithm)은 10-4 수준의 Relative-Gap을 추정 하였으며, 경로 기반 알고리즘(Path Based Algorithm)은 10-6 수준의 Relative-Gap을 추정하였 다. 링크기반 알고리즘에서는 2000번 연산을 통하 여 Relative Gap 10-4 까지 수렴하였다. 경로 기반 알고리즘에서는 59회에 Relative Gap이 10-4 를 만 족하였으며, 198회에 10-5 를 만족하였다. 하지만 10-6은 2000번 이상의 연산이 필요로 하였다. 연산 초반에는 Relative Gap이 감소하는 속도가 느려지는 현상을 관찰 할 수 있었다. EMME는 FWA의 분석 결과는 다른 교통수요 분석 프로그램과 유사한 결 과를 나타내었다. Relative GAP의 수렴 속도나 수렴 범위에 대하여 큰 차이를 나타내지 않았다. 하지만 PBA 분석 결과는 CUBE의 PBA와 다른 수렴성을 나타내었으며, Trans CAD의 OBA와도 상이한 특성 을 나타내었다. EMME의 PBA는 FWA의 수렴성이 증가한 정도로 분석할 수 있다. FWA Relative GAP 의 경우, 10-4 근처에서 수렴속도가 감소하는 결과 가 10-7 정도 수렴수준에서 동일한 결과가 나타나 는 것으로 분석되었다.Fig .5

    둘째로, TransCAD는 반복연산횟수를 10,000번으 로 설정하였으며 Relative-Gap = 0을 종료조건으로 적용하였다. 반복연산 횟수가 증가함에 따라 출발 지 기반 알고리즘(Origin Based Algorithm)은 링크기 반 알고리즘(Frank Wolfe algorithm)보다 빠르게 Relative-Gap이 감소하였지만 더 이상 Relative-Gap 이 감소하지 않았다. 링크기반 알고리즘은 출발지 기반 알고리즘보다 연산속도는 느렸지만 10-4까지 Relative-Gap이 감소하는 것을 확인할 수 있었다. 출 발지 기반 알고리즘은 경로기반 알고리즘 보다 목 적함수 값에 빨리 수렴하고, 연산시간은 더 오래 걸 리는 것을 확인할 수 있었다. 구체적으로, TransCAD의 분석결과 FWA는 10-4, OBA는 10-10 까지 수렴하였다. 목적함수 값은 OBA가 FWA보다 더 작은 값을 찾았으며, OBA가 FWA보다 빠른 속 도로 연산을 종료하는 것으로 분석되었다.Fig .6,7

    마지막으로 CUBE의 경우 분석결과, 링크기반 알 고리즘에서는 10-4 수준의 Relative-Gap으로 수렴하 였으나, 경로기반 알고리즘에서는 10-10 수준의 Relative-Gap까지 분석되었지만, 수렴하지 못하는 결 과를 나타내었다. CUBE에서는 목적함수가 제시되 지 않고 총통행비용, 총 통행거리, 총 통행시간에 대한 분석결과를 제시한다. 총 통행거리는 반복연 산 초기에 링크기반알고리즘의 변화율이 크게 나타 났으며 200번 이후 경로기반알고리즘의 총 통행거 리와 비슷한 값을 추정하였다. 총 통행시간도 비슷 한 결과를 나타내었다.Table .7Fig .8

    3)교통량 분석 결과

    먼저 일부 특정링크를 중심으로 미시행과 시행 시의 차이를 검토하였다. FWA의 경우, 프로그램별 로 미시행과 시행시의 교통량 차이는 약 0.2%~2.8% 로 유사한 것으로 나타났으며, PBA와 OBA의 경우 에도 교통량 차이는 유사하며, 0.6%~7%의 차이를 보이고 있다.

    다음으로, 각 교통수요 분석프로그램의 미시행 시나리오에 대하여 각 링크의 평균 교통량을 추정 하고, 프로그램별 편차를 추정해 봄으로서, 교통수 요분석 프로그램에 따른 추정 교통량의 차이를 비 교하였다. 각각의 프로그램의 편차는 FWA의 경우, -2.13%~2.13%로 유사하며 PBA 혹은 OBA의 경우에 도 -0.74%~0.04%로 차이가 미미한 것을 알 수 있다. 분석결과 교통량이 증가함에 따라 통행배정량의 차 이가 증가하는 것으로 분석되었으며, PBA가 OBA 보다 교통량의 분산이 높게 나타났다.

    4)편익 분석 결과

    프로그램별, 알고리즘별로 시나리오1, 시나리오2 의 편익결과에 대해서 비교하였다. 시나리오1의 경 우, 92백만원/일～97백만원/일로 산출되어서 약 4% 의 차이를 보이고 있어서 유사하게 산정되는 것을 알 수 있다. 시나리오2에 있어서도 편익이 134백만 원/일～138백만원/일로 약 3%의 차이를 보이고 있 어서 시나리오1과 마찬가지로 별 차이가 없는 것을 알수 있다.

    Relative Gap별 편익분석결과를 살펴보면, 최종수 렴결과와 달리 알고리즘별로 편익값이 상이한 것을 알 수 있다. 분석 모형별로 편익분석을 살펴보면, 우선 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와 유사한 것으로 나타났다.Table .7

    3.활용방안

    각각의 통행배정기법 및 프로그램별 분석 결과 및 활용상에서 고려하여야 할 사항들을 좀 더 살펴 보면 다음과 같다.

    링크기반(Link-Based) 통행배정 기법은 검토된 4 개의 분석프로그램 모두에서 지원하고 있으며, 다 른 통행배정 기법에 비해 수렴횟수(Iteration Number) 에 따라 목적함수값과 수렴지표(Relative Gap 등)가 서서히 안정적으로 감소하는 현상을 보이고 있다. 다만, 다른 기법들에 비해 보다 많은 시간이 소요되 며 모형의 수렴정도가 일정 수준, 예를 들어 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까지는 낮아지도록 하는 것이 바람직 할 것으로 판단된다.

    출발지기반(Origin-Based) 통행배정 기법은 TransCAD프로그램에서 지원하고 있으며, 링크기반 (Link-Based) 및 경로기반(Path-Based) 기법 보다 목 적함수값과 수렴지표(Relative Gap 등)가 빠르게 감 소하는 것으로 나타났다. 수렴지표(Relative Gap 등) 는 가장 낮게 나타나고 있어 기존 기법들에 비해 빠르다고 볼 수 있으나, 최종적인 통행배정 결과는 큰 차이가 없는 것으로 나타났다. 앞서 분석한 결과 들과 비교하였을 때 출발지기반(Origin-Based) 통행 배정 기법의 경우 최소한 Relative Gap 값이 10-6수 준까지 낮아지도록 하는 것이 바람직할 것으로 판 단된다.

    Ⅴ결 론

    통행배정 모형은 교통여건 변화에 따른 이용자 의 경로선택 행위 변화를 모형에서 구현하기 위해 수요(지역간 통행량)와 공급(도로망)간의 균형점을 이용자 균형원칙이라는 제약조건 하에서 찾아가는 최적화 모형의 하나라 할 수 있다. 따라서 어떠한 프로그램과 통행배정 기법들을 이용하더라도 최적 해에 도달하였을 경우 그 결과값은 근본적으로 같 아야 하나, 모형에서 고려하고자 하는 현실세계가 복잡해질수록 최적해에 도달한 결과를 얻기 어렵다 는 한계를 갖고 있다. 따라서 적정한 수준에서 통행 배정 결과의 안정적인 결과를 도출하고자 하는 노 력이 요구된다.

    본 연구에서는 개별링크기반(Link-Based)의 통행 배정 기법 외에 새로운 통행배정기법(경로기반, 출 발지기반)을 대상으로 통행배정알고리즘의 수렴성 을 검토하고 적정수준의 종료기준을 제시하고자 하 였다. 분석결과 수렴성이 어느 정도 확보된 이후부 터는 비교적 안정된 결과를 도출하는 것으로 나타 났다.

    본 연구에서 실무적으로 사용되는 여러 교통분 석 프로그램과 통행배정 기법들을 달리하여 분석한 결과 국가교통DB와 같은 교통망을 이용하여 분석 할 경우 통행배정 모형이 충분히 수렴되지 않은 상태에서는 어떠한 결과값을 적용하는가에 따라 차 이가 클 수 있어 조사결과의 안정성에 관한 문제가 제기될 가능성이 존재한다. 따라서 비용/편익 분석 을 수행하는데 있어서 각 연구진들은 이에 대한 인 식과 더불어 주의를 기울일 필요가 있으며, 본 연구 에서 분석된 결과를 참조하여 각 분석프로그램 및 통행배정 기법별로 적정한 수준의 수렴성 확보 및 안정된 결과값을 도출하여야 할 것이다.

    Figure

    ITS-14-31_F1.gif

    Toy-network

    ITS-14-31_F2.gif

    Change of Relative Gap in Toy-networks

    ITS-14-31_F3.gif

    Large scale network

    ITS-14-31_F4.gif

    Change of relative gap according to number of iteration (summary)

    ITS-14-31_F5.gif

    The result of analysis(EMME)

    ITS-14-31_F6.gif

    The result of analysis(TransCAD)

    ITS-14-31_F7.gif

    The result of analysis(CUBE)

    ITS-14-31_F8.gif

    Traffic assignment result comparison by algorithms

    Table

    Link attribute value

    Result of Objective value in Toy network(V/C=0.4)

    Objective function values comparison followed by assignments in softwares

    Analysis result

    The result of benefit analysis according to Relative Gap

    Reference

    1. Beckmann MJ , McGuire CB , Winston CB (1956) Studies in the Economics of Transportation , Yale University Press, Connecticut,
    2. LeBlanc LJ (1973) Mathematical Programming Algorithms for Large Scale Network Equilibrium and Network Design Problems , PhD thesis, Northwestern Univ, Evanston, Illinois, USA,
    3. Fukushima M (1984) “On the Convergence of a Class of Outer Approximation Algorithms for Convex Programs” , Journal of Computational and Applied Mathematics, Vol. 10 ; pp.147-156
    4. Weintraub A , Ortiz C (1985) Accelerating “Convergence of the Frank-Wolfe Algorithm” , Transportation Research Part B: Methodological, Vol.19 ; pp.113-122
    5. Lupi M (1986) “Convergence of the Frank—Wolfe Algorithm in Transportation Networks” , Civil Engineering Systems, Vol.3 ; pp.7-15
    6. Hendrickson C T , Janson B N (1987) “Expert Systems and Pavement Management” ,
    7. Arezki. Y , Van Vliet. D (1990) “A Full Analytical Implementation of the PARTAN/Frank–Wolfe Algorithm for Equilibrium Assignment” , Transportation Science, Vol.24 ; pp.58-62
    8. Dafermos S C (1968) Traffic Assignment and Resource Allocation in Transportation Networks , PhD thesis, Operations Research, Johns Hopkins University, Baltimore, USA,
    9. Jayakrishnan R , Tsai Wei T , Prashker Joseph N , Rajadhyaksha Subodh (1994) A Faster Path-Based Algorithm for Traffic Assignment , Working Paper, University of California Transportation Center,
    10. Bar-Gera H (1999) Origin-based Algorithms for Transportation Network Modeling , PhD thesis, University of Illinois at Chicago, USA,
    11. Robert B Dial (2006) “A Path-Based User-Equilibrium Traffic Assignment Algorithm That Obviates Path Storage and Enumeration” , Transportation Research Part B : Methodological, Vol.40 ; pp.917-936
    12. Powll WB , Sheffi Y (1982) “The Convergence of Equilibrium Algorithms with Predetermined Step” , Transportation Science, Vol.16 ; pp.45-55
    13. Hearn DW , Lawphongpanich S , Ventura JA (1987) Computation Mathematical Programming : Restricted Simplicial Decomposition : Computation and Extensions, Springer,
    14. Larsson T , Patriksson M , Rydergren C (1997) Network Optimization : Applications of Simplicial Decomposition with Nonlinear Column Generation to Nonlinear Network Flows, Springer,
    15. Daneva M , Lindberg P O (2002) “A Conjugate Direction Frank-Wolfe Method with Applications to the Traffic Assignment” , Operations Research Proceedings, Springer ,
    16. Larsson T , Patriksson M (1992) “Simplicial Decomposition with Disaggregated Representation for the Traffic Assignment Problem” , Transportation Science, Vol.26 ; pp.4-17
    17. Bar-Gera H , Luzon A (2007) “Differences among Route Flow Solutions for the User-Equilibrium raffic Assignment Problem” , Journal of Transportation Engineering, Vol. 133 ; pp.232-239
    18. Zhang H M , Nie Y , Qian Z (2008) “Estimating Time-Dependent Freeway Origin-Destination Demands with Different Data Coverage: Sensitivity Analysis” , Transportation Research Record: Journal of the Transportation Research Board, Transportation Research Board of the National Academies, Vol.2047 ; pp.91-99
    19. Inoue S , Maruyama T (2012) “Computational Experience on Advanced Algorithms for User Equilibrium Traffic Assignment Problem and Its Convergence Error” ,
    20. Florian M , He S (2009) Changing Assignment Al gorithms : The Price of Better Convertgence , from http://www.teachamerica.com/APP09/APP09S14Florian/player.html,
    21. (2010) Caliper Mapping Software, New Empirical Study of Alternative Traffic Equilibrium Algorithms , from http://www.caliper.com/press/what_transcad_ users_should_know_about_traffic_assignment. pdf,
    22. Zhong Z , Matthew M (2010) What TransCAD Users Should Know about New Static Traffic Assignment Methods , from https://www.google.co.kr/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&ved=0CCMQFjAB&url=http%3A%2F%2F,
    23. Boyce D , Ralevic-Dekic B , Bar-Gera H (2004) “Convergence of Traffic Assignments: How Much is Enough?” , Journal of Transportation Engineering, Vol.130 ; pp.49-55
    24. Bloy K (2004) The Equilibrium Assignment – What Is A “Correct” Solution? , from http://www.inro.ca/en/pres_pap/international/ieug04/BloyMexico.pdf,
    25. Wilson B (2006) “Finding the Value in ESD” , Property Australia, Vol.20 ; pp.70-71

    저자소개

    • 김 주 영 (Joo-young Kim)
    • 2014년 2월~ 현 재 : 서울시립대학교 연구교수
    • 2010년 3월~2014년 2월 : 서울시립대학교 공학박사(교통공학)
    • 2008년 3월~2010년 2월 : 서울시립대학교 공학석사(교통공학)
    • trafficplan@naver.com
    • 연락처 : 02) 6490-5661

    • 김 재 영 (Jae-young Kim)
    • 2007년 3월~ 현 재 : 한국개발연구원(KDI) 전문위원
    • 2001년 8월~2007년 2월 : 한국개발연구원(KDI) 연구원, 주임연구원
    • 2004년 3월~2007년 2월 : 서울시립대학교 공학박사(교통공학)
    • 1999년 3월~2001년 2월 : 서울시립대학교 공학석사(교통공학)
    • planner@kdi.re.kr
    • 연락처 : 010-6674-9965

    • 박 상 준 (Sang-jun Park)
    • 2005년 11월~ 현 재 : 한국개발연구원(KDI) 전문위원
    • 2004년 2월 : 한양대학교 박사과정 수료(교통계획)
    • 2004년 1월~2005년 11월 : 경기개발연구원 연구원
    • 2001년 4월~2004년 1월 : 서울시정개발연구원
    • spark@kdi.re.kr
    • 연락처 : 044-550-4735

    • 이 승 재 (Seung-jae Lee)
    • 1998년 10월~ 현 재 : 서울시립대학교 교수(교통공학과)
    • 1996년 10월~1998년 9월 : 서울시립대학교 도시공학과 전임강사
    • 1995년 11월~1996년 9월 : 교통개발연구원 책임연구원
    • 1990년 10월~1995년 4월 : University College London 공학박사(교통공학)
    • 1988년 3월~1990년 2월 : 서울대학교 환경대학원 도시계획학석사
    • sjlee@uos.ac.kr
    • 연락처 : 02) 6490-2823

    Footnote