최단경로 탐색영역 축소 알고리즘 개발
Development of Shortest Path Searching Network Reduction Algorithm
0
조회
0
다운로드
4
인용
0
참고문헌
키워드
초록
본 연구에서는 최단경로 탐색 소요시간을 줄이기 위한 목적으로 탐색영역을 축소하는 알고리즘을 개발하였다. 개발된 알고리즘은 출발노드와 목적노드를 최소의 노드 수로 연결하면서 직선거리의 합이 최소인 임시경로를 구축하고,구축된 임시경로의 부하량 보다 적은 부하량의 경로를 연결할 가능성이 있는 노드들을 찾는 것이다. 하나의 노드에서출발노드까지의 직선거리와 목적노드까지의 직선거리 합이 임시경로의 부하량을 최소 가로 부하량 원단위로 나눈 값보다 적을 경우, 그 노드는 임시경로 보다 더 적은 부하량을 가질 수 있는 경로를 구성할 가능성이 있는 노드가 된다. 이와 같은 노드들만을 탐색영역으로 하면 탐색영역이 축소됨에 따라 최단경로 탐색 소요시간을 줄일 수 있게 된다. 개발된 알고리즘은 큰 탐색영역에서 출발노드와 목적노드가 가까울 경우 더욱 효과적이다.
Abstract
This study developed searching network reduction algorithm for reduce shortest path searching time. Developed algorithm is searching nodes that have the including possibility of less weights path than temporal path that consists minimum number of nodes and minimum sum of the straight line distances. The node that has the including possibility of shortest path is the node that the sum of straight line distance from start node and straight line distance to target node is less than the value that temporary path's weights divided by minimum weights units. If searching network reconstitutes only these nodes, the time of shortest path searching will be reduced. This developed algorithm has much effectiveness that start node and target node is close in large network.
참고문헌 (9)
- Lipimg Fu, "Expected shortestpaths in dynamic and stochastic traffic networks", Transportation Research Part B, 32(7), pp.499~516 (1998)
- 김태형, "도시부 가로망에서의 링크 통행속도 기반One-to-One 최단시간 경로탐색 알고리즘 개발", 한국ITS학회 논문지, 11(5), pp.38~45 (2012), 한국ITS학회
- E.W. DIJKSTRA, "A Note on Two Problems in Connexion with Graphs", Numerische Mathematik1, pp.269~271 (1959)
- Orda, A., "Shortest-path andminimum-delay algorithms in networks withtime-dependent edge-length", journal of the ACM, 37, pp.607~625 (1990)
- Kaufman, E, "Fastestpaths in time-dependent networks for intelligentvehicle highway systems application", IVHS journal, 1(1), pp.1~11 (1993)
- Ziliaskopoulos, A.K, "Time-dependent, shortest-path algorithms forreal-time intelligent vehicle system applications", Transportation Research Record, 1408, pp.94~100 (1993), TRB,National Research Council
- Chabini, I, "A new algorithm for shortest-path indiscrete dynamic networks", Proceeding of the 8thInternational Federation of Automatic ControlSymposium on transportation Systems, 2, pp.551~556 (1997)
- Hall, R, "The fastest path through a network withrandom time-dependent travel time", Transportation Science, 20(3), pp.182~188 (1986)
- Ryu, Yeong-Geun, "A Study on the Forecasting ofBus Travel Demand and the Method ofDetermining Optimal Bus Network", Ph. D, pp.1996