환승 저항을 고려한 운행시간표 기반 대중교통 다중 경로 탐색 알고리즘
A schedule-based Public Transit Routing Algorithm for Finding K-shortest Paths Considering Transfer Penalties
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
운행시간표 기반 대중교통 경로 탐색 알고리즘은 운행계획에 따른 정류장별 출·도착 시각을 이용하여 최소 이동 시간이 소요되는 단일 경로를 산출한다. 다만, 경로 계산 과정에서환승 저항, 대안 경로 선택 등의 추가 요소들을 반영하는데 한계가 있다. 본 연구는 환승 저항 및 다중 경로 탐색이 반영된 개선된 RAPTOR 알고리즘을 제안한다. 환승 저항은 환승 시점에 적용되며, 교통수단 유형을 구분하여 적용하였다. 본 연구에서는 수도권 대중교통 이용승객의 실제 이동 경로를 기준으로 개선 전·후의 알고리즘 결과를 분석하였다. 이를 통해 제시한 알고리즘이 승객의 다양한 경로 선택 기준을 반영한다는 것을 확인하였다.
Abstract
Schedule-based public transit routing algorithm computes a single route that calculated minimum travel time using the departure and arrival times for each stop according to vehicle operation plan. However, additional factors such as transfer resistance and alternative route choice are not reflected in the path finding process. Therefore, this paper proposes a improved RAPTOR that reflected transfer resistance and multi-path searching. Transfer resistance is applied at the time of transfer and different values can be set according to type of transit mode. In this study, we analyzed the algorithm's before and after results compared with actual route of passengers. It is confirmed that the proposed algorithm reflects the various route selection criteria of passengers.
참고문헌 (20)
- Arbex R. O., "Efficient transit network design and frequencies setting multi-objective optimization by alternating objective genetic algorithm", Transportation Research, 81, pp.355~376 (2015)[DOI]
- Cionini A., "Engineering graph-based models for dynamic timetable information systems", OASIcs-OpenAccess Series in Informatics, 42, pp.46~61 (2014)
- Delling D., "Public transit labeling", International Symposium on Experimental Algorithms, pp.273~285 (2015)
- Delling D., "Round-based public transit routing", Proceedings of the Meeting on Algorithm Engineering & Expermiments, pp.130~140 (2012)
- Dibbelt J., , International Symposium on Experimental Algorithms, pp.43~54 (2013)
- Garcia-Martinez A., "Transfer penalties in multimodal public transport networks", Transportation Research Part A: Policy and Practice (2018)
- Guo J., "A new algorithm for finding the K shortest paths in a time-schedule network with constraints on arcs", Journal of Algorithms & Computational Technology, 11(2), pp.170~177 (2017)[DOI]
- Hu X., "A Constrained Time-Dependent K Shortest Paths Algorithm Addressing Overlap and Travel Time Deviation", International Journal of Transportation Science and Technology, 4(4), pp.371~394 (2015)[DOI]
- 김응철, "교통약자의 환승을 고려한 K경로탐색 알고리즘 개발", 서울도시연구, 10(2), pp.147~159 (2009), 서울연구원[DOI]
- 김은지, "교통안전, 환경지표의 저항값을 고려한 대중교통 경로 탐색 알고리즘 개발", 한국ITS학회 논문지, 16(1), pp.78~89 (2017), 한국ITS학회[DOI]
- Madkour A., "A survey of shortest-path algorithms", ~ (2017)
- Park B. H., "Effects of Transfer Penalty in the Public Transit Assignment", Social Economy & Policy Studies, 17(2), pp.65~92 (2001)
- Park H. C., "A Study of Diffenrence Between Intramodal and Intermodal Transfer Penalties", Proceedings of the KOR-KST Conference, 66, pp.555~560 (2012)
- Pyrga E., "Efficient models for timetable information in public transportation systems", Journal of Experimental Algorithmics, 12, pp.1~39 (2008)
- Strasser B., "Connection scan accelerated", 2014 Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments, pp.125~137 (2014)
- Wang S., "Solving the K-shortest paths problem in timetable-based public transportation systems", Journal of Intelligent Transportation Systems, 20(5), pp.413~427 (2016)[DOI]
- Witt S., "Trip-Based Public Transit Routing", Algorithms-ESA 2015, pp.1025~1036 (2015)
- Yang S. J., "A study on Route Choice Modeling in Rapid Transit Network Considering Transfer Penalty and Angular Cost", pp.2017
- 유경상, "Transfer Penalty Estimation with Transit Trips from Smartcard Data in Seoul, Korea", KSCE Journal of Civil Engineering, 19(4), pp.1108~1116 (2015), 대한토목학회[DOI]
- Yoo H., "A Study for Improving the Convenience of Transfer in Urban Railway : Cases of the Airport Railroad", pp.2017