1. 서 론

링크표지기반최적경로탐색(이하 링크탐색)은 이전링크(Previous Link)에서 다음링크(Next Link)로 표지확정과정(Lee, 2004)이 진행된다. 따라서 링크탐색은 네트워크를 확장하지 않고 링크-링크 사이에 존재하는 회전페널티를 반영할 수 있다. 그러나 이전노드(Previous Node)에서 다음노드(Next Node)로 표지확정(Dijkstra, 1958)이 진행되는 노드표지기반최적경로탐색(이하 노드탐색)은 네트워크확장을 통해 회전페널티를 반영할 수 있다. 이러한 링크탐색의 장점은 교차로 회전페널티와 도시철도 환승페널티를 반영한 정보제공에 효과적으로 활용된다. 링크탐색을 활용하여 교차로 신호시간 또는 회전금지(Kirby and Potts, 1969; Lee, 2004)를 고려하거나 도시철도의 환승시간 또는 환승가중치(Gabriel and Bernstein, 1997; Shin and Baek, 2016; Lee, 2017)를 반영하여 최적해의 도출이 가능하다.

철도는 노선환승과 역사환승에 대한 관점에서 링크탐색의 추가적인 검토가 요구된다. 링크탐색의 적용은 노선환승에만 적용이 가능하다. 노선환승은 열차승차와 열차하차의 간격에서 보행이동시간과 차량대기시간으로 표현되므로 역→역→역(노드→노드→노드)의 노선환승이 링크-링크로 처리된다. 그러나 역사환승의 경우 환승이 노드인 역사내에서 발생하기 때문에 역-역(노드→노드)의 단일 링크에서 환승을 고려하는 문제이다. 이는 가상링크를 구축하여 *→역→역(*→노드→노드)으로 네트워크확장을 유도하게 되며 따라서 링크탐색을 효과적으로 활용하지 못하는 한계가 발생한다.

이러한 문제는 특히 교통카드자료의 단말기ID(Ticket Gate ID)를 기반으로 구축되는 수도권철도경로탐색에서 확인되었다. 철도환승역은 노드로 인식되는 역사내부에서 환승이 발생하기 때문에 링크탐색에 역사환승페널티를 반영하는 정확한 해법이 적용되지 않는다. 교통카드자료기반 철도네트워크에서 최적경로탐색은 보행승객이동성평가 및 운임정산과 같은 이슈에서 중요한 가치를 지니고 있다.

본 연구는 교통카드자료를 기반으로 구축된 철도네트워크에서 역사환승패널티를 반영하는 링크탐색 알고리즘을 구축한다. 이를 위해 교통카드단말기ID로 구축된 철도네트워크를 역사환승의 관점에서 검토하고 네트워크확장없이 역사환승페널티를 반영하기 위한 우회방안을 제안한다. 본 연구의 주요관점은 사전에 구축된 노선환승페널티를 선별하여 역사환승페널티로 착안하는 방안이다.

2. 이론적 배경

2.1 카드단말기ID와 철도네트워크

수도권에서 사용되는 교통카드자료는 철도역사의 승객이동을 단말기ID를 통해 인식한다. 예를 들면 단일노선으로 운영되는 ‘구의’역은 ‘0213’, 3개 노선의 환승이 이루어지는 ‘고속터미널’역은 3호선 ‘0329’, 7호선 ‘2736’, 9호선 ‘4123’의 단말기ID로 구축되어 있다. 카드단말기ID로 구축된 철도네트워크에서 ‘고속터미널’역은 3개의 단말기ID를 포함하는 하나의 빅노드(BigNode)로 구축되었다. 여기서 ‘빅노드’란 1) ‘메트로 9호선’의 단말기ID ‘4123’, 2) ‘3호선’의 단말기ID ‘0329’, 3) ‘7호선’의 단말기ID ‘2736’을 ‘고속버스터미널’역 명칭의 단일노드로 지명하는 것을 의미하며, 단말기ID가 하나인 역도 역명칭을 통해 빅노드로 지칭된다.

