초록 ▼

본 연구에서는 Dijkstra 알고리즘을 이용하여 복수의 경로를 구축하는 최적경로 알고리즈을 제안하였다. 복수의 경로를 찾기 위해서 준최적의 경로를 이용하였으며, 준최적의 경로를 찾기 위해 메모리에 로드된 도로망 데이터중에서 이미 검색한 최저경로에 해당하는 링크들을 삭제한후, 이 데이터를 가지고 Dijkatra 알고리즘을 다시 수행하여 준퇴적의 경로를 찾도록 하였다. 그리고 복수의 경로를 구축할 때 준 최적경로의 총비용이 먼저 검색한 최적경로의 총비용보다 너무 값이 클 경우에는 최적경로로서의 의미가 없어지므로 적어도 처음에 검색한

본 연구에서는 Dijkstra 알고리즘을 이용하여 복수의 경로를 구축하는 최적경로 알고리즈을 제안하였다. 복수의 경로를 찾기 위해서 준최적의 경로를 이용하였으며, 준최적의 경로를 찾기 위해 메모리에 로드된 도로망 데이터중에서 이미 검색한 최저경로에 해당하는 링크들을 삭제한후, 이 데이터를 가지고 Dijkatra 알고리즘을 다시 수행하여 준퇴적의 경로를 찾도록 하였다. 그리고 복수의 경로를 구축할 때 준 최적경로의 총비용이 먼저 검색한 최적경로의 총비용보다 너무 값이 클 경우에는 최적경로로서의 의미가 없어지므로 적어도 처음에 검색한 최적경로의 총비용과 임계값의 차이를 두어 비용간의 차이값이 임계값보다 작을 경우 준최적경로로 채택해도록 한다. 또한 도로망 데이터는 특성상 방대한 양을 가지므로 도로망의 계층성과 섹터화 정보를 이용하여 효율적으로 검색하는 방법을 제안하였다.

Abstract ▼

In this study, we proposed an optimal route guidance algorithm by searching multiple paths based on the Dijkstra algorithm. Multiple paths with sub-optimality can be determined as follows. To find the sub-optimal route, we first remove the link of optimal route which is already searched in the road

In this study, we proposed an optimal route guidance algorithm by searching multiple paths based on the Dijkstra algorithm. Multiple paths with sub-optimality can be determined as follows. To find the sub-optimal route, we first remove the link of optimal route which is already searched in the road network data, and then we repeat the execution of the Dijkstra algorithm. If the cost of sub-optimal path is much greater than that of the optimal path, we stop the repetitive execution to find the sub-optimal route. The condition of sub-optimality is satisfied only when the difference between the cost of chosen path and that of the optimal path is less than the suggested threshold. Also, since it is not easy to process the huge amount of data for the road network, we proposed the efficient searching method using the hierarchy and the sector information of road network.
This study also suggested a new map-matching algorithm for the car navigation systems using Kalman filtering and linear regression methods. This eventually brings the improvement of positioning accuracy of the vehicle with GPS receiver. After representing a travelling vehicle's motion by state equations using Singer's model, the proposed map-matching algorithm places the position of the vehicle right on the road and also improves the positioning accuracy of the vehicle through Kalman filtering. In the intersection, since it is difficult to determine precisely the current travelling road, we take linear regression to the estimated values from Kalman filltering. This gives the direction angle of turning vehicle. Then we can determine the correct route direction after comparing all the route-direction angles at the intersection. Through actual route travelling tests, we have shown that the suggested map-matching algorithm is much superior to the conventional algorithms. We expect that this map-matching algorithm with optimal route guidance algorithm guarantees efficient and reliable car navigation systems in the near future.

목차 Contents

• I. 서론...7
• II. 디지탈 수치 도로지도...8
• III. 항법전용 데이타의 구축...11
• IV. 최적경로 알고리즘...14
• V. 도로망의 계층성...20
• VI. 섹터화 정보의 이용...23
• VII. 복수 경로 구축...25
• VIII. 맵 매칭 알고리즘...26
• IX. 실험 결과...41
• X. 결론...50
• 인용문헌...51