Journal Search Engine

Volume/Issue :

Year(s) : to

Search :

Title :

Author :

Keyword :

Abstract :

Figure :

Table :

Reference :

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.23 No.2 pp.1-14
DOI : https://doi.org/10.12815/kits.2024.23.2.1

Development of A Turn Label Based Optimal Path Search Algorithm

Meeyoung Lee^*

^*National Economic Advisory Council

^† Corresponding author : mylee@krihs.re.kr

Received 26 May 2023 │ Revised 27 June 2023 │ Accepted 2 April 2024

Abstract

The most optimal route-search algorithm thus far has introduced a method of applying node labels and link labels. Node labels consider two nodes simultaneously in the optimal route-search process, while link labels consider two links simultaneously. This study proposes a turn-label-based optimal route-search technique that considers two turns simultaneously in the process. Turn-label-based optimal route search guarantees the optimal solution of dynamic programming based on Bellman’s principle as it considers a two-turn search process. Turn-label-based optimal route search can accommodate the advantages of applying link labels because the concept of approaching the limit of link labels is applied equally. Therefore, it is possible to reflect rational cyclic traffic where nodes allow multiple visits without expanding the network, while links do not allow visits. In particular, it reflects the additional cost structure that appears in two consecutive turns, making it possible to express the structure of the travel-cost function more flexibly. A case study was conducted on the metropolitan urban railway network consisting of transportation card terminal readers, aiming to examine the scalability of the research by introducing parameters that reflect psychological resistance in travel with continuous pedestrian transfers into turn label optimal path search. Simulation results showed that it is possible to avoid conservative transfers even if the travel time and distance increase as the psychological resistance value for continuous turns increases, confirming the need to reflect the cost structure of turn labels. Nevertheless, further research is needed to secure diversity in the travel-cost functions of road and public-transportation networks.

Key Words : Node Label , Link Label , Turn Label , Optimal Path Algorithm , Integrated Transportation Network , Psychological Resistance

Turn Label 기반 최적경로탐색 알고리즘 개발

이 미 영^*

^*주저자 및 교신저자 : 국민경제자문회의 연구관

초록

지금까지의 최적경로탐색 알고리즘은 노드표지와 링크표지를 적용하는 방안이 소개되었다. 노드표지는 2개의 노드를 최적경로 탐색과정에서 동시에 고려한다. 링크표지는 2개의 링크를 탐색과정에서 동시에 고려한다. 본 연구는 2개의 회전을 탐색과정에서 동시에 고려하는 회전 표지기반 최적경로탐색기법을 제안한다. 회전표지기반 최적경로탐색은 2개의 회전을 탐색과 정에서 고려하기 때문에 Bellman(1957)의 최적원리에 근거한 동적프로그래밍의 최적해가 보장 된다. 한편 회전표지기반 최적경로탐색은 링크표지의 극한 접근 개념을 동일하게 적용하기 때 문에 링크표지를 적용하는 장점을 수용할 수 있다. 따라서 네트워크의 확장없이 노드는 복수 의 방문이 허용되면서 링크는 방문이 허용되지 않는 합리적 순환통행을 반영하는 것이 가능하 다. 특히 2개의 연속회전에서 나타나는 추가적인 비용구조를 반영하는 특성이 포함되어 통행 비용함수의 구조를 보다 유연하게 표현하는 것이 가능하다. 교통카드 단말기로 구성된 수도권 도시철도 네트워크를 대상으로 시행된 사례연구는 연속된 보행환승이 나타나는 통행에 대한 심리적 저항감을 나타내는 파라메타를 Turn Label 최적경로탐색에 도입하여 연구의 현실적 확 장성을 검토하였다. 연속회전에 대한 심리적 저항값이 커지면서 통행시간 및 거리가 늘어나도 연속된 환승을 우회하는 방안으로 시뮬레이션 결과가 도출되어 Turn Label의 비용구조를 반영 하는 것이 확인되었다. 향후 도로교통망 및 대중교통망의 통행비용함수에 대해 다양성을 확보 하기 위한 추가적인 연구의 진행이 필요하다.

키워드 : 노드표지 , 링크표지 , 회전표지 , 최적경로탐색 , 복합교통망 , 심리적 저항감

This article has been cited by 0 article in crossref

Cited-By

Funding:

Ⅰ. 서 론

최적경로탐색 알고리즘(이하 최적경로탐색)은 노드표지(Node Label: NL)에서 시작되었다. Node Label 기반 최적경로탐색은 출발노드에서 도착노드까지의 최적비용경로를 탐색하는 것이다. Moore(1957)는 Node Label 갱신(NL Correction) 최적경로탐색을 제안하였다. Dijkstra(1959)는 Node Label 확정(NL Setting) 최적경로탐색 을 제안하였다. 이 두 알고리즘은 Bellman(1957)의 최적원리(Optimality Principle)를 만족하여 동적프로그래밍 (Dynamic Programming) 해법에 적용된다. 이후 최적경로탐색은 컴퓨터의 자료구조 측면에서 효과적으로 개 선될 수 있음이 Dial(1969)과 Dial et al.(1979)에 의해서 검토 및 제안되었다.