본 연구의 주제인 역사환승은 단말기ID와 열차승차/하차노선이 다른 상황에서 환승보행을 위한 페널티가 필요한 상황을 의미한다. 예를 들면 카드 TagIn 단말기ID가 ‘4123’이고 초승열차를 7호선에서 탑승하면 ‘9호선’에서 ‘3호선’ 역사를 지나서 ‘7호선’까지 보행으로 이동하고 ‘7호선’승강장에서 열차를 대기하는 시간이 소요된다. 역사환승은 노선환승과 같이 환승통로를 이용하는 측면에서 유사하나, 역사환승은 출발역사 및 하차역사에서 교통카드TagIn/Out과 함께 발생한다. 한편 노선환승은 열차하차, 환승이동대기, 열차승차로서 교통카드Tag관련 행위가 발생하지 않는다.

교통카드 단말기ID로 구축된 빅노드와 빅노드를 연결하면 링크자료가 구축된다. Fig. 1과 Fig. 2는 3개의 노선이 통과하는 ‘고속터미널’역과 인접된 주변부 6개 빅노드와 12개의 방향노선링크(Directed Line Link, 이하 링크)의 관계를 보여준다. 노선환승은 링크와 링크에서 노선이 달라서 보행환승이 필요한 경우를 의미한다. 예를 들면, 9호선 ‘신반포’역에서 7호선 ‘반포’역으로 환승하는 상황에서 9호선열차를 하차하고 보행으로 7호선 승강장까지 이동한 후 7호선 열차를 탑승하는 사례이다.

2.2 링크표지기반 최적경로탐색

Fig. 3은 교통카드단말기ID로 구축된 철도네트워크에서 출발지(r)부터 도착지(s)까지 Eq. (1)의 링크탐색과정을 보여주고 있다. r과 s는 각각 3개의 단말기ID를 내재한 빅노드로 인식되어 노선이 달라서 생기는 방향별 역사환승페널티가 반영되지 못한다. 그러나 r과 s가 아닌 중간환승역사인 j역사 – 링크a(i,j)와 링크b(j,k)에서 발생하는 방향별 T_ab와 H^b를 동시에 반영되도록 설계되었다. 따라서 r과 s의 역사환승페널티는 H^b에 한정되어 나타난다.

