Ⅰ. 서 론

통행배정 알고리즘은 분석 단위가 링크 또는 경로인지에 따라 링크기반 알고리즘과 경로기반 알고리즘으 로 구분된다(Jung and Chang, 2014). 링크기반 알고리즘은 링크 정보만을 이용해 링크 통행량을 계산하여 계 산적으로 효율적이지만 경로의 특성을 고려하기 어렵다. 경로기반 알고리즘(Cascetta et al., 1996;Yen, 1971; Azevedoet et al., 1993)은 여러 링크가 연결된 경로 정보를 이용한다. 분석 구간 내의 경로를 열거 (enumeration)하는 과정이 선행되어야 한다. 대규모 교통망에서는 무수히 많은 경로가 존재하므로 모든 경로 를 열거하는 것은 많은 시간과 비용이 요구된다.

Dial의 통행배정 알고리즘(Dial, 1971)은 대표적인 링크기반 알고리즘이다. 경로 열거 문제가 나타나지 않 고 대규모 교통망에서 효율적이다. 하지만 경로 특성을 간과하는 단점도 있다. 예컨대 신호교차로의 회전지 체 및 금지(Turn Penalty & Prohibition)를 구현하기 어렵다. 특히 링크기반의 Dial 알고리즘은 U-turn 또는 P-turn과 같이 동일노드를 복수로 방문하는 순환통행(cyclic flow)을 근본적으로 해석하지 못하는 한계가 존재 한다(Bell, 1995;Akamatsu, 1996;Huang and Bell, 1998;Wong, 1999). 또한 Dial 알고리즘의 효율적 경로 (efficient paths) 정의는 다소 엄격한 기준으로 네트워크를 축소하여 비합리적 결과가 도출되기도 한다 (Akamatsu, 1996).

이 연구는 기존의 Dial 알고리즘에 교차로의 회전지체 및 금지로 인해 나타나는 순환통행을 구현하고, 비 합리적 통행배정 문제를 완화하는 덩굴망기반의 Dial 알고리즘을 제시한다. 이를 위해 우선 Ⅱ장은 Dial 알고 리즘을 고찰하고 알고리즘의 한계를 정리한다. Ⅲ장에서는 Dial 알고리즘의 효율적 경로 개념을 단일 링크에 서 두 개의 연결된 링크의 방향으로 확장한 효율적 방향 개념을 도입하고 덩굴망기반(Vine-Based) 알고리즘 을 제안한다. 이어서 Ⅳ장에서는 사례연구를 통해서 덩굴망기반 Dial 알고리즘으로 순환통행 행태를 구현하 고, 비합리적 통행을 완화할 수 있음을 보인다. 마지막 Ⅴ장은 연구 내용을 요약하고 향후 연구과제를 정리 한다.

Ⅱ. Dial’s Algorithm

1. Dial 알고리즘

Dial 알고리즘(Dial, 1971)은 로짓 유형의 확률적 통행배정 알고리즘으로서 링크기반 해법으로 가장 널리 활용되고 있다. Dial 알고리즘은 교통망에서 이용되지 않을 것으로 판단되는 링크를 효과적으로 제거하기 위 해서, 특히 순환통행을 방지하기 위해서 효율적 경로 개념을 도입하였다. 효율적 경로란 ‘출발지에서 멀어지 고 도착지로 가까워지는 링크’, 즉 π^ri ≤ π^rj , π^is ≥ π^js 조건을 만족하는 링크 집합을 의미한다. 여기서 i와 j는 링크를 구성하는 기종점 노드를 의미한다. 또한 π^ri와 π^is는 각각 출발지 r에서 노드 i까지 최소 통행비 용, 노드 i에서 도착지 s까지의 최소 통행비용을 의미한다.

Dial 알고리즘은 크게 세 단계를 거쳐 출발지 r과 도착지 s간 통행량을 부하한다.

[단계1] 링크 가능성(Likelyhood) 계산

우선 출발지 r에서 모든 노드 i까지 최소 통행비용 π^ri와 모든 노드 i에서 도착지 s까지의 최소 통행비용 π^is를 계산한다. 또한 두 노드 i, j를 잇는 링크 (i, j)의 가능성 L_ij를 계산한다. c(ij)는 링크 (i, j)의 통행비용 을 의미한다.