최적원리가 보장되는 측면에서 링크표지(Link Label: LL)를 적용하는 최적경로탐색은 Lee(2004)에 의해서 광범위하게 검토되었다. Lee(2004)는 Link Label을 적용하여 링크 사이의 회전점수(Turn Penalty)를 도시교통 망의 교차로 부근에서 네트워크 확장 없이 반영할 수 있는 장점으로 활용하였다. 회전점수를 반영하는 방안 은 Caldwell(1961), Kirby and Potts(1969), Thomas(1991), Choi(1995), Noh and Namgoong(1995)에 의해서 도시교 통망의 교차로의 회전비용이 발생되는 상황을 염두에 두고 검토 및 연구되었다.

<Fig. 1>은 Node Label과 Link Label이 적용되는 차이점을 설명하고 있다. <Fig. 1(1)> Node Label로서 두 노드 i, j 에 대해 i 와 j 노드를 연결하는 링크비용(Δ_ij)를 나타내고 있다. 이때 모든 첨자는 노드로 표현되 고 있음을 알 수 있다. <Fig. 1(2)>는 Link Label로서 두 링크 a, b에 대해 a와 b 링크를 연결하는 회전비용 (d_ab)를 나타내고 있다. <Fig. 1(2)>는 모든 첨자가 링크로 표현되고 있음에 주목할 필요가 있는데 링크 a, b 의 비용을 각각 Δ_a 와 Δ_b로 나타내고 있다.

<Fig. 1>

Difference Between Node & Link Labels

지금까지 링크표지기법까지 연구가 진행되었다고 가정해 볼 때 이러한 표지기법을 계속해서 확장하는 방 안에 대한 고민이 본 연구의 시작이라고 볼 수 있다. Node Label과 Link Label에서 계속 확장되는 상황은 Turn Label, Two Link Label의 진행단계를 예측할 수 있다. 이러한 상황에서 Link Label의 다음 단계인 Turn Label이 적용된 최적경로탐색 과정에 대한 검토가 우선적으로 시행된 사례가 존재하지 않는다.

<Fig. 2>는 물리적으로는 두개의 인접링크(ab)로 표현되는 Turn Label(T_x)을 설명한다. Turn Label이란 두 개의 인접링크 사이에 존재하는 회전을 의미한다. 회전은 두 개의 링크로 표현되기 때문에 Turn Label을 고 려해서 경로선택 알고리즘을 구축하게 되면 탐색 과정에서 두 개의 회전을 동시에 반영하는 문제가 된다. 교 통망에서 두 개의 회전은 세 개의 연속된 링크로 표현되기 때문에 Turn Label 기반 최적경로탐색을 구축하기 위해서 세 개의 연속된 링크를 두 개의 인접회전인 T_x 와 T_y 로 적용하는 방안이 필요하다. <Fig. 2>는 인접 회전이 포함하는 비용구조를 나타내고 있다. 인접회전은 3개의 링크(a, b, c)로 표현되고, 각 링크와 링크 사 이의 회전비용(d_ab, d_bc)이 반영되는 링크표지의 속성이 그대로 포함된다. 이와 더불어 회전(T_x)과 회전(T_y) 사이에서 나타나는 회전의 회전의 회전비용( $d_{T_{x} T_{y}}$ )이 함께 합산될 수 있음을 알 수 있다.

<Fig. 2>

Turn Label & Cost Structure

이와같이 네트워크의 비용구조를 보다 세부적으로 적용할 수 있다는 점이 나타남에도 지금까지 Turn Label을 적용한 최적경로탐색은 제시되지 않았다고 볼 수 있다. 따라서 Turn Label 기반의 최적경로탐색에서 최적해에 도달하는 특성과 함께 실제 컴퓨팅에서의 적용 여부를 검증하는 작업이 필요하다.

본 연구는 Turn Label 기반의 최적경로탐색의 이론 및 실제 응용 사례를 검토한다. 이를 위해 1) 우선 Turn Label로 표시되는 최적경로탐색을 수식화하며, 2) Link Label 최적경로탐색과 비교하여 추가적인 비용구조를 검토하고, 3) 수도권 도시철도망을 대상으로 연속된 보행환승에 대하여 “하기 싫음”의 파라메타를 도입하는 사례를 분석한다.

Ⅱ. 선행연구 고찰

1. 노드표지(Node Label) 기반 최적경로탐색

Node Label 기반 최적경로탐색(Moore 1957;Dijkstra 1959)은 출발노드 r에서 모든 노드까지의 최적비용트리 (Optimal Cost Tree)를 구축하며 수식은 식(1) 및 <Fig. 3>과 같다. 여기서 탐색과정은 Node Label로 표시된 링 크(ij)로 한정되어 이루어지는 것을 보여주고 있다.

π^{r j} = min (π^{r i} + Δ_{i j}, π^{r j})

(1)

<Fig. 3>

Concept of Node Label Based Optimal Path Detection

여기서

π^rj : 출발 r에서 노드j 까지 최적비용
Δ_ij : 링크(ij)의 비용

2. 덩굴망(Vine) 기반 최적경로탐색

