제1모형(대피시간 최소화 모형)

모형의 목적 : 가장 짧은 시간 내에 유고예상지역의 모든 시민들을 안전지대로 대피 시키는 것

전제 : 대피시간 제한 없음 변수 : 통행시간

사용이론 : 최단경로 탐색법과 통행배분/배정 결합 모형

대피시간을 최소화하기 위해서는 주어진 상황에서 이용 가능한 경로를 통하여 각 방향에 위치한 안전지대로 대피할 수 있는 최단경로 탐색이 선행되어야 한다.

<표 5-8> 최단경로 탐색 알고리즘의 특징

알고리즘 특징

수형망 알고리즘

⋅노드와 연결 링크간의 관계를 이용하여 경로를 구축

⋅경로구축시 고려되는 범위가 좁다는 점에서 단순교통망에서는 효율적

⋅시작노드부터 모든 노드의 최소 경로 산출 가능

⋅계산이 간단하고 빠름

⋅좌회전 , 우회전 , P-Turn, U-Turn 등의 회전지체 및 회전금지를 고려하 지 않음

덩굴망 알고리즘

⋅최소도착비용을 결정해야 하는 노드의 전노드와, 전전노드까지를 검색범 위로 가짐

⋅연산속도가 수형망 알고리즘보다 2배 느림

⋅연속적 회전 및 P-Turn, U-Turn을 반영하지 못함

수정형 덩굴망 알고리즘

⋅특정노드로 유입하는 방향에 따라 노드표지를 별도로 기록

⋅하나의 노드에 필요한 접근로 수만큼의 표지를 가짐

⋅교차로에서 회전유형의 추가적인 절차없이 현실적인 최단경로 탐색

⋅경로 추적시 올바르지 못한 경로를 찾는 경우가 발생

⋅한 노드에 대하여 하나의 최적경로만을 찾기에 차기 대안을 고려할 수 없음

다중표지 수정형 덩굴망

알고리즘

⋅회전정보를 고려하여 정확한 경로탐색

⋅다양한 회전유형 반영

⋅다중표지기법을 이용함으로 최적노선의 대안노선을 찾는 알고리즘 적용 가능

⋅계산량이 커짐 동적 다중표지

덩굴망 알고리즘

⋅시간에 따라 변화하는 교통상황을 반영할 수 있는 시간변수를 추가하여 시간에 대한 동적인 알고리즘임

⋅다중표지 수정형 덩굴망 알고리즘의 특징을 전부 포함

⋅계산량이 다중표지 수정형 덩굴망 알고리즘보다 시간간격수만큼 많아짐 (1) 최단경로 탐색 알고리즘

최단경로 탐색 알고리즘으로 알려진 종류에는 수형망, 덩굴망, 수정된 덩굴망, 다중표지 수정형 덩굴망, 동적 다중표시 덩굴망 알고리즘 등 5가지 유형의 알고 리즘이 존재한다. 각각의 특징과 장단점은 위 <표 5-9>와 같다.

여러 최단경로 알고리즘 가운데, 다중표지 수정형 덩굴망 알고리즘(MILVA : Multi-Labelling Vine Algorithm)은 논문 「도시부 ATIS 적용을 위한 동적 다중 표 지덩굴망 알고리즘의 개발, 박상준, 1998. 12 」에 따르면 Bellman의 최적원리에 의해 회전부담금(회전방향(우회전, 직진, 좌회전)에 따른 상이한 비용)을 포함할 수 있는 현실성 있는 경로를 탐색할 수 있어, 널리 사용되고 있는 알고리즘이다.

본 연구에서도 도로의 침수 및 유실로 인한 네트워크 단절 시 회전제약을 잘 반 영한 현실적인 경로탐색을 위하여 다중표지 수정형 덩굴망 알고리즘을 이용하여 경로탐색을 수행하도록 하였다.

Bellman의 최적원리 :

‘출발노드 r 에서 노드 j까지의 최단경로가 노드 i를 통과하였다면 그 경로상에 서 r에서 i까지의 부분 경로 또한 최단 경로가 된다.’

λ_j^*= m in { λ_i + d_ij }

여기서, ^λj^*= r 에서 출발하여 j까지의 최단 경로 비용 ^λi = r 에서 출발하여 i까지의 최단 경로 비용 ^dij = link (i, j)의 비용

^r= 최초 출발노드 ^d = 최종 도착노드

i = 현재 최단 경로 탐색 대상이 되는 기준 노드(첫번째 노드) ^j = 노드 ⁱ와 하나의 링크로 연결된 노드로써 현재 탐색 대상이 되는

두 번째 노드

다중표지 수정형 덩굴망 알고리즘 프로세스는 회전정보를 고려한 현실적인 최

단경로를 산출하는 알고리즘으로 구체적인 단계는 다음의 과정을 따른다.

Step 1 : 초기화

1) C¹r r= 0 , p¹rr= 0 , pp¹rr= 0

