earticle

논문검색

ATIS

최소 기대 부하량을 이용한 최단경로 탐색 알고리즘 개발

원문정보

Development of a Shortest Path Searching Algorithm Using Minimum Expected Weights

유영근

피인용수 : 0(자료제공 : 네이버학술정보)

초록

영어

This paper developed a new shortest path searching algorithm based on Dijkstra's algorithm and A* algorithm, so it guarantees to find a shortest path in efficient manner. In this developed algorithm, minimum expected weights implies the value that straight line distance from a visiting node to the target node multiplied by minimum link unit, and this value can be the lowest weights between the two nodes. In behalf of the minimum expected weights, at each traversal step, developed algorithm in this paper is able to decide visiting a new node or retreating to the previously visited node, and results are guaranteed. Newly developed algorithm was tested in a real traffic network and found that the searching time of the algorithm was not as fast as other A* algorithms, however, it perfectly found a minimum path in any case. Therefore, this developed algorithm will be effective for the domain of searching in a large network such as RGV which operates in wide area.

한국어

본 연구에서는 최단경로를 반드시 찾아내는 Dijkstra 알고리즘의 장점과 최단경로 탐색 소요시간을 단축시키는 A* 알고리즘의 장점을 결합시킨 새로운 최단경로 탐색 알고리즘을 개발하였다. 개발한 알고리즘은 탐색노드에서 목적노드까지의 최소 기대 부하량을 산출하고 이 값을 이용하여 계속 탐색 또는 이전 탐색노드로의 후퇴를 결정한다. 최소 기대 부하량은 목적노드까지의 직선거리에 최소 가로 부하량 원단위를 곱하여 산출하는데, 적용하는 네트워크에서는 그 값 이하의 부하량이 존재할 수 없는 값이다. 개발한 알고리즘을 실제 네트워크에 적용하여 최단경로를 탐색해 본 결과, 어느 정도의 탐색 소요시간은 필요로 하나, 완벽하게 최단경로를 구축하는 것으로 나타났다. 개발한 알고리즘은 광역의 네트워크를 이용하는 차량 경로 안내시스템 등에서 효과를 가질 것으로 판단한다.

목차

요약
 Abstract
 I. 서론
 II. 기존 연구
  1. 양방향 탐색법(Bidirectional Search)
  2. 목적지 직접 탐색법(Goal-Directed Search)
  3. 네트워크 계층 구분법(Hierarchical Methods)
 III. 최소 가로 부하량 원단위
 IV. 최소 기대 부하량
 V. 새로운 최단경로 탐색 알고리즘
 VI. 개발 알고리즘의 효율성
  1. 효율성 검증방법
  2. 사례 네트워크와 부하량
  3. 효율성 검증
 VII. 결론
 참고문헌

저자정보

  • 유영근 Ryu, Yeong-Geun. 영남교통정책연구원 원장

참고문헌

자료제공 : 네이버학술정보

    함께 이용한 논문

      ※ 기관로그인 시 무료 이용이 가능합니다.

      • 4,000원

      0개의 논문이 장바구니에 담겼습니다.