Node Label을 적용해서 두 링크 사이의 회전을 반영하는 방안을 구축한 연구가 제안되었으며 이를 덩굴망 (Vine)으로 구축하였다. Vine은 줄기를 구부릴 수 있는 유연성을 나타내기 위한 용어로서 교통망의 U-Turn을 표현하기 위해서 적용되었다. Thomas(1991)에 의해서 제안되었으며 Choi(1995)에 의해서 교차로를 중심으로 나타나는 순환 통행(Cyclic Trip)을 반영하는 방안으로 적용하였다. Choi(1995)는 간단한 교통망의 확장을 통 해서 최적조건을 만족하는 방안을 검토하였다. 식(2) 및 <Fig. 4>와 같이 경로탐색을 시행하는 모든 첨자가 3 개의 연속적으로 연결된 노드(i, j, k)로 링크비용(Δ_ij, Δ_jk), 회전비용(d_ijk)를 표현하고 있다. 특히 노드 i 와 k 사이에 노드 j 를 고려하기 위해 확장되는 과정에서 Bellman(1957)의 최적조건이 만족하지 못하는 상황 이 나타난다. Choi(1995)는 네트워크 변형을 통해서 최적해를 유도하는 방안을 제시하였다.

π^{r k} = min (π^{r i} + Δ_{i j} + d_{i j k} + Δ_{j k}, π^{r k})

(2)

<Fig. 4>

Concept of Vine Based Optimal Path Detection

여기서

π^rk : 출발 r에서 노드k까지 최적비용
Δ_jk : 링크(jk)의 비용
d_ijk : 회전(ijk)의 비용

3. 링크표지(Link Label) 기반 최적경로탐색

경로탐색에서 Bellman(1957)의 최적조건을 만족하면서 회전점수를 반영하는 최적경로탐색은 Link Label을 활용하는 방법이다. Lee(2004)는 Choi(1995)의 3개 연속 노드(i, j, k)로 구성된 Vine을 2개의 인접링크(a, b) 로 표현하였다. 식(3)과 <Fig. 5>와 같이 링크의 도착지점(끝없이 접근하는 극한 개념으로 도착노드는 아님) 으로 표현하였다. 두 개의 전후방 링크로 표현되면 식(1)과 같이 적용이 가능하다. Link Label 기반 최적경로 탐색은 네트워크의 확장이 요구되지 않도록 회전점수가 반영된다. 한편 도착노드 s 가 확정되면 식(3)과 같 이 r - s 간 링크비용을 노드비용으로 확정하는 과정이 필요하다.

\begin{array}{l} π^{r b} = min (π^{r a} + d_{a b} + Δ_{b}, π^{r b}) \\ π^{r s} = min (π^{r b} | b \in Γ_{-}^{s}) \end{array}

(3)

<Fig. 5>

Concept of Link Label Based Optimal Path Detection

여기서

π^ra^(b) : 출발 r에서 링크a(b)의 도착지점까지 최적비용
d_ab : 회전(ab)의 비용
Δ_b : 링크(b)의 비용
$Γ_{-}^{s}$ : 도착노드가 s 인 링크집합
π^rs : 출발 r에서 도착노드 s 까지 최적비용

Ⅲ. Turn Label 기반 최적경로탐색 알고리즘

1. 이론적 기반

Turn Label 이란 두 개의 인접링크 사이를 의미하며 <Fig. 5>에서 회전(ab)와 같은 개념이다. 본 연구의 Turn Label 기반 최적경로탐색은 두 개의 인접 Turn을 고려하며 이는 3개의 연속된 링크(a, b, c)로 나타난다. 이때 회전(ab)을 T_x 로, 회전(bc)를 T_y 로 각각 나타내며 Turn Label 기반의 최적경로탐색은 식(4)와 <Fig. 6>과 같이 나타낸다. 이때 두 인접 Turn으로 구성된 식은 Bellman(1957)의 최적조건이 일차적으로 성립된다고 볼 수 있다.

<Fig. 6>

Concept of Turn Label Based Optimal Path Detection

여기서 도착 Turn이 출발링크(b)와 도착링크(c)로 구성되어 있으므로 c까지의 최적통행비용을 우선 산정 하는 과정이 요구된다. 여기까지는 Link Label 기반 최적경로탐색과 동일하다. 따라서 도착노드 s 가 확정되 면 식(3)의 r - s 간 링크비용을 노드비용으로 확정하는 과정이 요구된다.

\begin{array}{l} π^{r T_{y}} = min (π^{r T_{x}} + d_{T_{x} T_{y}} + Δ_{c}, π^{r T_{y}}) \\ π^{r c} = min (π^{r T_{y}} | T_{y} \in Γ_{-}^{c}) \\ π^{r s} = min (π^{r c} | c \in Γ_{-}^{s}) \end{array}

(4)

여기서

: 출발 r에서 Turn T_y_(x) 의 도착지점까지 최적비용
Δc : 링크(c)의 비용
: 회전의 회전(T_xT_y)의 비용
$Γ_{-}^{c}$ : 링크(c)가 도착링크인 회전집합
π^rc : 출발 r에서 도착링크(c)까지 최적비용

