Yen 알고리즘을 활용한 열차 다중경로 탐색
Finding the K-Shortest Paths in a Rail Network Using Yen’s Algorithm
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
본 연구의 목적은 철도 최적 운영 대안의 실현성 및 효과성을 높이기 위한 출발지와 목적지 간 복수의 가능 경로 탐색 방법론을 고찰하는 것이다. 네트워크에서의 다중경로 탐색알고리즘인 Yen 알고리즘을 활용하여 철도 네트워크에서의 복수의 가능 경로를 탐색하는 방법론을 제시하였다. 또한 철도 시설 현황을 고려한 철도 네트워크의 모델링 방법도 제안하였다. 경부선 고밀도 영역의 네트워크 데이터를 활용하여 Yen 알고리즘에 의한 다중경로 탐색의 적용 가능성을 확인하였으며, 연산시간 측정을 통해 마이크로 실시간 자동 관제에 다중경로 정보의 활용 방안을 제안하였다. 본 연구의 결과를 활용하여 국내 열차 운영 최적화 시 기존 reordering 중심의 대안에서 rerouting 대안까지 확대하여 적용할 수 있다.
Abstract
The purpose of this study is to examine methodologies to find the K-shortest paths between origins and destinations to increase the feasibility and effectiveness of the optimal railway operation alternatives. A methodology for finding possible routes in a railway network using Yen’s algorithm, which is a K-shortest paths algorithm, is presented. In addition, a network construction method considering railway facilities was also proposed. Using the network data of the high-density area of the Gyeongbu Line, the applicability of Yen’s algorithm was verified, and a method of using K-paths for real-time automatic control was proposed with the computation time. Using the results of this study, domestic train operation alternatives can be expanded from reordering to rerouting.
참고문헌 (14)
- Reynolds, E., "Modelling, Solution and Evaluation Techniques For Train Timetable Rescheduling Via Optimisation", doctor, pp.2020
- Fuchsberger, M., "Algorithms for railway traffic management in complex central station areas", doctor, pp.2012
- Dijkstra, E. W., "A Note on Two Problems in Connexion with Graphs", Numerische Mathematik, 1, pp.269~271 (1959)
- Ford jr., L.R., "Flows in networks" (1962), Princeton University Press
- Yen, J.Y., "Finding the K Shortest Loopless Paths in a Network", Management Sciences, 17(11), pp.711~715 (1971)
- Martins, E. Q. V., "An algorithm for ranking paths that may contain cycles", European Journal of Operational Research, 18(1), pp.123~130 (1984)
- Azevedo, J. A., "An algorithm for the ranking of shortest paths", European Journal of Operational Research, 69(1), pp.97~106 (1993)
- Eppstein, D., "Finding the k Shortest Paths", SIAM Journal on computing, 28(2), pp.652~673 (1998)
- Jiménez, V. M., "A Lazy Version of Eppstein’s K Shortest Paths Algorithm", WEA 2003: Experimental and Efficient Algorithms, LNCS, 2647, pp.179~191 (2003)
- 임강원, "교통망 분석에서 K경로탐색 알고리즘에 관한 연구 (Ordered Heap Tree 구축방식을 중심으로)", 대한교통학회지, 23(8), pp.113~129 (2005), 대한교통학회
- "Yen's algorithm" (2002)[URL]
- Bouillet, E., "Path routing in mesh optical networks" (2007), Wiley
- Cho, J. S., "A K Least Time Paths Searching Algorithm for Time Dependent Intermodal Transportation Networks with Departure Time Schedule Constraints, Journal of Korean Society of Transportation", Journal of Korean Society of Transportation, 24(3), pp.167~176 (2006), Korean Society of Transportation
- 조종석, "복합교통망에서의 동적K최소시간경로탐색", 대한교통학회지, 24(5), pp.77~88 (2006), 대한교통학회