L i j = { e θ ( π r j − π r i − c ( i j ) ) if ( π r i ≤ π r j , π i s ≥ π j s ) 0 otherwise

[단계2] 링크 가중치(Weight) 계산

출발지 r에서 시작하여 출발지에서 가까운 노드 i부터 w (ij) 를 계산한다.

w i j = { L i j if i = r L i j ∑ ( m i ) w m i o t h e r w i s e

여기서 ( m i ) ∈ Γ i −로서 Γ i −는 노드 i가 도착노드인 링크집합을 의미한다.

[단계3] 링크 통행량(Volume) 계산

도착지 s에서 시작하여 출발지에서 먼 노드 i부터 링크 통행량 x_ij를 계산한다. 여기서 x_rs는 출발지 r과 도착지 s간의 통행량을 의미한다.

x i j = { q r s w i j ∑ ( m i ) w m j if j = s [ ∑ ( j m ) x j m ] w i j ∑ ( m j ) w m j o t h e r w i s e

여기서 ( j m ) ∈ Γ i +, 로서 Γ i +는 i노드가 시작노드인 링크집합을 의미한다.

2. Dial 알고리즘과 순환통행

순환통행이란 어느 노드를 2회 이상 방문하는 경로로 이동하는 것으로서 도시가로망의 신호교차로에서 흔히 나타난다. <Fig. 1>은 순환통행이 나타날 수 있는 예시 네트워크이다. 출발지와 도착지는 각각 ①과 ⑤ 이며 교차지점 ③에서 회전 ②-③-⑤의 회전페널티가 100이다. 각 노드 i의 출발지부터의 통행비용 π^ri과 도 착지까지의 통행비용 π^is는 <Table 1>과 같다. ① (=r)부터 ⑤ (=s )의 최적경로는 ①-②-③-④-③-⑤이다. 이 경로는 ③을 2번 방문하는 즉, ③-④-③을 U턴하는 경로이다.

Dial 알고리즘은 <Fig. 1>에서 나타날 수 있는 순환통행을 근본적으로 차단하는 알고리즘 구조를 갖는다. 효율적 링크의 정의 π^ri ≤ π^rj , π^is ≥ π^js 를 만족하는 링크만으로 네트워크를 축소하는 과정에서 순환경로가 제거되기 때문이다. 즉, <Fig. 1>의 링크 ③-④와 ④-③이 제거된다. 따라서 노드 ③에서 회전 ②-③-⑤에 높은 페널티가 존재함에도 불구하고 Dial 알고리즘은 모든 통행을 ①-②-③-⑤의 경로에 배정하는 불합리한 결과 를 도출한다. <Fig. 2>

3. 효율적 경로 정의로 인한 비합리적 통행배정 결과

Dial 알고리즘의 효율적 경로 정의는 엄격한 기준으로 네트워크를 축소하여 비합리적인 통행배정 결과를 도출할 수 있다. 예컨대 총 통행비용이 상대적으로 적은 경로가 선택대안 집합에서 제외되거나, 미미한 통행 비용 차이로 통행배정이 되지 않을 수 있다. Akmatsu(1996)의 네트워크 <Fig. 3>이 대표적인 예시로서, 링크 ⑤-⑥, ⑥-⑤가 통행비용 1만큼의 차이로 효율적 링크에서 제외되고, 이로 인해 교통량이 ⓡ-①-②-③-④-⑤- ⓢ 경로에만 배정되는 문제점이 나타난다. Akmatsu(1996)는 이 문제를 해결하기 위해 Markov의 연산과정을 무한대로 진행하여 순환통행을 강제로 구현하는 방안을 제시하였다. 그러나 이 연산기법은 대규모 네트워크 에서 효율적으로 구동될 수 없다는 한계를 내포하고 있다. 그밖에 효율적 경로의 정의를 수정하거나 없애는 방식에 관한 논의(Bell, 1995;Akamatsu, 1996;Huang and Bell, 1998;Wong, 1999;Leurent, 1997;Si et al, 2010;Van Vliet, 1981)도 진행되었다.

Ⅲ. 덩굴망기반 Dial 알고리즘 개발

이 연구에서는 두 개의 링크, 즉 세 개의 노드를 동시에 고려하여 덩굴망 연산을 할 수 있는 Dial 알고리즘을 개발한다. 기존의 Dial 알고리즘은 단일 링크를 분석단위로 하지만, 이 연구에서 제안하는 알고리즘은 두 개의 링크를 동시에 고려한다. 이를 위해 우선 기존의 ‘효율적 경로’ 정의를 ‘효율적 방향’이라는 새로운 개념으로 확장한다. 효율적 경로는 한 개의 링크를 구성하는 두 개의 노드 정보로 정의되지만, 효율적 방향은 두 개의 연결된 링크, 즉 세 개의 연결된 노드 정보로 정의된다. 알고리즘은 효율적 방향 정의를 반영하여 수정한다.

효율적 방향은 ‘두 링크 사이의 회전 지체를 반영하여 출발지에서 멀어지고 도착지에서 가까워지는 방향’, 즉 π^ra ≤ π^rb , π^as ≥ π^bs로 정의한다. 여기서 a와 b는 <Fig. 4>에서 나타나듯이 인접한 두 링크이고, π^ra와 π^as는 각각 출발지 r에서 a까지의 전방 최소 통행비용, 도착지 s에서 a까지의 후방 최소 통행비용을 의미한다. 여기서 최소 통행비용은 링크와 링크사이의 회전지체 d_ab를 반영한 링크기반 표지확정기법(Lee, 2004)으로 산출하였다. <Table 1>

덩굴망기반 알고리즘은 다음과 같이 3단계로 구성된다.

[단계1] 방향 가능성(Directional Likelyhood) 계산

출발지 r에서 모든 링크 a까지의 최소 통행비용 π^ra와 모든 링크 b에서 도착지 s까지 최소 통행비용 π^bs 를 계산한다. 또한 효율적 방향 정의 조건을 고려하여 회전가능성 L_ab를 계산한다. c_b는 링크 b의 통행비용, d_ab는 링크 a, b의 회전비용을 의미한다.

L a b = { e θ ( π r b − π r a − d a b − c b ) if ( π r a ≤ π r b , π a s ≥ π b s ) 0 o t h e r w i s e

[단계2] 회전 가중치(Directional Weight) 계산

출발지 r에서 시작하여 출발지에서 가까운 회전된 링크부터 링크 가중치 w_ab를 계산한다.

w a b = { L a b if a ( i , j ) , i = r L a b ∑ ( c a ) w c a o t h e r w i s e

여기서 ( c a ) ∈ Γ a −로서 Γ a −는 링크 a가 도착링크인 링크집합을 의미한다.

[단계3] 회전 통행량(Directional Volume) 계산

도착지 s에서 시작하여 출발지에서 먼 회전된 링크의 시작노드부터 회전 통행량 υ_ab를 계산한다.

υ a b = { q r s w a b ∑ ( c a ) w c a if b ( i j ) , j = s [ ∑ ( b c ) υ b c ] w a b ∑ ( c b ) υ c b o t h e r w i s e

여기서 ( b c ) ∈ Γ b −, 로서 Γ b −는 링크 b가 시작링크인 링크집합을 의미한다.

이때 링크 a의 통행량 x_a는 다음과 같다.

x a = ∑ b ∈ T a + υ a b

Ⅳ. 사례연구

1. 순환경로 구현

이 연구에서 제안한 덩굴망기반 알고리즘을 <Fig. 1>의 네트워크에 대하여 적용하였다. 파라미터 θ = 1.0, 기종점 교통량 q_rs = 1000(r=①, s =⑤)으로 설정하였다. 효율적 방향은 ①-②-③, ②-③-④, ②-③-⑤, ③-④-③, ④-③-⑤로 나타난다. 다만 방향 ②-③-⑤는 회전비용이 100으로 높아서 방향 가능성 L 이 미미한 값으로 도출되 었다. 방향 ①-④-③은 효율적 방향 정의를 충족하지 않아서 통행배정 대상에서 제외되었다. 따라서 기종점 통행 은 모두 경로 ①-②-③-④-③-⑤에 배정되었다. ③-④-③의 U턴 순환통행이 구현되는 것을 확인할 수 있다.

한편 방향 ②-③-⑤의 회전비용을 조정하면 노드 ③에서 순환통행과 비순환통행을 동시에 구현할 수 있다. 예컨대 <Fig. 1>의 네트워크에서 방향 ②-③-⑤의 회전비용을 100에서 5로 조정하고 알고리즘을 분석하면 그 결과는 <Fig. 6>와 <Table 2>와 같다. 효율적 방향은 <Fig. 5>와 같이 5개 방향이 포함된다. 방향 ②-③-⑤의 방향 가능성이 L=0.0498로 회전비용 조정 전에 비해 높아지고, 비순환경로 ①-②-③-⑤와 순환경로 ①-②-③-④-③-⑤에 각각 47.4통행과 952.6통행이 배정된다. 순환통행량과 비순환통행량의 비율은 회전비용으로 조절할 수 있다.

2. 비합리적 통행배정 문제 완화

이 연구의 덩굴망기반 Dial 알고리즘은 기존 Dial 알고리즘의 통행배정 경로가 효율적 경로 정의에 의해 엄격하게 제한되는 문제를 완화한다. 예컨대 기존 알고리즘으로는 비합리적 통행배정 결과가 나타나는 Akmatsu(1996)의 네트워크 <Fig. 3>에 덩굴망기반 Dial 알고리즘을 적용하면 <Fig. 7>의 결과를 도출한다. 기 존 Dial 알고리즘은 효율적 경로의 정의에 의해 링크 ⑤-⑥, ⑥-⑤가 통행배정 대상에서 제외되지만 덩굴망기 반 알고리즘은 방향 ①-⑥-⑤를 합리적 방향에 포함하고 6.7 통행을 배정한다.

Ⅴ. 결 론

Dial 알고리즘의 링크기반의 연산은 도시교통망에서 나타나는 순환통행에 대한 고려가 근본적으로 불가능 한 구조적 한계를 지니고 있다. 또한, 효율적 경로의 정의는 엄격한 기준으로 분석 네트워크를 축소함으로써 비합리적 결과를 도출할 수도 있다. 이 연구는 두 개의 링크를 동시에 고려하는 효율적 방향 개념을 도입하 고 덩굴망기반 Dial 알고리즘을 제안하였다. 또한 사례분석을 통해서 덩굴망기반 Dial 알고리즘이 순환통행, 순환 및 비순환 혼재 통행을 구현할 수 있으며 비합리적 경로배정 문제를 완화하는 것을 보였다. 향후 덩굴 망기반 Dial 알고리즘을 도시교통망, 대중교통망, 보행네트워크 등 대규모 교통망에 확장 및 적용하는 후속 연구가 필요하다.