$$\begin{array}{l}\pi^{rb}=min(\pi^{ra}+T_{ab}+\frac{H_b}2+c_b,\;\pi^{rb}\left|b\in\Gamma_a^+\right.\\s.t.\;T_{rb}=AccT_r,\;b\in\Gamma_r^+\\\;\;\;\;\;\;\;T_{as}=EggT_s,\;a\in\Gamma_s^-\end{array}$$

(1)

여기서, 𝜋^ra(𝜋^rb)는 출발역 r의 링크 a(b)의 도착지점까지 최소시간;

T_ab는 링크 a에서 링크 b의 환승이동시간

H_b는 링크 b의 열차배차간격; c_b는 링크 b In-Vehicle 통행시간;

${\Gamma }_a^{+}$는 링크 a에서 유출링크집합; ${\Gamma }_r^{+}$( ${\Gamma }_s^{-}$)는 r(s)이 출발(도착)노드인 유출(유입)링크집합;

Acc T_r(Egg T_s는 승차역r(하차역s) 접근(이탈)시간으로 3분

링크탐색을 적용하여 빅노드의 역사환승페널티를 반영하는 가장 기초적인 검토는 단말기ID와 역사ID의 노선정보를 보유한 가상링크(Dummy Link)로 연결하는 방법이다. Fig. 4와 확장네트워크에 대하여 Eq. (2)의 적용을 통해 링크탐색의 구현이 가능하다. 그러나 네트워크확장을 최대한 억제하는 측면에서 링크탐색의 장점이 상쇄되는 문제에 봉착하게 되며 역사환승을 위한 환승자료의 구축이 요구되는 문제가 발생한다.

$$\begin{array}{l}\pi^{r_zb}=min(\pi^{r_za}+T_{ab}+\frac{H_b}2+c_b,\;\pi^{r_zb}\left|b\in\Gamma_a^+\right.\\s.t.\;T_{r_zb}=AccT_r,\;b\in\Gamma_r^+\\\;\;\;\;\;\;\;T_{as_z}=EggT_s,\;a\in\Gamma_s^-\end{array}$$

(2)

여기서, ${\pi }^{r_{z}b}$는 단말기ID r_z에서 링크 b의 도착지점까지 최소시간

2.3 환승페널티를 반영하기 위한 노드표지 및 링크표지기반 알고리즘

일반적으로 대중교통에서의 환승페널티의 명칭은 도시부교차로의 회전페널티와 동일하게 해석된다. 최적경로선택알고리즘에서 회전페널티를 반영하는 방안으로 노드표지와 링크표지의 활용으로 구별된다.

노드표지기반최적경로알고리즘은 회전페널티를 반영하기 위해 한번에 3개의 노드표지를 검색하는 방안이다. Choi(1995)는 노드표지에 근거하여 회전금지가 존재하는 교차로에서 유턴(U-Turn)을 포함하는 알고리즘을 제시하였다. Choi(1995)는 3개의 노드를 표지로 하여 노드(Node), 전노드(Previous Node) 전전노드(Previous Previsou Node)의 개념을 적용하였으며 이때 2개의 인접된 교차로에서 회전페널티가 존재하는 상황에서는 최적조건(Optimality Condition)이 만족되지 못함을 예시하여 설명하였다. 이러한 상황을 우회하기 위한 전략으로 회전페널티가 인접되어 존재하는 도시부네트워크에서 중간노드(Mid Node)를 도입하여 가상노드개념을 적용하였다. 이러한 개념은 궁극적으로 네트워크확장을 유도하게 되며, 무엇보다도 환승역사가 매우 많이 존재하는 수도권철도네트워크에서 알고리즘을 노드기반으로 유지하는 매우 소모적인 노력만 가중시키는 문제가 발생된다.

링크표지기반 최적경로알고리즘은 회전페널티를 반영하기 위해 한번에 2개의 링크표지를 검색하는 방안이다. Kirby and Potts(1969), Namgung et al.(1998), Lee(2004)는 링크표지에 근거하여 회전페널티를 반영하는 방안을 제시하였다. Lee(2004)는 링크표지가 링크(Link)와 전링크(Previous Link)의 링크표지확정(Link Label Setting)을 거치는 상황에서 최적조건이 만족됨을 증명하였으며 노드표지의 개념과 비교하여 설명하였다. 현재 모든 차량내비게이션, 대중교통정보플랫폼은 링크기반알고리즘으로 운영된다고 할 수 있다.

3. 역사환승 페널티를 반영한 링크기반 최적경로탐색

3.1 개요

출발역과 도착역 단말기ID는 이미 노선정보를 포함한다. 단말기ID와 역사ID를 가상링크로 연결하는 것은 노선정보를 가상링크로 구축해서 링크탐색을 시도하는 것이다. 본 연구는 단말기ID와 연결링크의 두 노선을 비교하여 노선환승페널티의 환승이동시간(T_ab)을 역사환승페널티로 적용한다. ‘고속터미널’역 역사환승사례의 Fig. 5와 같이 역사환승은 환승시설 이용에 있어 노선환승과 거의 동일하다.

3.2 역사환승페널티를 반영한 링크탐색

역사환승페널티를 노선환승페널티로 직접 적용하는 방법은 Eq. (3)과 같다. 제약조건으로 단말기ID와 링크의 노선정보를 나타내는 𝛷(r_z), 𝛷(s_z), 𝛷(a), 𝛷(b)에 대하여 비교를 통해 역사환승페널티(T_ab)의 검색이 가능하다.

$$\begin{array}{l}\pi^{r_zb}=min(\pi^{r_za}+T_{ab}+\frac{H_b}2+c_b,\;\pi^{r_zb}\left|b\in\Gamma_a^+\right.\\s.t.\;T_{r_zb}=AccT_r+T_{ab}\;\;if\;\Phi(r_z)=\Phi(a)\;\;b\in\Gamma_r^+\\\;\;\;\;\;\;\;T_{as_z}=T_{ab}+EggT_s\;\;if\;\Phi(b)=\Phi(s_z)\;\;a\in\Gamma_s^-\end{array}$$

(3)

여기서, 𝛷(r_z), 𝛷(s_z)는 각각 단말기ID r_z, s_z 노선; 𝛷(a), 𝛷(b)는 각각 링크 a, b 노선;

4. 사례연구

4.1 네트워크 및 구축효과

2017년 10월 기준으로 배포된 교통카드자료에 포함된 교통카드단말기ID를 대상으로 사례연구를 시행한다. 단말기ID는 총 688개가 운영되고 있으며 이중 빅노드는 588개로 구축되었다. 복수의 단말기ID가 운영되는 환승역은 80개로 구축되었다. 빅노드로 연결된 링크는 1,332개 빅노드를 중심으로 방향을 나타내는 회전은 2,132개이며 이중 노선환승은 824개로 구축된다. Tables 1~4는 각각 교통카드단말기ID, 링크, 노선환승페널티(T_ab), 노선별 배차시간(H_b)을 나타내고 있다.

Table 1. Smart Card Ticket Gate ID

Terminal ID	Station Name	Railway Line
0152 - 1846	Jonggak - Suwon	Line 1 - Bundang Line

Table 2. Links Connected by Two BigNodes

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

Table 3. Transfer Penalty Between Lines (T_ab)

From Station	Transfer Station	To Station	Transfer Time (min.)	From Line	To Line
Yangjae - Songpa	Gangnam - Garak Market	Yeoksam - Suseo	3.5 - 1.8	Sinbundang Line - Line 8	Line 2 - Line 3

Table 4. Headway of Railway Line (H_b)

Line	Headway (min.)
Line 1 - U-Line	3.7 - 5.5

제안된 알고리즘의 효율성은 네트워크의 확장이 필요하지 않은 측면에서 가장 크게 작용된다. Table 2와 Table 3은 역사명을 빅노드로 구축한 링크와 노선환승페널티를 나타내고 있다. 그러나 단말기ID로 전환되는 상황에서 가상링크와 가상링크를 기반으로 노선환승페널티를 반영하는 별도의 작업이 요구되며 불필요한 수작업을 동반하게 된다. 이러한 장점은 Fig. 6의 복잡한 수도권철도노선도에 민자노선의 진입으로 네트워크가 계속 확장되고 있는 상황에서 나타난다. 향후 링크탐색이 철도를 포함한 통합대중교통체계를 운영하는 핵심알고리즘으로 지속적인 활용이 필요한 상황을 고려할 때 네트워크를 최대한 가볍고 단순하게 유지하는 방안이 요구되며, 본 연구는 이러한 방향에서 적합한 해법을 제안했다.

4.2 일일 교통카드자료분석

2017년 10월 18일 수요일 선/후불 교통카드에서 총 수도권대중교통통행은 20,846,811(trip), 이중 철도통행(S)은 8,369,938(trip)이 나타난다. 철도통행에서 역사환승페널티의 비중을 분석하는 방향으로 2가지 시나리오(A, B)를 Fig. 7의 과정에 따라 추진한다.

(A) 우선 링크표지기반알고리즘을 통하여 복수노선이 존재하는 환승역사간 역사환승횟수를 추정하는 대안을 분석한다. 이를 위해 총 92개 역사를 대상으로 동일노선환승역사 6개(강동, 성수, 금천구청, 병점, 구로, 가좌)를 제외한 86개를 대상으로 1) 출발역(r)과 도착역(s)으로 나타나는 수요(q^rs)를 산정하고 2) 역사환승수요를 제안된 링크탐색기법을 적용하여 산정한다.

(B) 수도권철도네트워크 전체를 대상으로 본 연구에서 제안하는 링크표지기반알고리즘을 수행하여 역사환승횟수를 추정한다. 이때 기존알고리즘에서 나타나는 노선환승횟수를 파악하고 본 연구에서 새롭게 도출되는 역사환승횟수를 비교하여 수도권철도네트워크의 환승횟수에 대한 변화를 파악한다.

86개 철도 환승역사

서울역, 시청, 종로3가, 동대문, 신설동, 청량리, 동묘앞, 을지로3가, 을지로4가, 동대문역사문화공원, 신당, 왕십리, 건대입구, 잠실, 종합운동장, 선릉, 강남, 교대, 사당, 대림, 신도림, 영등포구청, 당산, 합정, 홍대입구, 충정로, 연신내, 불광, 충무로, 약수, 옥수, 고속터미널, 양재, 도곡, 수서, 가락시장, 오금, 노원, 창동, 성신여대입구, 삼각지, 이촌, 동작, 총신대입구, 용산, 노량진, 신길, 가산디지털단지, 금정, 수원, 부평, 주안, 인천, 온수, 석계, 도봉산, 회룡, 오이도, 복정, 강남구청, 선정릉, 모란, 정자, 이매, 기흥, 대곡, 회기, 상봉, 망우, 효창공원앞, 공덕, 디지털미디어시티, 김포공항, 계양, 검암, 원인재, 판교, 까치산, 여의도, 청구, 군자, 천호, 보문, 태릉입구, 부평구청, 인천시청

4.3 시나리오(A)

본 절은 복수노선이 환승하는 86개 환승역사에서 상호통행을 연계하는 상황을 가정하여 본 연구에서 제시하는 링크표지기반알고리즘을 토대로 역사환승횟수의 변화를 파악한다.

Table 5에서 q^rs를 내림차순으로 정리한 총 결과로서 7,113 r-s쌍에 1,015,111(trip)으로 전체 철도통행 8,369,938(trip)의 12.1%를 차지하고 있다. q^rs를 출발역 r과 도착역 s에 대하여 역사내이동은 직승직하(동일노선열차승하차 및 교통카드단말기)보행통행, 역사환승보행통행으로 구분하면 다음과 같이 4개 – 1) r과 s의 직승직하(f^--), 2) r의 역사환승 s의 직승직하(f^r-), 3) r의 직승직하 s의 역사환승(f^-s), 4) r과 s의 역사환승(f^rs) – 통행조합이 나타난다. 이들 통행비율은 f^-- 15.7%, f^r- 51.5%, f^-s 3.8%, f^rs 28.0%로 각각 나타난다. 역사환승에 의한 환승횟수변화는 1,129,240건(=522,440+38,700+(2*284,050))으로 승객1인당 역사환승은 1.1(회)로 나타나고 있다.