Turn Label 기반 최적경로탐색에서 소개되는 회전의 비용 $d_{T_{x} T_{y}}$ 를 통해 3개의 링크를 탐색하는 차이점이 나타난다고 볼 수 있다. 이를 증명하기 위해 <Fig. 7>과 같이 링크(b)까지의 최적경로비용(π^rb)와 회전(T_X) 의 비용을 일치시키면 이 문제는 회전(ab)를 이끌고 다니면서 회전(bc)로의 탐색문제로 정확하게 표현된다. 따라서 Turn Label 기반 최적경로탐색은 $d_{T_{x} T_{y}}$ 가 탐색과정에서 반영되면서 Link Label 기반 최적경로탐색의 특성이 모두 포함된다.

π^{r T_{y}} = min (π^{r T_{x}} + d_{T_{x} T_{y}} + d_{b c} + Δ_{c}, π^{r T_{y}})

(5)

<Fig. 7>

Concept of Turn Label Based Optimal Path Detection

여기서

d_bc : 회전(bc)의 비용

2. 비용구조 확장( $d_{T_{x} T_{y}}$ ) 사례 검토

식(5)에 의해서 Turn Label 기반 최적경로탐색은 Link Label 탐색과 비교해서 모든 비용구조를 포함하면서 회전의 회전에서 나타나는 비용( $d_{T_{x} T_{y}}$ )이 추가로 반영된다는 점에서 차이가 있다. $d_{T_{x} T_{y}}$ 는 현실에서 발생하 는 도로교통의 신호교차로를 대상으로 한 사례에서 나타난다. <Fig. 8>은 도시도로의 연속해서 위치하는 신 호교차로가 연속되는 회전과 회전에서 발생하는 통행비용을 보다 면밀하게 반영하는 상황을 나타내고 있다. ①은 우회전(ab)에서 회전비용(d_ab)가 반영되고 링크(b)의 비용(Δ_b)이 적용되고 다시 좌회전(②), 직진(③), 우회전(④)을 통해 추가 회전비용(Δ_c)이 발생하는 것을 보여주고 있다. 이때 $d_{T_{x} T_{y}}$ 의 역할을 추론하면, 링크 (a)에서 링크(c)까지의 교통상황, 즉 하류부 교통류의 변화를 보다 세분화하여 통행비용에 반영하는 것이 가 능하다는 것이다. 이러한 전략은 자율주행차량과 같이 교통상황의 변화에 상호작용성이 높은 시스템에 적합 할 수 있다. 한편 본 연구의 사례연구로 제시하고 있는 수도권 도시철도 네트워크에서 환승 후 바로 환승과 같은 저항감에 대한 심리적 비용을 적용하는 사례로 활용될 수 있다. 3개의 링크를 연속으로 반영하는 Turn Label의 $d_{T_{x} T_{y}}$ 비용구조를 통해서 Label이 계속해서 확장된다고 가정하는 2-Link Label, 2.5-Link Label, 3-Link Label 등의 비용구조가 이와 유사한 패턴으로 적용될 것이다. 한편 현실적인 경로탐색의 측면에서 현재의 Turn Label인 1.5-Link Label 이상으로 확장하는 것은 실효성이 떨어진다고 볼 수 있다. 향후 교통망 이상의 복잡한 네트워크 구조가 나타나면 이때 적용해 보는 것도 의미가 있다고 평가된다.

<Fig. 8>

Cost Structure of $d_{T_{x} T_{y}}$

3. Turn Label 확정 해법

Dijkstra(1959)가 제시한 Node Label 확정 기반 최적경로탐색은 탐색 노드 집합(Next Node Set: NNS)에서의 출발지에서 가장 최소의 비용으로 나타나는 노드를 선택하여 탐색을 진행한다. Lee(2004)는 Link Label 확정 기반 최적경로탐색은 탐색 링크 집합(Next Link Set: NLS)에서 가장 최소의 비용으로 나타나는 링크를 선택 하여 진행하며 정확하게 Dijkstra(1959)가 제시한 방법을 적용했다. 여기서도 Turn Label 확정 기반 최적경로 탐색이 해법으로 적용될 수 있음을 사례를 통해서 검토한다.

우선 <Fig. 9>는 최소 단위의 링크에도 적용되는 Turn Label을 구축하기 위해서 가상의 출발 및 도착노드 r, s 를 연결하는 가상의 링크를 도식화하였으며 본 연구는 여기서 제시된 네트워크의 확장을 통해서 해법을 구축한다. <Table 1>은 단일 링크에서 Turn Label 기반 경로탐색의 과정이 수행됨을 보여주고 있다.

<Fig. 9>

Network Transformation Using Dummy Nodes and Links

<Table 1>

Turn Label Detection Process for One Link

T_x	T_y	Cost	Back Turn
-	ⓡ-a-ⓢ	Δ_a	-
ⓡ-a-ⓢ	-

