Bee Geum  Hwan-Gue Cho

Vol. 13,  No. 6, pp. 269-277, Jun.  2024
https://doi.org/10.3745/TKIPS.2024.13.6.269

Shortest Path Quickest Path Simple Path Road Network

PDF

With the advancement of modern IT technologies, the operation of autonomous vehicles is becoming a reality, and route planning is essential for this. Generally, route planning involves proposing the shortest path to minimize travel distance and the quickest path to minimize travel time. However, the quality of these routes depends on the topological characteristics of the road network graph. If the connectivity structure of the road network is not rational, there are limits to the performance improvement that routing algorithms can achieve. Real drivers consider psychological factors such as the number of turns, surrounding environment, traffic congestion, and road quality when choosing routes, and they particularly prefer routes with fewer turns. This paper introduces a simple path algorithm that seeks routes with the fewest turns, in addition to the traditional shortest distance and quickest time routes, to evaluate the characteristics of road networks. Using this simple path algorithm, we compare and evaluate the connectivity characteristics of road networks in 20 major cities worldwide. By analyzing these road network characteristics, we can identify the strengths and weaknesses of urban road networks and develop more efficient and safer route planning algorithms. This paper comprehensively examines the quality of road networks and the efficiency of route planning by analyzing and comparing the road network characteristics of each city using the proposed simple path algorithm.