Table 5. Transfer Station Ration to Demand between r and s

No.	r	s	qrs	f
				f--	fr-	f-s	frs
1	Jamsil	Gangnam	6,915	2,612	3,677	299	327
2	Gangnam	Jamsil	6,814	3,704	2,822	24	264
3	Seolleung	Gangnam	4,329	1,429	2,479	193	228
4	Gangnam	Sadang	4,233	1,251	985	145	1,852
	-	-	-
7113	Gangnamgu office	Daegok	1	0	1	0	0
Total Sum			1,015,111 (100.0%)	169,921 (15.7%)	522,440 (51.5%)	38,700 (3.8%)	284,050 (28.0%)

Table 5의 q^rs에 대하여 f^--, f^r-, f^-s, f^rs의 최고빈도를 보여주는 r-s쌍에 대한 결과는 각각 Tables 6~9와 같다. Table 6에서 최대 f^--는 ‘강남’과 ‘잠실’역간 3,704(trip)로 나타나며 역사환승은 2,822+24+(2*264)=3,374(건)으로 나타난다. Table 7은 최대 f^r-는 ‘잠실’과 ‘강남’역간 3,677(trip)로 나타나며 역사환승은 3,677+299+(2*327)=4,630(건)으로 나타난다. Table 8은 최대 f^-s는 ‘강남’과 ‘선릉’역간 314(trip)로 나타나며 역사환승은 1,436+314+(2*701)=3,152(건)으로 나타난다. Table 9은 최대 f^rs는 ‘판교’와 ‘강남’ 역간 2,390(trip)로 나타나며 역사환승은 391+17+(2*2,390)=5,188(건)으로 나타난다.

