Journal of the Korean Society of Civil Engineers Vol. 38, No. 6: 941947/ December, 2018 DOI: https://doi.org/10.12652/ksce.2018.38.6.0941 Transportation Engineering ISSN 10156348 (Print) ISSN 2287934X (Online) www.kscejournal.or.kr 교통공학 역사환승페널티를고려한링크표지기반최적경로탐색 교통카드기반철도네트워크를중심으로 이미영 * Lee, Mee Young* Link LabelBased Optimal Path Algorithm Considering Transfer Penalty Focusing on A Smart Card Based Railway Network ABSTRACT transfers for smart card based railway networks refer to transfer pedestrian movements that occur at the origin and destination nodes rather than at a middle station. To calculate the optimum path for the railway network, a penalty for transfer pedestrian movement must be included in addition to the cost of withincar transit time. However, the existing link labelbased path searching method is constructed so that the station transfer penalty between two links is detected. As such, station transfer penalties that appear at the origin and destination stations are not adequately reflected, limiting the effectiveness of the model. A ghost node may be introduced to expand the network, to make up for the station transfer penalty, but has a pitfall in that the link labelbased path algorithm will not hold up effectively. This research proposes an optimal path search algorithm to reflect station transfer penalties without resorting to enlargement of the existing network. To achieve this, a method for applying a directline transfer penalty by comparing Ticket Gate ID and the line of the link is proposed. Key words : Ticket Gate ID, BigNode, transfer penalty, Link labelbased path searching 초록교통카드기반도시철도네트워크에서역사환승은중간환승역이아닌출발역과도착역의노드에서발생하는환승보행이동을의미한다. 철도네트워크에서최적의경로를탐색하기위해서는차내통행시간이외에환승보행이동에대한페널티를반영하는방안이요구된다. 그러나기존링크표지기반경로탐색기법은링크와링크의사이에서나타나는환승페널티가인식되도록설계되었다. 따라서출발역과도착역에서나타나는역사환승페널티를반영하지못하는한계가발생한다. 역사환승페널티를반영하기위해가상링크를도입하여네트워크를확장하는방안이있으나링크표지기반알고리즘을효과적으로유지하지못하는단점이발생된다. 본연구는역사환승페널티를반영하기위하여네트워크확장없이최적경로를탐색하는알고리즘을제안한다. 이를위해단말기ID와링크의노선을비교하여노선환승페널티를직접적용하는방안을제안한다. 검색어 : 교통카드단말기 ID, 빅노드, 역사환승패널티, 링크표지기반경로탐색 * 정회원 교신저자 국토연구원책임연구원 (Corresponding Author Korea Research Institute for Human Settlements mylee@krihs.re.kr) Received October 8, 2018/ revised October 23, 2018/ accepted November 6, 2018 Copyright c 2018 by the Korean Society of Civil Engineers This is an Open Access article distributed under the terms of the Creative Commons Attribution NonCommercial License (http://creativecommons.org/licenses/bync/3.0) which permits unrestricted noncommercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
역사환승페널티를고려한링크표지기반최적경로탐색 교통카드기반철도네트워크를중심으로 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로구축된철도네트워크를역사환승의관점에서검토하고네트워크확장없이역사환승페널티를반영하기위한우회방안을제안한다. 본연구의주요관점은사전에구축된노선환승페널티를선별하여역사환승페널티로착안하는방안이다. 단말기 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개의방향노선링크 (a) Three Lines of Ticket Gate ID 2. 이론적배경 2.1 카드단말기 ID 와철도네트워크 수도권에서사용되는교통카드자료는철도역사의승객이동을 (b) Transfer Movement Fig. 1. Three Lines Ticket Gate ID of Express Bus Terminal 942 Journal of the Korean Society of Civil Engineers
이미영 여기서, ( ) 는출발역 r의링크 a(b) 의도착지점까지최소시간 ; 는링크 a에서링크 b의환승이동시간 는링크 b의열차배차간격 ; 는링크 b InVehicle 통행시간 ; 는링크 a에서유출링크집합 ; ( ) 는 r(s) 이출발 ( 도착 ) 노드인유출 ( 유입 ) 링크집합 ; ( ) 는승차역r( 하차역 s) 접근 ( 이탈 ) 시간으로 3분 Fig. 2. Link Expression Centering to Express Bus Terminal (Directed Line Link, 이하링크 ) 의관계를보여준다. 노선환승은링크와링크에서노선이달라서보행환승이필요한경우를의미한다. 예를들면, 9호선 신반포 역에서 7호선 반포 역으로환승하는상황에서 9호선열차를하차하고보행으로 7호선승강장까지이동한후 7호선열차를탑승하는사례이다. 링크탐색을적용하여빅노드의역사환승페널티를반영하는가장기초적인검토는단말기ID와역사ID의노선정보를보유한가상링크 (Dummy Link) 로연결하는방법이다. Fig. 4와확장네트워크에대하여 Eq. (2) 의적용을통해링크탐색의구현이가능하다. 그러나네트워크확장을최대한억제하는측면에서링크탐색의장점이상쇄되는문제에봉착하게되며역사환승을위한환승자료의구축이요구되는문제가발생한다. 2.2 링크표지기반최적경로탐색 Fig. 3은교통카드단말기ID로구축된철도네트워크에서출발지 (r) 부터도착지 (s) 까지 Eq. (1) 의링크탐색과정을보여주고있다. r과 s는각각 3개의단말기ID를내재한빅노드로인식되어노선이달라서생기는방향별역사환승페널티가반영되지못한다. 그러나 r과 s가아닌중간환승역사인 j역사 링크a(i,j) 와링크b(j,k) 에서발생하는방향별 와 를동시에반영되도록설계되었다. 따라서 r과 s의역사환승페널티는 에한정되어나타난다. Fig. 4. Network Expansion of BigNode min (2) s.t. 여기서, 는단말기 ID 에서링크 b 의도착지점까지최소시간 Fig. 3. Link LabelBased Railway Network min (1) s.t. 2.3 환승페널티를반영하기위한노드표지및링크표지기반알고리즘 일반적으로대중교통에서의환승페널티의명칭은도시부교차로의회전페널티와동일하게해석된다. 최적경로선택알고리즘에서회전페널티를반영하는방안으로노드표지와링크표지의활용으로구별된다. 노드표지기반최적경로알고리즘은회전페널티를반영하기위해한번에 3개의노드표지를검색하는방안이다. Choi(1995) 는노드 Vol.38 No.6 December 2018 943
역사환승페널티를고려한링크표지기반최적경로탐색 교통카드기반철도네트워크를중심으로 표지에근거하여회전금지가존재하는교차로에서유턴 (UTurn) 을포함하는알고리즘을제시하였다. 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와연결링크의두노선을비교하여노선환승페널티의환승이동시간 ( ) 을역사환승페널티로적용한다. 고속터미널 역역사환승사례의 Fig. 5와같이역사환승은환승시설이용에있어노선환승과거의동일하다. 3.2 역사환승페널티를반영한링크탐색역사환승페널티를노선환승페널티로직접적용하는방법은 Eq. (3) 과같다. 제약조건으로단말기ID와링크의노선정보를나타내는,,, 에대하여비교를통해역사환승페널티 ( ) 의검색이가능하다. min (3) s.t. if if 여기서,, 는각각단말기ID, 노선 ;, 는각각링크 a, b 노선 ; 4. 사례연구 4.1 네트워크및구축효과 2017년 10월기준으로배포된교통카드자료에포함된교통카드단말기ID를대상으로사례연구를시행한다. 단말기 ID는총 688개가운영되고있으며이중빅노드는 588개로구축되었다. 복수의단말기ID가운영되는환승역은 80개로구축되었다. 빅노드로연결된링크는 1,332개빅노드를중심으로방향을나타내는회전은 2,132개이며이중노선환승은 824개로구축된다. Tables 1~4는각각교통카드단말기ID, 링크, 노선환승페널티 ( ), 노선별배차시간 ( ) 을나타내고있다. 제안된알고리즘의효율성은네트워크의확장이필요하지않은측면에서가장크게작용된다. Table 2와 Table 3은역사명을빅노드로구축한링크와노선환승페널티를나타내고있다. 그러나단말기ID로전환되는상황에서가상링크와가상링크를기반으로노선환승페널티를반영하는별도의작업이요구되며불필요한수작업을동반하게된다. 이러한장점은 Fig. 6의복잡한수도권철도 Table 1. Smart Card Ticket Gate ID Terminal ID Name Railway Line 0152 1846 Jonggak Suwon Line 1 Bundang Line Table 2. Links Connected by Two BigNodes Departure Arrival Travel Time (min.) Railway Line Fig. 5. Links Connected to Departure and Arrival BigNode Noryangjin City Hall Daebang Euljiro 1 ga 2.5 2.0 Kyungbu Line Line 2 944 Journal of the Korean Society of Civil Engineers
이미영 Table 3. Transfer Penalty Between Lines ( ) From Transfer To 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 ( ) Line Line 1 ULine Headway (min.) 3.7 5.5 Fig. 7. Case Study Process using Smart Card Data ( ) 를산정하고 2) 역사환승수요를제안된링크탐색기법을적용하여산정한다. (B) 수도권철도네트워크전체를대상으로본연구에서제안하는링크표지기반알고리즘을수행하여역사환승횟수를추정한다. 이때기존알고리즘에서나타나는노선환승횟수를파악하고본연구에서새롭게도출되는역사환승횟수를비교하여수도권철도네트워크의환승횟수에대한변화를파악한다. Fig. 6. Seoul Metropolitan Railway Network 노선도에민자노선의진입으로네트워크가계속확장되고있는상황에서나타난다. 향후링크탐색이철도를포함한통합대중교통체계를운영하는핵심알고리즘으로지속적인활용이필요한상황을고려할때네트워크를최대한가볍고단순하게유지하는방안이요구되며, 본연구는이러한방향에서적합한해법을제안했다. 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) 으로나타나는수요 86개철도환승역사서울역, 시청, 종로3 가, 동대문, 신설동, 청량리, 동묘앞, 을지로3 가, 을지로 4가, 동대문역사문화공원, 신당, 왕십리, 건대입구, 잠실, 종합운동장, 선릉, 강남, 교대, 사당, 대림, 신도림, 영등포구청, 당산, 합정, 홍대입구, 충정로, 연신내, 불광, 충무로, 약수, 옥수, 고속터미널, 양재, 도곡, 수서, 가락시장, 오금, 노원, 창동, 성신여대입구, 삼각지, 이촌, 동작, 총신대입구, 용산, 노량진, 신길, 가산디지털단지, 금정, 수원, 부평, 주안, 인천, 온수, 석계, 도봉산, 회룡, 오이도, 복정, 강남구청, 선정릉, 모란, 정자, 이매, 기흥, 대곡, 회기, 상봉, 망우, 효창공원앞, 공덕, 디지털미디어시티, 김포공항, 계양, 검암, 원인재, 판교, 까치산, 여의도, 청구, 군자, 천호, 보문, 태릉입구, 부평구청, 인천시청 4.3 시나리오 (A) 본절은복수노선이환승하는 86개환승역사에서상호통행을연계하는상황을가정하여본연구에서제시하는링크표지기반알고리즘을토대로역사환승횟수의변화를파악한다. Table 5에서 를내림차순으로정리한총결과로서 7,113 rs쌍에 1,015,111(trip) 으로전체철도통행 8,369,938(trip) 의 12.1% 를차지하고있다. 를출발역 r과도착역 s에대하여역사내이동은직승직하 ( 동일노선열차승하차및교통카드단말기 ) Vol.38 No.6 December 2018 945
역사환승페널티를고려한링크표지기반최적경로탐색 교통카드기반철도네트워크를중심으로 Table 5. Transfer Ration to Demand between r and s No. r s 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 6. Highest Frequency of Non Transfer ( ) r s Gangnam Jamsil 6,814 3,704 2,822 24 264 Table 7. Highest Frequency of Departure Transfer ( ) r s Jamsil Gangnam 6,915 2,612 3,677 299 327 Table 8. Highest Frequency of Arrival Transfer ( ) r s Gangnam Seolleung 3,429 798 1,436 314 701 Table 9. Highest Frequency of Departure & Arrival Transfer ( ) r s Pangoy Gangnam 3,233 435 391 17 2,390 보행통행, 역사환승보행통행으로구분하면다음과같이 4개 1) r과 s의직승직하 ( ), 2) r의역사환승 s의직승직하 ( ), 3) r의직승직하 s의역사환승 ( ), 4) r과 s의역사환승 ( ) 통행조합이나타난다. 이들통행비율은 15.7%, 51.5%, 3.8%, 28.0% 로각각나타난다. 역사환승에의한환승횟수변화는 1,129,240건 (=522,440+38,700+(2*284,050)) 으로승객1인당역사환승은 1.1( 회 ) 로나타나고있다. Table 5의 에대하여,,, 의최고빈도를보여주는 rs쌍에대한결과는각각 Tables 6~9와같다. Table 6에서최대 는 강남 과 잠실 역간 3,704(trip) 로나타나며 역사환승은 2,822+24+(2*264)=3,374( 건 ) 으로나타난다. Table 7 은최대 는 잠실 과 강남 역간 3,677(trip) 로나타나며역사환승은 3,677+299+(2*327)=4,630( 건 ) 으로나타난다. Table 8은최대 는 강남 과 선릉 역간 314(trip) 로나타나며역사환승은 1,436+314+(2*701)=3,152( 건 ) 으로나타난다. Table 9은최대 는 판교 와 강남 역간 2,390(trip) 로나타나며역사환승은 391+17+(2*2,390)=5,188( 건 ) 으로나타난다. 4.4 시나리오 (B) 본절은모든빅노드 588개의상호통행의연계상황을가정하여 946 Journal of the Korean Society of Civil Engineers
이미영 Table 10. Change of Number of Transfer Considering All rs Pairs All Ticket Gate ID (r s) Number of Line Transfer (4,956,921) r s q rs f Change of Number of Transfer f r f s f rs 592,406+600,749+(2*73,403)=1,339,961 8,369,938 7,103,380 592,406 600,749 73,403 본연구에서제시하는링크표지기반알고리즘을토대로역사환승횟수의변화를파악한다. 수도권철도통행전체 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( 회 ) 로변화된다. 5. 결론 교통카드단말기ID기반철도네트워크에서역사환승은출발역과도착역에서나타나는환승을위한보행이동이필요한상황을의미한다. 링크표지기반경로탐색은출발지와도착지를노드로인식하기때문에출발지와도착지에서발생하는역사환승비용을반영하지못하는문제가존재한다. 이문제를극복하기위해서는모든역사에서단말기ID와역명노드를링크로인식하는가상링크의도입을통한네트워크확장이필요하다. 그러나네트워크확장은링크표지기반알고리즘에적합한활용의한계를노출시킨다. 특히수도권철도네트워크와같이복수운영기관마찰, 노선명혼재, 신규교통수단진입, 완 / 급행운영체계, 환승할인요금체계의다양화문제를고려할때링크표지기반알고리즘의효과적정립체계는수도권통합대중교통체계의분석지원을위해매우중요하다. 본연구는네트워크확장없이출발역과도착역에서나타나는역사환승페널티를링크표지기반경로탐색에반영하기위한방안을제안했다. 이를위해단말기ID와연결링크노선을비교하여일치되는노선환승페널티를적용하는방안을제안했다. 수도권철도네트 워크를토대로사례연구를수행하여역사환승페널티를고려하여링크표지기반최적경로탐색이효과적으로적용될수있음을예시하였다. 특히기존의 0.59( 회 ) 의수도권철도네트워크노선환승횟수에서역사환승을반영하여 0.75( 회 ) 까지환승횟수변화를고려하는것이타당함을링크표지기반알고리즘의개선과함께추가적으로입증하였다. References Choi, K. C. (1995). Network representation schemes for UTURN and implementation in the vinebased dijkstra shortest path algorithm. Journal of Korean Society of Transportation, Vol. 13, No. 3, pp. 3552 (in Korean). Gabriel, S. and Bernstein, D. (1997). The traffic equilibrium problem with nonadditive path costs. Transportation Science, Vol. 20, No. 5, pp. 337348. Kirby, R. F. and Potts, R. B. (1969). The minimum route problem for networks with turn penalties and prohibitions. Transportation Research 3, pp. 397408. Lee, M. Y. (2004). Transportation network models and algorithms considering directional delay and prohibitions for intersection movement. Ph.D. Thesis, University of Wisconsin at Madison. Lee, M. Y. (2017). Transportation card based optimal msimilar paths searching for estimating passengers route choice in seoul metropolitan railway network. The Journal of The Korea Institute of Intelligent Transport Systems, Vol. 16, No. 2, pp. 112. Namgeung, S., Rho, J. H. and Choi, J. J. (1998). Development of the treebased pathfinding in urban transportation networks. Mathl. Comput. Modelling, Vol. 27, No. 911, pp. 5165. Shin, S. I. and Baek, N. C. (2016). A logit type of public transit trip assignment model considering stepwise transfer coefficients. Journal of Korean Society of Transportation, Vol. 34, No. 6, pp. 570579 (in Korean). Vol.38 No.6 December 2018 947