2013 년도한국철도학회추계학술대회논문집 KSR2013A263 지능형트립플래너구성을위한최적경로알고리즘및시뮬레이션분석 Development and analysis of the optimized path selection algorithm for intelligent trip planner 안태기 *, 김순희 * TaeKi Ahn *, SunHee Kim * Abstract The intelligent trip planner containing an optimized path selection function is highly required by users as informational equipment such as computer, smart phone and smart pad are spreading rapidly. However, conventional trip planner provided by a government, local government or company have only limited function with basic path searching algorithm for a public or individual transportation system separately. This paper propose a novel path finding algorithm for an optimized path search considering a public transportation system merged with an individual transportation system to maximize user convenience from door to door. Simulation results have been demonstrated to show performance of the proposed algorithm. This developed optimized path selection algorithm is expected to be a base line data for the intelligent trip planner. Keywords : Trip planner, path search, optimized path selection, path finding algorithm 초록컴퓨터, 스마트폰및스마트패드등정보기기의급속한보급으로이용자는최적의경로찾기를포함한지능형트립플래너의기능을요구하고있다. 하지만현재정부, 지자체, 기업등에서제공하고있는트립플래너의기능은대중교통, 개인교통별로길찾기기능을제공하는초보적인수준에머무르고있다. 본논문에서는개인교통과대중교통을병합하여출발지에서목적지까지편의성을고려한최적경로를검색할수있는알고리즘을제안한다. 제안된알고리즘을적용하여시뮬레이션을통한성능을입증하였으며, 지능형트립플래너구현시기초자료로이용할수있을것으로기대한다. 주요어 : 트립플래너, 경로탐색, 최적경로, 길찾기 1. 서론 여행을계획하는이용객들은개인교통과대중교통을이용한다양한경로중가장적절한경로를선택하기를원한다. 인터넷, 스마트폰등폭넓은정보기기의보급은이용객으로하여금보다높은수준의경로찾기서비스를요구하도록하고있다. 현재각종포털사이트를운영하고있는정부, 지자체기관또는기업들은인터넷또는스마트폰을통하여이용객이여행전여정계획을세울수있도록개인교통과대중교통의추천경로및실시간정보등을제공하고있다. 이용객은이러한정보를바탕으로여정계획을세우고여 교신저자 : 한국철도기술연구원광역도시교통연구본부 (tkahn@krri.re.kr) * 한국철도기술연구원광역도시교통연구본부
필요한경우에는실시간변경을통하여여정계획을수정하기도한다. 하지만현재여정계획수립을위한트립플래너의기능은개인교통과대중교통이단절된형태만을제공하고있다. 이용객은출발지에서목적지까지단절없는정보를원하고있으며, 특히개인교통과대중교통을모두이용하는트립플래너에대한요구를만족할수있는서비스는현재제공하지못하고있다. 또한개인교통과대중교통을병합한실제이용객의편의성을고려한최적경로방법에대해서는많은연구가진행되지않고있다. 본논문에서는개인교통과대중교통을병합하고, 이용객의편의성을고려한지능형트립플래너알고리즘을제안하고, 시뮬레이션을통하여알고리즘의효과를제시하였다. 이용객의관점에서편의성을고려하고출발지에서목적지까지전체여정에대한가장최적의여정계획을수립할수있는방법을제시함으로써향후지능형트립플래너설계시많은기여를할수있을것으로기대된다. 2. 본론 2.1 지능형트립플래너트립플래너는여행을하고자하는이용객이관심있는장소를여행하기위하여필요한경로와장소에대한관련정보 ( 개장시간, 폐장시간등 ) 등에대한정보를포함하여여정계획을세울수있도록도와주는도구를의미한다. 현재는이러한트립플래너는웹사이트또는스마트앱등을통하여서울시등일부지역에대하여제공하고있으나아직까지는초보단계에머물고있다. 그림 1은서울을여행할수있는트립플래너 아이투어서울 앱의기능을보여주고있다. Figure 1 Conventional Trip planner I tour seoul as smart phone application
트립플래너는관광명소, 추천코스, 맛집, 숙박, 쇼핑, 공연정보등다양한정보를제공할수있는기능을가질수있지만, 지정된장소까지이동수단에대한정보는가장중요한정보중하나이다. 지능형트립플래너는이용객에게가장최적의여정계획을수립하도록도움을줄수있는시스템으로가장중요한기능중하나는이용객의편의성을고려한구간별최적의이동수단에대한정보를제공하는것이다. 본논문에서는트립플래너의다양한기능중최적의경로를찾아가기위한최적경로기능에대한내용을다루고있다. 스마트폰, 태블릿 PC 등스마트기기의보급이기하급수적으로증가하면서이를활용한다양한길찾기관련애플리케이션또한활발히개발되고있다. 특히, 사용자질의를통해대중교통또는자가용을이용한경로를안내해주는경로탐색애플리케이션은생활과밀접하게사용되어사용자들에게유익하고편리한정보를제공하고있다. 그러나기존의경로탐색애플리케이션에서는경로탐색과정에서대중교통및자가용을복합적으로사용하는사용자에게경제적으로유리한경로탐색정보는제공하지않는단점이있다. 예를들면, 자가용을이용하여지하철역까지이동한후대중교통을이용하여회사까지출근하는사용자일경우, 무료주차장과가까운지하철역또는가장저렴하거나빠르게대중교통으로환승할수있는주차장등의안내를해주는경로탐색애플리케이션은개발되지않은실정이다. 본논문에서는개인교통과대중교통을모두고려하여이용자관점에서의여정계획수립을위한최적경로알고리즘에대한내용에중점을두고있다. 2.2 지능형트립플래너최적경로알고리즘 본논문은개인교통수단과대중교통수단을복합적으로이용하는경로추천알고리즘을제안하고, 편의성및시간경비를고려한환산경비가최소가되는추천경로를제공하는알고리즘을제안한다. 제안된알고리즘은교통망노드, 링크생성알고리즘및경로생성알고리즘, 이용자의사반영알고리즘으로구성되어있으며, 그림 2는이러한알고리즘에대한상세내용을표현하였다. 교통망노드, 링크생성알고리즘은지하철역, 버스정류장, 환승주차장등을개별노드로생성하고동일링크를통행하는모든수단을링크로처리하여개인교통과대중교통을같이병합할수있도록하였다. 경로생성알고리즘은모든링크에대하여최소환산경비를찾는단계로서편의성및시간을고려한경비중최소의경비를가진추천경로를생성하고저장한다. 이용자의사반영알고리즘은생성된추천경로를저장하고있는탐색링크집합에서변경을원하는구간에대하여이용자의사를반영하여경로생성알고리즘의결과를변경하여생성하도록하고, 이용자의사가반영된최종경로를생성하고저장한다.
Figure 2 Optimized path selecting algorithm diagram 그림 3은 KRRI에서서울메트로까지경로에이러한알고리즘을적용한경우를보여주고있다. 그림에나타낸바와같이, 주차장, 지하철역, 버스정거장등을노드로선정하고노드중공통노드를추출하여이러한공통노드를통한추천경로를생성할수있다. 공통노드를통한추천경로가추출되면, 알고리즘은사용자검색조건을반영하여최종경로를생성할수있다. 그림에나타난최종경로를보면, 출발지노드인 KRRI 에서자가용 ( 주차장 ) 을이용하여 경마공원 까지이동한후, 경마공원 에서지하철을타고 사당 까지이동한후목적지노드인 서울메트로 로도보이동했음을알수있다. 여기서, 사용자검색조건은자가용을선호교통수단으로설정하고, 주차장비용이무료이며최소금액으로이동하는조건으로추천경로중자가용을이용한후대중교통으로환승하는경로가선정될수있다. 출발지노드에서자가용을이용한후대중교통으로환승하는경로는 의왕, 경마공원, 사당 및 서울메트로 노드를거치는방법이될수있는데, 사용자검색조건에부합하는무료주차장이 경마공원 에위치하므로, 경마공원 이자가용과지하철의환승지점이될수있다. 그러므로사용자는경마공원역인근에위치한주차장까지자가용으로이동한후, 주차를하고 4호선경마공원역에서지하철을탑승한후사당역에도착할수있다. 이로써, 사용자에게자가용과대중교통을복합적으로이용할수있는경로를안내해줄수있으며이때, 무료주차장과같은이동에따른비용을반영한빠른경로를안내할수있으므로시간과비용을모두고려한효율적이고경제적인경로안내를제공할수있다.
Figure 3 intelligent path searching results for the route from KRRI to Seoul metro. 2.3 지능형트립플래너시뮬레이션제안된알고리즘의효과를확인해보기위해간단한사례를중심으로시뮬레이션을실시하였다. 사례는개인승용차, 버스, 지하철, 환승주차장등이존재하며, 경로탐색구간은한국철도기술연구원 (KRRI)~ 서울메트로사례를연구하였다. 사례는경기도에서서울도심으로이동하는경로이며, 다양한경로들이탐색되게된다. 표1은제안된알고리즘수행결과와국내최대포털업체의웹사이트에서제공하고있는길찾기기능수행결과, Tago에서제공하는대중교통정보기능수행결과를비교하여나타내고있다. 이때편의성및시간경비를고려한환산경비는수식 (1) 과 (2) 에따라계산하였다. 환산비용총계 = 편의성고려한교통비 + 시간비용 (1) 편의성고려한교통비 = 불편계수 * 교통비 (2) 여기서교통비 = 대중교통비 [ 대중교통수단인경우 ] 주차비 + 통행료 + 유류비 [ 개인교통수단인경우 ] 주차비와통행료는구간별실제금액을적용하고, 유류비는 Opnet에서제공하는당일휘발유평균값을적용하였으며, 평균연비는 10km/l를적용하였다. 시간비용은 2013년기준수도권에서의 1시간당통행시간가치인 9,860원 / 인을적용하였다. 불편계수는이용자가교통수단을이용하는경우느끼는불편정도를나타내는계수로서이용자별주관적인계수가될수있으며, 향후이에대한심도있는연구가필요하다. 본시뮬레이션에서는버스를 1.0으로하여상대적인계수를적용하였으며, 지하철은 0.9, 개인교통은 0.2를적용하여시뮬레이션을수행하였다. 시뮬레이션에서환승및도보관련한시간경비, 개인교통의감가상각비등은포함하지않았으며, 보다자세한비용산정에관련해서는향후연구가진행되어야할사항이다.
Table 1 cost efficiency analysis of the optimized path searching algorithm ( 단위 : 분, 원 ) 비용 환산비용 구분 통행시간교통비유류비편의성고려환산비용 시간고려환산비용 환산비용 총계 절감율 대중추천 88 1,100-1,100 14,461 15,561 43% 개인추천 39 27,800 4,522 6,464 6,409 12,873 31% 제안 42 1,950 3,971 2,004 6,902 8,906 주 ) 대중추천 : 대중교통수단탐색경로, 개인추천 : 개인교통수단 ( 승용차 ) 탐색경로 제안 : 복수수단교통망최적탐색경로 표 1에서보는바와같이제안된방법은개인교통또는대중교통을단독으로이용하는경우보다약 30~40% 이상의환산경비절감효과를볼수있다. 또한제안된시뮬레이션결과는제안된알고리즘이이용자의노하우를반영하는경우이용자의환산경비절감과편의성향상에도움이될수있다는것을보여주고있다. 3. 결론본논문에서는개인교통과대중교통을병합하고, 편의성및시간경비를고려한환산경비를최소화할수있는경로생성알고리즘에대하여제안하였다. 제안된알고리즘은향후이용자의노하우를반영하여출발지에서목적지까지 D2D(Door-to-Door) 의최적여정계획을수립할수있는기초가될것으로기대한다. 참고문헌 [1] 김현명, 임용택, 유전알고리듬을이용한전역탐색최단경로알고리듬개발, 대한교통학회지, 제17권 2호, pp.163~178, 1999 [2] 최기주, U-Turn을포함한가로망표현및최단경로의구현, 대한교통학회지제 13권 3호, pp.35~52, 1997 [3] Abbaspour R. A., Samadzadegan F., An evolutionary solution for multimodal shortest path problem in metropolies, Comsis Vol.7 No.4, 2010 [4] Huguet M-J, Kirchler D., Parent P., Calvo R. W., 2way multi Modal Shortest path problem, Tristan 2013