Table 6. Highest Frequency of Non Station Transfer (f^--)

r	s	qrs	f
			f--	fr-	f-s	frs
Gangnam	Jamsil	6,814	3,704	2,822	24	264

Table 7. Highest Frequency of Departure Station Transfer (f^r-)

r	s	qrs	f
			f--	fr-	f-s	frs
Jamsil	Gangnam	6,915	2,612	3,677	299	327

Table 8. Highest Frequency of Arrival Station Transfer (f^-s)

r	s	qrs	f
			f--	fr-	f-s	frs
Gangnam	Seolleung	3,429	798	1,436	314	701

Table 9. Highest Frequency of Departure & Arrival Station Transfer (f^rs)

r	s	qrs	f
			f--	fr-	f-s	frs
Pangoy	Gangnam	3,233	435	391	17	2,390

4.4 시나리오(B)

본 절은 모든 빅노드 588개의 상호통행의 연계상황을 가정하여 본 연구에서 제시하는 링크표지기반알고리즘을 토대로 역사환승횟수의 변화를 파악한다. 수도권철도통행 전체 8,369,938(건)에서 노선환승은 4,956,921(건)으로 개인승객당 노선환승은 4,956,921/ 8,369,938=0.59(회)로 나타난다. 역사환승은 출발역사환승 592,406 (건), 도착역사환승 600,749(건), 출발/도착역사환승 73,403(건)으로 나타나 총 역사환승은 1,339,961(건)으로 Table 10과 같이 산정되었으며 개인승객당 역사환승은 1,339,961/8,369,938=0.16(회)로 나타난다. 따라서 수도권철도네트워크에서 기존 0.59(회)에서 역사환승횟수를 고려하면 0.75(회)로 변화된다.