다음으로 Turn Label 확정 기반 최적경로탐색을 검토하기 위하여 도입된 교통망은 <Fig. 10(1)>과 같이 4 개 노드와 4개 링크로 이루어져 있다. 출발노드 ①, 도착노드 ④가 정해진 상황에서 네트워크를 <Fig. 10(2)> 와 같이 확장하여 Dijkstra(1959) 및 Lee(2004)가 검토한 Label 확정 과정을 Turn Label에 재현하면 <Table 2> 와 같다. 탐색 회전 집합(Next Turn Set)에서 최소비용의 Turn을 선택하여 다음 탐색 Turn으로 적용하고 표지 를 확정한다. 총 Turn 개수만큼 6회 탐색을 시행한다(ⓡ①②, ⓡ①③, ①②④, ①③②, ③②④, ②④ⓢ).

<Fig. 10>

4-Node-4 Link Network and Network Transformation

<Table 2>

Turn Label Setting Based Optimal Detection Process

T_x	T_y	$d_{T_{x} T_{y}}$	Cost	Back Turn	Next Turn Set
-	ⓡ①②	0	6	-	{ ⓡ①②, ⓡ①③ }
-	ⓡ①③	0	3	-	{ ⓡ①②, ⓡ①③ }
ⓡ①③	①③②	0	5	ⓡ①③	{ ⓡ①②, ①③② }
①③②	③②④	0	6	①③②	{ ①③②, ③②④ }
ⓡ①②	①②④	0	7	ⓡ①②	{ ③②④, ①②④ }
③②④	②④ⓢ	0	6	③②④	{ ①②④, ②④ⓢ }
②④ⓢ	-				{ ①②④ }
①②④	②④ⓢ	0	7>6		{ }

Bellman의 최적조건에 적합한 동적프로그래밍(Dynamic Programming)이 적용되어 도착지  에서 역방향 Turn으로 경로를 구축하는 식(4)의 적용 과정은 아래와 같다.

\begin{array}{l} π^{r (4 s)} = min (π^{r (24 s)}) = 6 \\ π^{r s} = min (π^{r (4 s)}) = 6 \end{array}

ⓡ①③→③②④→②④ⓢ : 6
ⓡ①→①③→③②→②④→④ⓢ : 6
ⓡ→①→③→②→④→ⓢ : 6
①→③→②→④ : 6

4. Node 및 Link 순환경로 제거

Turn Label 기반 최적경로탐색 과정에서 2-Turn (3-Link)를 한 번에 고려하게 되며 이는 Node 및 Link 순환 경로(이하 Cyclic Path: CP) 통행을 발생시킬 수 있다. Node 순환 통행(Cyclic Path)은 U-Turn과 P-Turn의 합리 적 통행을 포함하며 Lee(2004)가 예시한 바와 같이 Link Label 기반 최적경로탐색에서 반영이 가능하다. 한편 Turn Label을 적용하면 Link 순환통행이 형성되기 때문에 이에 대한 별도의 검토가 필요하다.

우선 Turn Label 기반 최적경로탐색은 탐색과정에서 3개 링크를 동시에 처리하기 때문에 Link CP 및 Node CP가 생성될 수 있다. Lee(2004)는 교통망에서 합리적 Node CP는 가능하다고 언급하였으며 이는 <Fig. 11> 과 같은 통행의 발생을 의미한다. 한편 교통망에서 Link를 재방문하는 상황은 현실적으로 나타나지 않기 때 문에 <Fig. 12>는 발생하지 않는다. 일반적으로 도로교통망은 Node CP가 가능하나 Link CP는 허용되지 않는 다. 한편 대중교통망에서는 Node 및 Link CP가 나타나지 않는다고 볼 수 있다. 교통망의 특성에 따라서 Node 및 Link CP를 탐색과정에서 선택적으로 선별하는 과정이 요구된다.

<Fig. 11>

Generation of Node Cyclic Path

<Fig. 12>

Generation of Link Cyclic Path

Ⅳ. 사례연구

1. 수도권 도시철도망과 교통카드기반 자료 통행함수

본 연구는 사례연구를 위해서 교통카드자료로 구축된 수도권 도시철도를 대상으로 통행함수를 구축하고 Turn Label 기반 최소시간통행경로 탐색을 시행한다. 2022년 5월 31일 일일 자료를 기준으로 수도권 도시철 도는 615개 역사와 114개 환승역으로 구성되어 있다. 승객의 승차 역사 TagIn 및 하차 역사 TagOut 단말기의 경우 환승역사에서는 복수로 비치·운영된다. 615개 역사에서 운영되는 요금단말기는 731개이다. <Table 3>은 단말기ID로 구성된 역사 및 도시철도 관리 노선을 나타내고 있다. <Fig. 13>은 수도권 도시철도망과 환승역 사를 나타내고 있다.

<Table 3>

Smart Card ID and Station Name and Line

Terminal ID	Station Name	Urban Railroad Line
0152	Jonggak	Line1
-	-	-
1846	Suwon	Bundang Line

<Fig. 13>

Seoul Metropolitan Urban Railway Network and Transfer Stations

