비가산성 경로비용을 반영한 링크표지기반 Node-to-Link 최적경로탐색
A Link-Label Based Node-to-Link Optimal Path Algorithm Considering Non Additive Path Cost
0
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
기존의 Node-to-Node기반 최적경로탐색은 기점노드에서 모든 종점노드도착조건이 성립되는 가정으로 구축되었다. 최근 적응적 경로탐색의 등장으로 Node-to-Node 경로탐색은 최적해를 도출하지 못하는 한계가 존재한다. 따라서 교통정보를 링크에서 실시간 반영하기 위한Node-to-Link(또는 Link-to-Node; NL) 문제에 필요성이 대두되고 있다. 본 연구는 Node-to-Link의최적 해법을 구축하는 방안으로서 링크표지와 비가산성경로비용이 존재하는 네트워크를 가정한다. 링크표지는 회전페널티가 존재하는 교차지점에서 네트워크의 원형을 유지하게 한다. 비가산성경로비용의 포함은 최적경로를 도출하기 위해서 M-유사경로의 열거를 필요로 한다. 본연구는 진입링크기반 네트워크 변형기법에서 링크표지를 통하여 루프를 통제하며 최종링크까지 최적해를 보장하기 위한 방향삭제와 회전금지를 제안하였다. 사례연구를 통해 제안된 방법이 경험적 최적해를 도출하는 것으로 파악되었다. 향후 대규모 네트워크에서 검증작업의 필요성을 언급하며 마무리 하였다.
Abstract
Existing node-to-node based optimal path searching is built on the assumption that all destination nodes can be arrived at from an origin node. However, the recent appearance of the adaptive path search algorithm has meant that the optimal path solution cannot be derived in node-to-node path search. In order to reflect transportation data at the links in real-time, the necessity of the node-to-link (or link-to-node; NL) problem is being recognized. This research assumes existence of a network with link-label and non-additive path costs as a solution to the node-to-link optimal path problem. At the intersections in which the link-label has a turn penalty, the network retains its shape. Non-additive path cost requires that M-similar paths be enumerated so that the ideal path can be ascertained. In this, the research proposes direction deletion and turn restriction so that regulation of the loop in the link-label entry-link-based network transformation method will ensure that an optimal solution is derived up until the final link. Using this method on a case study shows that the proposed method derives the optimal solution through learning. The research concludes by bringing to light the necessity of verification in large-scale networks.
참고문헌 (14)
- Azevedo J. A, "An Algorithm from the Ranking of Shortest Paths", European Journal of Operational Research, 69, pp.97~106 (1993)
- Bellman R, "Dynamic Programming" (1957), Princeton University Press
- Choi K, "Network Representation Schemes for U-TURN and Implementation in the Vine-Based Dijkstra Shortest Path Algorithm", Journal of Korean Society of Transportation, 13(3), pp.35~52 (1995)
- Dijkstra E. W, "A Note on Two Problems in Connexion with Graphs", Numerische Mathematik, 1, pp.269~271 (1959)
- Gabriel S, "The Traffic Equilibrium Problem With Nonadditive Path Costs", Transportation Science, 20(5), pp.337~348 (1997)
- Kirby R. F, "The Minimum Route Problem for Networks with Turn Penalties and Prohibitions", Transportation Research, 3, pp.397~408 (1969)
- Lee M, "Transportation Network Models and Algorithms Considering Directional Delay and Prohibitions for Intersection Movement", Ph.D, pp.2004
- 이미영, "수도권 도시철도망 승객이동경로추정을 위한 교통카드기반 최적 M-유사경로 구축방안", 한국ITS학회 논문지, 16(2), pp.1~12 (2017), 한국ITS학회[DOI]
- Martins E. Q. V, "An Algorithm for Ranking paths THat May Contain Cycles", European Journal of Operational Research, 18, pp.123~130 (1984)
- Moore E. F, "The Shortest Path Through A Maze,” Proceedings of An International", Conference of Symposium on the Theory of Switching (1957), Harvard University
- 신성일, "Stepwise 환승계수를 고려한 Logit 유형 대중교통통행배정모형", 대한교통학회지, 34(6), pp.570~579 (2016), 대한교통학회[DOI]
- 신성일, "교통망에 적합한 K 비루프 경로 탐색 알고리즘", 대한교통학회지, 22(7), pp.121~131 (2004), 대한교통학회
- 신성일, "누적환승함수를 고려한 경험적 최적경로탐색 방안", 한국ITS학회 논문지, 15(3), pp.60~67 (2016), 한국ITS학회[DOI]
- Yen J. Y, "Finding the K Shortest Loopless Paths in A Network", Management Science, 17, pp.711~715 (1971)