2) C¹r j=t_{r j} , p¹r j=r , pp^1rj= 0 ∀j ( j : r 과 하나의 링크로 직접 연결된 노드)

3) C^gr k= ∞ , p^grk= 0 , pp^grk= 0 ∀k, g ( k : k≠r 그리고 k≠j ) 4) r 을 집합 N 의 목록에 기록하여 둔다.

Step 2 : 집합 N에서 노드 선택 및 제거

1) 집합 N 에서 순서에 따라 노드 i 를 선택하고 노드 i 를 집합 N 의 목록에 서 제거

2) J_i= {j₁,j₂, ⋯ } 의 집합을 구한다. 하지만 이 때, j = p^hr i, ( C^hri

= m in {C¹_ri,C²_ri, ⋯ } )인 경우는 j 를 집합에 포함시키지 않는다. 단 j - i - j 의 U-turn이 허용될 경우에는 j 를 집합에 포함시킨다.

3) 만일 집합 N 에서 선택할 노드가 없으면 (단계 5)로 간다.

Step 3 : 집합 ^Ji에서 노드 선택 및 제거

1) 집합 Ji에서 순서에 따라 노드 j 를 선택하고 집합 Ji의 목록에서 j 를 제거 한다.

2) Kj= {k₁,k₂,⋯|k≠j } 인 집합을 구한다. 단, i - j - i 의 U-turn이 허용되 어 k = i 인 경우에는 i 를 집합 Kj에 포함시킨다. 하지만 U-turn이 허용되 지 않거나 k = p^hrj인 경우에는 k 를 Kj에 포함시키지 않는다.

3) 만일 선택할 j 가 없으면 (Step 1)로 간다.

Step 4 : 집합 K

1) 집합 Kj에서 순서에 따라 k 를 선택한다. 집합 Kⁱ 목록에서 k 를 제거한 다.

2) k 노드에 대한 전노드로써 j 노드가 되는 전노드코드 g 를 찾는다. 만일 j 노드가 전노드로 기록이 되어 있지 않으면 전노드번호가 0으로 나오는 첫 번째 g 를 노드 k 에 대한 노드 j 의 전노드코드로 할당한다.

3) 만일 선택할 노드 k 가 없으면 (Step 2)로 간다.

Step 5 : 선택된 노드 k 까지의 노선비용을 계산하고 노드표지를 수정

1) j 노드의 전노드들 중에 i 노드번호를 전노드로 하는 전노드코드 h 를 찾는 다( i = p^hr j).

2) T^grk=C^h_rj+t_jk+P_ijk를 계산한다. ( j 가 i - j - i U-turn 허용노드인 경 우 : P^ijk=P_iji)

3) 만일 T^grk<C^g_rk이면 C^gr k=T^g_{r k}, p^g_{r k}=j, p p^g_{r k}=i 로 수정한다. 그리고 만일 T^grk< min {C¹_rk,C²_rk,⋯ } 이면 노드 k 와 j 를 각각 집합 N 의 목 록에 추가하도록 한다. 하지만 k 또는 j 가 집합 N 에 이미 있으면 해당되 는 노드는 포함시키지 않는다.

4) 만일 T^grk≥C^g_rk이면, 노드표지를 수정하지 않고, k 와 j 를 N 에 추가하지 않는다. Step 3으로 간다.

Step 6 : 노드표지를 이용하여 최단경로를 역으로 추적

1) C^grd= m in {C¹_rd,C²_rd, ⋯ } 인 전노드코드 g 를 찾아 전노드 k = p^grd 전 전노드 j = p p^grd를 찾는다.

2) j, k , d 를 순서대로 노선노드 집합 R 의 목록에 R = {j,k,d } 와 같이 추가 한다.

3) 노드 k 의 전노드가 j 즉 j = p^gr k인 전노드코드 g 를 찾아 g 에 속한 k 노 드의 전전노드 i = p p^grk를 추적한다.

4) i 노드를 집합 R 목록의 첫 번째 위치로 R = {i,j,k ,⋯ ,d } 와 같이 추가한 다.

5) 만일 i = r 이면 최단경로 추적을 완료한다. 만일 아니면 k = j , j = i 로 놓 고 (단계 5)의 (3)으로 가서 반복한다.

알고리즘에서 사용된 변수의 설명은 다음 표와 같다.

<표 5-9> 다중표지 수정형 덩굴망 알고리즘 변수 설명

C^g_rj 현재까지 계산된 값 중에서 출발지점 r에서 전노드코드 g인 전노드를 거쳐 노 드 j까지 이르는 최소통행비용

P_ijk ^시작노드 i에서 회전노드 j를 거쳐 끝 노드 k에 이르는 차량회전의 회전 벌점 (turn penalty)

P_iji ^노드 i에서의 j - i - j U-turn 벌점(penalty). 만일 i노드가 U-turn 허용노드 인 경우

k 노드 j와 하나의 링크로 연결된 노드로써 현재 탐색 대상이 되는 세 번째 노드 g ^{임의의 노드} k에 도달하는 방향을 나타내기 위한 코드로써 노드 k에 하나의