수도권 도시철도의 경로탐색에 적용되는 통행비용함수는 식(6)에서 환승역사의 보행시간(분)인 W_ab와 W_bc와 열차를 기다리는 평균배차간격(분) H_c/2과 차내통행시간(분) t_c를 나타내고 있다. 식(6)에서 $d_{T_{x} T_{y}}$ = β ∙ (W_ab⊕W_bc) 로 전환하여 사용하고 있는데 이는 2개 Turn에서 연속으로 환승이 나타나는 상황을 인지적 인 저항비용(감)으로 나타내도록 하는 것이다. 여기서 β는 W_ab > 0와 W_bc > 0인 상황(즉, 회전 ab와 bc가 모 두 보행환승이 필요한 경우)에서 저항을 나타내는 파라메타로 ⊕연산자는 이러한 내용을 포함하고 있다. 또 한 식(5) $π^{r T_{y}} = min (π^{r T_{x}} + d_{T_{x} T_{y}} + d_{b c} + Δ_{c}, π^{r T_{y}})$ 의 d_bc = W_bc이고 Δ_c = H_c/2 + t_c로 식(6)으로 전 환되고 있다. 이는 환승보행후 링크c의 통행시간(Δ_c)은 차량대기시간(H_c/2)과 링크주행시간(t_c)을합산한 것이다.

π^{r T_{y}} = min(π^{r T_{x}} + β \cdot (W_{a b} \oplus W_{b c}) + W_{b c} + \frac{H_{c}}{2} + t_{c}, π^{r T_{y}})

(6)

<Table 3-6>은 역명노드를 구성하는 교통카드단말기ID(Terminal ID), 노선링크, 환승보행시간(W_ab), 노선평 균배차시간(H_b)을 나타내고 있으며 시나리오를 컴퓨팅으로 수행하는 입력자료로 적용된다. <Table 3>의 교 통카드단말기ID는 총 731개, 역명으로 분류된 역사는 총 615개로 구성되었다. <Table 4>의 수단-링크는 9호 선 급행 및 완행을 포함하여 1,429개로 구축되었다. <Table 5>의 환승역의 방향별 회전은 총 2,508개로 이중 동일노선의 통과는 1,401개, 보행이 필요한 환승은 1,107개로 구성되었다. <Table 6>의 노선별 평균배차간격 은 1호선부터 김포골드라인까지 총 34개 노선이 반영되었다. 연속 Turn은 총 4,809개가 생성되었으며 이중 연속으로 환승이 나타나는 경우는 1,178개가 자체적으로 구축되었다.

<Table 4>

Link Data (Δ_b, minutes)

Departure Station	Arrival Station	Travel Time(minutes)	Subway Line
Noryangjin	Daebang	2.5	Kyungbu Line
-	-	-	-
City Hall	Euljiro 1 ga	2.0	Line 2

<Table 5>

Pedestrian Transfer Time (W_ab ,W_bc, minutes)

From Station	Transfer Station	To Station	Transfer Time(minutes)	From Line	To Line
Yangjae	Gangnam	Yeoksam	3.5	Sinbundang Line	Line 2
-	-	-	-	-	-
Songpa	GarakMarket	Suseo	1.8	Line8	Line 3

<Table 6>

Headway of Urban Railroad Line (H_b, minutes)

Line	Headway(minutes)
Line 1	3.7
-	-
U-Line	5.5

사례연구에 적용되는 수도권 도시철도 통행자료는 일일 연계통행(Trip Chain: TC)에서 도시철도 통행(S)를 모두 고려한 것으로 총 8,270,305(TC)가 생성되었다 <Table 7>. 이들 연계통행자료를 대상으로 615개의 역 간 통행자료 OD로 구성한 결과 242,724개로 나타났으며 유효 OD 통행은 7,889,088(통행)으로 구축되었다.

<Table 7>

Trip Chains with Railroad Trip(S) in Smart Card Data (2022.5.31, Tuesday)

Sequence	Trip Chain	Count	Sequence	Trip Chain	Count
1	S	5934399	21	BSS	603
2	BS	1028076	22	BBSBB	525
3	SB	982691	23	SSB	471
4	BSB	219220	24	SBBSB	470
5	SBB	37342	25	BBBBS	401
6	BBS	28370	26	SBBBS	223
7	BSBB	7963	27	SBSBB	197
8	BBSB	6384	28	SBSBS	159
9	SBS	5194	29	BBSBS	99
10	SBBB	3515	30	BSSB	76
11	SS	3458	31	SSBB	9
12	BBBS	2171	32	BSSBB	4
13	SBBS	2090	33	SSS	4
14	SBSB	1272	34	BBSS	2
15	BSBBB	1115	35	SSSB	2
16	BSBS	1110	36	BBSSB	2
17	BBBSB	724	37	BSSS	2
18	SBBBB	685	38	SSBBS	1
19	BSBBS	666	39	BSSBS	1
20	BSBSB	608	40	SSBBB	1

2. 시나리오 평가