Table 10. Change of Number of Transfer Considering All r-s Pairs

All Ticket Gate ID (r - s)

Number of Line Transfer (4,956,921)

Change of Number of Transfer

r

s

qrs

f

f--

f r→

→ fs

f rs

592,406+600,749+(2*73,403)=1,339,961

8,369,938

7,103,380

592,406

600,749

73,403

5. 결 론

교통카드단말기ID기반 철도네트워크에서 역사환승은 출발역과 도착역에서 나타나는 환승을 위한 보행이동이 필요한 상황을 의미한다. 링크표지기반경로탐색은 출발지와 도착지를 노드로 인식하기 때문에 출발지와 도착지에서 발생하는 역사환승비용을 반영하지 못하는 문제가 존재한다. 이 문제를 극복하기 위해서는 모든 역사에서 단말기ID와 역명노드를 링크로 인식하는 가상링크의 도입을 통한 네트워크확장이 필요하다. 그러나 네트워크확장은 링크표지기반알고리즘에 적합한 활용의 한계를 노출시킨다. 특히 수도권철도네트워크와 같이 복수운영기관 마찰, 노선명 혼재, 신규교통수단 진입, 완/급행운영체계, 환승할인요금체계의 다양화 문제를 고려할 때 링크표지기반알고리즘의 효과적 정립체계는 수도권통합대중교통체계의 분석지원을 위해 매우 중요하다.

본 연구는 네트워크확장없이 출발역과 도착역에서 나타나는 역사환승페널티를 링크표지기반경로탐색에 반영하기 위한 방안을 제안했다. 이를 위해 단말기ID와 연결링크노선을 비교하여 일치되는 노선환승페널티를 적용하는 방안을 제안했다. 수도권철도네트워크를 토대로 사례연구를 수행하여 역사환승페널티를 고려하여 링크표지기반최적경로탐색이 효과적으로 적용될 수 있음을 예시하였다. 특히 기존의 0.59(회)의 수도권철도네트워크노선 환승횟수에서 역사환승을 반영하여 0.75(회)까지 환승횟수변화를 고려하는 것이 타당함을 링크표지기반알고리즘의 개선과 함께 추가적으로 입증하였다.