링크로 연결된 노드의 전노드 코드 g_. g ∈ G_k= {1,2,⋯ }

J_i ^노드 i와 하나의 링크로 직접 연결된 노드로써 노드 i에서 노드 탐색에 사용될 노드 집합

K_j ^노드 j를 거쳐 노드 i와 두 개의 링크에 의해 연결된 노드로써 노드 i에서 노 드 탐색에 사용될 노드의 집합

N 검색 대상의 기준노드 i가 될 노드의 집합. N = {n₁,n_{2 ,}n_3,⋯ }

p_rj^{g 출발지점} r에서 노드 j에 이르는 경로로써 전노드코드 g에 해당하는 전노드 의 번호(predecessor 혹은 back node)

pp_rj^{g 출발지점} r에서 노드 j에 이르는데 전노드코드 g에 해당하는 전노드의 전노 드

R 최종결과로써 최단경로의 노선노드 집합

T^g_rk 노선탐색 중 출발지점 r에서 전노드 p^g_rk를 거쳐 노드 k까지의 현재 계산된 노선비용

(2) 손실가치의 계량화

국가기간망에 유고상황이 발생하여 도로가 붕괴 혹은 폐쇄될 경우 일정기간 동안 교통소통이 두절됨에 따라 해당 도로구간 상류부에 대기행렬을 초래하게 되어 심각한 교통혼잡을 야기하게 된다.

이를 계량화하기 위한 기본 원리는 공학적인 대기행렬 이론을 이용하여 단순 하게 아래 그림과 같이 나타낼 수 있으며, 본 연구에서는 이를 토대로 유고지역 의 교통혼잡 규모와 손실최소화 모형을 수립하였다.

<그림 5-2> 유고상황시 대기행렬 다이어그램 Q : 용량 rQ : 유고에 의해 감소된 용량 q : 교통수요 ID : 유고지속시간 MQL : 최대대기행렬 MWT : 최대대기시간 R1 : 복구시간(우회로 제공시) R2 : 추가 복구시간(우회로 미제공시) D1 : 총 지체(우회로 제공시) D2 : 추가 총 지체(우회로 미제공시) t0 : 유고 발생 시각 t1 : 유고 처리 시각

t2 : 대기행렬해소시각(우회로제공시) t3 :정상교통류도달시각(우회로미제공시)

한편, 이러한 교통혼잡은 주변도로에 전반적으로 교통부하를 전가시키고 이로 인한 전체도로체계내의 통행시간증가와 차량 운행비용의 증가에 따른 손실이 발 생한다. 이를 계량화하기 위해서는 기존의 도로타당성 조사에서 사용하였던 ‘Do’,

‘Do Nothing’ 대안비교법을 거꾸로 활용하여 유고로 인한 도로폐쇄 구간을 포함 시킨 대안과 그렇지 않은 대안의 통행배정결과를 비교하는 방안을 활용하였다.

교통손실의 계량화는 최근 적용되고 있는 ‘도로부문 예비타당성의 표준지 침’(2004, 한국개발연구원)에서 그 근거를 찾을 수 있다.

위의 표준지침에서는 도로 등 공공부문 사업을 시행함으로서 파생될 수 있는

‘교통측면의 편익’을 직접편익과 교통개선으로 인한 사회적 편익인 간접편익으 로 구분하여 제시하였다.

표준지침에서 제시된 많은 변수 중 계량화가 가능한 변수를 종합하여 제시하 면 차량운행비용, 통행시간비용, 교통사고비용 및 교통환경 비용으로 분류할 수 있으며, 본 연구에서는 통행시간비용만을 고려하였다.

<표 5-10> 교통손실 항목

구 분 교통손실 항목

교통부문 손실

① 차량운행 비용

② 통행시간 비용

③ 교통사고 비용

④ 교통환경 비용

통행시간비용은 국가적 재난에 대비한 신속한 대처하지 못함으로 인해 운전자 나 시민이 차량내부에서 보내는 시간이 늘어나는 것을 계산한 손실비용이다. 통 행시간 비용은 통행목적에 따른 통행시간가치를 추정해서 산정하며, 또한 업무 통행시간 가치, 비업무통행 시간가치로 구분하여 산출하며 산출방식은 다음과 같다.

① 업무통행 시간가치

현재의 임금수준을 산정하여 통행시간의 손실분에 대한 생산 활동을 증대시킬 수 있는 시간이다. 고용주의 측면에서 통행자의 인건비는 최소한 생산활동 가치 이상을 나타낸다고 말할 수 있으므로 업무통행의 시간가치는 인건비를 기준으로 산정될 수 있다.

기준이 되는 다른 여러 변수들이 있으나, 대부분의 선진국은 인건비 측면에서 통행시간가치를 고려함으로써 임금수준보다 높은 가치를 부여하고 있다. 2000년 기준 시간당 임금의 경우 승용차 운전자 8145원/인․시간, 버스 운전자 7595원/