사례연구는 승객의 통행에서 연속된 보행환승이 나타나는 상황에 대한 심리적 저항감을 표현하는 방안을 강구하는 측면으로 분석하였다. 이를 위해 식(6)의 통행함수에서 β ∙ (W_ab +W_bc∣W_ab > 0 ,W_bc > 0) 에 적용 되는 β=(0, 1, 3, 5, 10, 15, 20, 25) 순으로 증가시켰다. 이는 모든 OD 간 최소통행비용을 적용하여 전량배정 을 시행하는 과정에서 (W_ab > 0 ,W_bc > 0)가 나타나는 3개의 연속링크 abc (2개의 연속회전 통행 $υ_{T_{x} T_{y}}$ 의 통 행량이 0이 되는 상황을 분석하기 위한 것이다.

모든 OD간 전량배정이 β값에 따라 분석된 평가 결과는 <Table 8>과 같다. β=0 는 연속 보행환승에 대해 서 심리적인 저항감이 없는 상태로 총 통행의 0.51181(%)로 나타났다. β가 증가하면서 연속된 보행환승을 피하는 상황을 모사하는 것으로 분석되었다. 총배정통행량(A)에서 연속된 보행환승이 나타나는 통행의 비율 은 점차 줄어들면서 β=25의 상황에서 연속된 보행이 발생하는 환승통행( $υ_{T_{x} T_{y}}$ )이 0이 되는 상황이 나타났다. 이는 시나리오에서 예상한 바와 같이 저항감을 크게 느끼고 회피하는 상황을 모사하는 것을 보여주고 있다.

<Table 8>

Assigned Trip with Psychological Resistance Parameter (β)

β	$υ_{T_{x} T_{y}}$		B/A*100 (%)
β	Total Assigned Trip : (A)	(W_ab > 0, W_bc > 0) : (B)	B/A*100 (%)
0	61521664	314875	0.51181
1	62078552	50894	0.08198
3	62175224	9830	0.01581
5	62189919	6145	0.00988
10	62209664	2052	0.00330
15	62217010	134	0.00022
20	62218433	17	0.00003
25	62232332	0	0.00000

Ⅴ. 결 론

기존의 최적경로를 탐색하는 표지를 구분하는 경우 Node Label과 Link Label로 소개되었다. Node Label은 경로탐색과정에서 2개의 노드를 동시에 탐색한다. 또한, Link Label도 2개의 링크를 동시에 탐색한다. 다만 2 개의 인접링크 사이에 회전을 나타내는 방식으로 Node Label은 네트워크 확장을 적용하며 Link Label은 확장 없이 적용이 가능하다. 본 연구는 연속된 2개의 링크로 구성된 회전(Turn)을 경로탐색에 반영하는 Turn Label 방식을 소개한다. Turn Label 기반의 최적경로탐색은 2개의 연속된 Turn을 탐색에 활용하며 이는 3개의 링크 를 동시에 탐색하는 형태로 진행된다. Turn Label 기반의 최적경로탐색은 동적프로그래밍의 적용인 전후방 탐색 조건을 만족하기 때문에 최적해는 보장되는 것으로 나타났다.

본 연구는 Turn Label 기반 최적경로탐색을 도식화하는 과정에서 링크표지에서 적용하는 링크의 도착노드 에 대한 극한 개념의 적용을 통해서 기존의 해법 적용이 가능하도록 구축하였다. 사례연구는 수도권 도시철 도를 대상으로 1일 교통카드의 역간 OD는 전량배정하는 상황을 염두에 두고 연속된 보행환승이 나타나는 심리적 저항감을 적용하는 방안을 강구하였다. 저항 파라메타의 값이 증가할수록 (0~25) 연속된 보행환승을 회피하는 상황의 모사가 가능한 것으로 분석되었다. 특히 수도권 도시철도의 대규모 네트워크 및 OD를 통 해서 Turn Label 기반 최적경로탐색의 활용 부분까지 합리적으로 검토되었다고 평가된다.

Figure

<Fig. 1>.

Difference Between Node & Link Labels

<Fig. 2>.

Turn Label & Cost Structure

<Fig. 3>.

Concept of Node Label Based Optimal Path Detection

<Fig. 4>.

Concept of Vine Based Optimal Path Detection

<Fig. 5>.

Concept of Link Label Based Optimal Path Detection

<Fig. 6>.

Concept of Turn Label Based Optimal Path Detection

<Fig. 7>.

Concept of Turn Label Based Optimal Path Detection

<Fig. 8>.

Cost Structure of dTxTy

<Fig. 9>.

Network Transformation Using Dummy Nodes and Links

<Fig. 10>.

4-Node-4 Link Network and Network Transformation

<Fig. 11>.

Generation of Node Cyclic Path

<Fig. 12>.

Generation of Link Cyclic Path

<Fig. 13>.

Seoul Metropolitan Urban Railway Network and Transfer Stations

Table

<Table 1>.

Turn Label Detection Process for One Link

Tx	Ty	Cost	Back Turn
-	ⓡ-a-ⓢ	Δa	-
ⓡ-a-ⓢ	-

<Table 2>.

Turn Label Setting Based Optimal Detection Process

<Table 3>.

Smart Card ID and Station Name and Line

<Table 4>.

Link Data (Δ_b, minutes)

<Table 5>.

Pedestrian Transfer Time (W_ab ,W_bc, minutes)

<Table 6>.

Headway of Urban Railroad Line (H_b, minutes)

<Table 7>.

Trip Chains with Railroad Trip(S) in Smart Card Data (2022.5.31, Tuesday)

Sequence	Trip Chain	Count	Sequence	Trip Chain	Count
1	S	5934399	21	BSS	603
2	BS	1028076	22	BBSBB	525
3	SB	982691	23	SSB	471
4	BSB	219220	24	SBBSB	470
5	SBB	37342	25	BBBBS	401
6	BBS	28370	26	SBBBS	223
7	BSBB	7963	27	SBSBB	197
8	BBSB	6384	28	SBSBS	159
9	SBS	5194	29	BBSBS	99
10	SBBB	3515	30	BSSB	76
11	SS	3458	31	SSBB	9
12	BBBS	2171	32	BSSBB	4
13	SBBS	2090	33	SSS	4
14	SBSB	1272	34	BBSS	2
15	BSBBB	1115	35	SSSB	2
16	BSBS	1110	36	BBSSB	2
17	BBBSB	724	37	BSSS	2
18	SBBBB	685	38	SSBBS	1
19	BSBBS	666	39	BSSBS	1
20	BSBSB	608	40	SSBBB	1

<Table 8>.

Assigned Trip with Psychological Resistance Parameter (β)

β	υTxTy	B/A*100 (%)
0	61521664	314875	0.51181
1	62078552	50894	0.08198
3	62175224	9830	0.01581
5	62189919	6145	0.00988
10	62209664	2052	0.00330
15	62217010	134	0.00022
20	62218433	17	0.00003
25	62232332	0	0.00000

Reference

Bellman, R. (1957), On the Theory of Dynamic Programming, Princeton University Press, Princeton.
Caldwell, T. (1961), “On Finding Minimum Routes in a Network With Turn Penalties”, Communications of the ACM, vol. 4, no. 2, pp.107-108.
Choi, K. (1995), “Network Representation Schemes for U-Turn and Implementation in the Vine-Based Dijkstra Shortest Path Algorithm”, Korean Society of Transportation, vol. 13, no. 3, pp.35-52.
Dial, R. (1969), “Algorithm 350: Shortest Path Forest with Topological Ordering”, Journal of the Association for Computing Machinery, vol. 12, pp.632-633.
Dial, R. , Glover, F. , Karney, D. and Klingman, D. (1979), “A Computational Analysis of Alternative Algorithms and Labeling Techniques for Finding Shortest Path Trees”, Networks, vol. 9, no. 3, pp.215-248.
Dijkstra, E. W. (1959), “A Note on Two Problems in Connexion with Graphs”, Numerische Mathematik, vol. 1, pp.269-271.
Kirby, R. F. and Potts, R. B. (1969), “The Minimum Route Problem for Networks with Turn Penalties and Prohibition”, Transportation Research, vol. 3, pp.397-408.
Lee, M. (2004), Transportation Network Models and Algorithms Considering Directional Delay and Prohibitions for Intersection Movement, Ph.D. Dissertation, University of Wisconsin at Madison.
Moore, E. F. (1957), The Shortest Path through A Maze, Harvard University Press, Cambridge.
Noh, J. and Namgoong, S. (1995), “Development of Shortest Path Finding Technique for Urban Transportation Network”, Journal of Korea Planning Association, vol. 30, no. 5, pp.153-167.
Thomas, R. (1991), Traffic Assignment Technique, Avebury Technical, Academic Publishing Group.

β	υTxTy		B/A*100 (%)
β	Total Assigned Trip : (A)	(Wab > 0, Wbc > 0) : (B)	B/A*100 (%)
0	61521664	314875	0.51181
1	62078552	50894	0.08198
3	62175224	9830	0.01581
5	62189919	6145	0.00988
10	62209664	2052	0.00330
15	62217010	134	0.00022
20	62218433	17	0.00003
25	62232332	0	0.00000

SITE MAP

Development of A Turn Label Based Optimal Path Search Algorithm

Abstract

Turn Label 기반 최적경로탐색 알고리즘 개발

초록

Ⅰ. 서 론

<Fig. 1>

<Fig. 2>

Ⅱ. 선행연구 고찰

1. 노드표지(Node Label) 기반 최적경로탐색

<Fig. 3>

2. 덩굴망(Vine) 기반 최적경로탐색

<Fig. 4>

3. 링크표지(Link Label) 기반 최적경로탐색

<Fig. 5>

Ⅲ. Turn Label 기반 최적경로탐색 알고리즘

1. 이론적 기반

<Fig. 6>

<Fig. 7>

2. 비용구조 확장( d T x T y ) 사례 검토

<Fig. 8>

3. Turn Label 확정 해법

<Fig. 9>

<Table 1>

<Fig. 10>

<Table 2>

4. Node 및 Link 순환경로 제거

<Fig. 11>

<Fig. 12>

Ⅳ. 사례연구

1. 수도권 도시철도망과 교통카드기반 자료 통행함수

<Table 3>

<Fig. 13>

<Table 4>

<Table 5>

<Table 6>

<Table 7>

2. 시나리오 평가

<Table 8>

Ⅴ. 결 론

Figure

Table

Reference

저자소개

Footnote

AUTHOR CHECK LIST

COPYRIGHT TRANSFER AND RESEARCH ETHICS FORM

ADOBE ACROBAT READER

2. 비용구조 확장( $d_{T_{x} T_{y}}$ ) 사례 검토