여기서 : 출발지 에서 링크 까지의 최적경로비용r b : 링크 에서 링크 로의 환적비용b
: 링크 의 비용b
링크표지를 노드표지로 전환하는 과정을 수행하여 출발지에서 노드까지의 최 적 비용을 도출하였고 이때 노드 를 도착링크로 하는 링크들의 최적 비용 중k 최소값이 노드 의 최소비용이다k .
그림 노드기반 최적비용 경로탐색
< 4-10>
min ∀ ∗\
환적과 보관을 고려한 최적 경로탐색은 두 링크사이에서 발생하는 보관비용을 포함시키는 것으로 위의 알고리즘과 동일한 절차를 수행한다.
min 여기서 는 링크
에서 로의 보관비용b그림 환적과 보관을 고려한 경로탐색 개념도
< 4-11>
다목적 경로탐색 및 확률적 통행배정 3)
개요 (1)
기종점 간 비용 시간 탄소배출 등의 다목적, , 비용요인을 고려한 비지배경로의 탐색과 탐색 된 경로의 확률에 따라 통행배정하는 방안을 적용하였다 탐색된 비지배경로의 일반화비용. 의 차이가 크지 않은 경로만을 선별적으로 고려 하도록 유사경로 탐색기법을 적용하며 통행배 정 절차는 그림< 4-12>와 같다.
표식 (2)
복합교통망에서의 다목적경로 탐색기법에서 사용될 표식은 다음과 같다.
⋯는 링크 와 링크 의 환적에서 발생되는 개의 다른 환적속성 벡터를a b D 나타내며, ⋯ ⋯는 링크 와 링크 의 환적에서 발생되는 개의a b D
그림 통행배정 절차
< 4-12>
다른 환적속성과 개의 링크 의 주행속성이 함께 표현된 벡터를 의미한다L b . 또한, 는 링크 의 도착 출발 노드가 출발 도착 노드인 링크 집합을 나a ( ) ( ) 타내며, 는 경로 에 속한 링크의 l 번째 링크속성의 합을, 는
에 속한 인접 링크 간 l 번째 환적속성의 합을 의미한다 이를 정리해보면. 다음과 같다.
⋯ : 링크 와 링크 의 환적에서 발생되는 개의 다른 환적속성 벡a b D 터
⋯ ⋯ : 링크 와 링크 의 환적에서 발생되는 개의 다른 환적a b D 속성과 개의 링크L b 주행속성이 함께 표현된 벡터
: 링크 의 도착노드 출발노드 가 출발노드 도착노드 인 링크집합a ( ) ( )
: 출발지 에서 링크 까지의 경로r b
→ ⋯ →
: 출발지 에서 링크 까지의 가능경로집합r b (feasible path set)
: 경로 에 속한 링크의 l 번째 링크속성의 합
: 경로 에 속한 인접링크 간 l 번째 환적속성의 합
링크수단기반 비지배경로의 정의
①
수단 링크 확장으로 모든 수단이 링크로 표현되어 링크는 수단을 포함한 링크 -속성으로 표현이 가능하다 인접된 두 수단 링크의 환적속성과 주행속성의 구분. -을 위하여 인접링크 와 는 차원의 환적속성 링크 는 차원의 주행속성으로a b D , b L 그림 와 같이 표현되며 결합된 차원의 결합벡터로 그림 와 같
< 4-13> , D+L < 4-14>
이 표현된다.
그림 은 출발지에서 연결된 링크의 환적속성이 으로 초기화되는 것을
< 4-13> 0
보여주고 있으며 그림, < 4-14>, <그림 4-15>의 결합된 벡터 속성 값에 대한 링크 수단의 비지배경로를 정의하면 정의 과 정의 와 같다< 1> < 2> .
그림 인접링크에 대한
< 4-13>
환적속성과 주행속성의 구분
그림 인접링크에 대한
< 4-14>
환적속성과 주행속성의 통합
그림 출발지 에서 연결된 링크에 대한 환적속성과 주행속성
< 4-15> r
정의
[ 1] : 와 를 에 속하면서 서로 다른 경로라고 하면 두, 경로의 환적속성과 주행속성의 개별속성 ⋯ ⋯
에 대하여 ≤ 이고 어떤 값에 대하여 여기서는q (
)
이면, 는 를 지배(Dominate)한다고 정의한다.
정의
[ 2] : 에 속하는 어떤 경로에 대하여 에 속하는 다른 어 떤 경로도 지배하지 못하면 비지배경로(Non Dominated Path)라고 정 의한다.
정의 과 정의 는 링크 수단으로 계산된 비지배경로로 실제교통망에서는 [ 1] [ 2]
-출발노드에서 어떤 노드까지의 경로로 표현되어야 하므로 노드기반 표지로 전환이 필요하며 정의, [ 3]에 의하여 노드기반으로 전환된 표지로 구축된다.
[정의3] : 에 속하는 경로 가 정의 과 정의 를 만족하면 경로집[ 1] [ 2]
합 에 속하는 경로가 노드기반으로 전환된 비지배경로 이다.
다목적 링크표지갱신 알고리즘
②
수단 링크로 확장된 네트워크에 대하여 출발지 에서 모든 링크까지 다목적 링- r 크표지갱신 알고리즘은 크게 가지로 분류3 - (1)초기화 과정, (2)다목적 링크경로 표지갱신(Link Path Label Correcting), (3)다목적 링크경로표지를 다목적 노드경로 표지로 전환 - 된다 초기화 과정에서 환적속성과 링크주행속성을 모두 고려한. 링크기반 최적경로를 통해 계산한다.
다목적 링크경로표지갱신에서는 출발지부터 모든 링크까지 정의 과 정의[ 1] [ 2]
를 만족하는 경로에 대해서는 경로전체를 표지로서 유지하는 것을 의미한다 이. 방법을 적용하면 계산에 소요되는 메모리는 매우 증가하나 경로를 계산하기 위, 해 필요한 절차를 단순한 논리로 구축할 수 있다.
마지막으로 출발지와 도착지는 노드로 표현되므로 링크경로표지를 노드경로 표지화하는 과정으로서 정의 을 만족하도록 노드경로표지를 갱신한다[ 3] .
[Step 0] 초기화
∞ ∀∈ ╲∈ ⋯
∞ ∀∈╲∈
⋯
∀∈
⋯
∀∈ ⋯
[Step 1] 링크확정표지기반 알고리즘의D+L번 수행과 함께 정의 과 정의[ 1] [ 2]
를 만족하는 다목적 링크수단 경로표지 초기화 및 계산
∀∈╲∈
⋯
∀∈╲∈
⋯
[Step 2] 다목적 링크 수단 경로 표지갱신-
-정의 과 -정의 를 만족하는 링크경로표지 확정 갱신과정 수행 [ 1] [ 2]
[Step 3] 다목적 링크 수단 경로 표지의 다목적 노드 수단 경로 표지로 전환- - - -정의 을 만족하는 탐색된 노드 수단 경로 표지 계산
[ 3] -
-유사경로 개념을 적용한 최적 대안 경로 결정
③
화물운송 운전자는 자신이 통행하는 경로에 대해 몇 가지 대안 경로를 가지고 있으며 환적 하는 역이 존재하기 때문에 운송교통망은 단일경로로 통행행태를, 표현할 수 없다 이를 해결하기 위해서는 대등한 서비스를 제공하는 다수의 유사. 경로를 파악하는 것이 필요하다 유사경로는 최적의 경로와 비교하여 비용측면. “ 에서 크게 차이가 나지 않는 경로 로 정의하며 유사경로를 결정하는 기준으로는” , 경로의 통행비용을 사용하도록 한다.
각 경로의 통행비용은 환적에 대한 불편도 개념이 적용되어 있어 특정 물품에, 대하여 경로를 선택하는 합리적인 기준이 될 수 있다 여기서 유사한지의 여부는. 통행거리 분포에 따라 몇 가지 변수가 포함될 수 있으나 본 연구에서는 최적 경, 로의 통행비용 대비 다른 경로의 통행비용의 차이가 몇 내에 포함되는지의 여% 부로 유사경로를 나타낼 수 있다.
이는 개인이 느끼는 불편도를 고려하여 결정한 최적 경로에 비해 어느 정도까, 지 통행대안 경로로 선택할 지의 여부로 보면 된다 예를 들면 최적경로의 일반. , 화 비용이 70만원일 때 최적경로, 10% 이내에 포함되는 경로를 유사경로로 본다 면 즉 일반화 비용이, , 77만원 이내인 모든 경로가 유사경로가 되며 유사경로를, 결정하는 과정은 다음 그림< 4-16>과 같다.
그림 유사경로 결정 과정도
< 4-16>
비지배경로 및 유사경로의 사례
④
개 노드와 개 경로의 예를 들면 출발지 에서 도착지 을 연결하는 경로가
2 5 , 0 1
총 개 존재하고 정의 과 정의 를 만족하는 비지배경로는5 [ 1] [ 2] [5,6], [6,5]의 속성 통행비용 환적시간 을 갖는 번과 번 경로이다 여기서 비지배경로 이외의 나
( , ) 1 5 .
머지 개 경로의 속성 값은3 [6,6], [6,7], [7,6]으로 이미 탐색된 두 개의 비지배경로 와 유사한 속성 값을 나타내고 있으나 비지배경로에는 포함되지 않는다, .