Earticle

초록

영어

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 | 영남교통정책연구원 원장 ] 주저자

참고문헌

발행기관

간행물

표지보기 관심저널 등록

• 간행물명

  한국ITS학회논문지 [The Journal of The Korean Society of Intelligent Transport Systems]

• 간기

  격월간

• pISSN

  1738-0774

• eISSN

  2384-1729

• 수록기간

  2003~2026

• 등재여부

  KCI 등재

• 십진분류

  KDC 326 DDC 338