WIT Press

A Route Navigation System With A New Revised Shortest Path Routing Algorithm And Its Performance Evaluation


Free (open access)

Paper DOI









1,001 kb


W. Wen & S. W. Hsu


This paper presents a route navigation system with a new revised shortest path routing algorithm for solving road traffic problems. The system can avoid selecting no left (right) turns, one-way roads, and congested roads when it determines the shortest paths from source to destination. Also, the new revised routing algorithm is compared numerically with existing algorithms such as the Dijkstra algorithm and the A* algorithm. We choose a road network containing 4000 nodes which have 200 no left turn situations and find in particular that the road traffic problem of a 4000-node traffic network can be solved within only 0.651 seconds on average. The prototype system was built and some extra functions were added so that its benefits not only offer the shortest path but also provide information and security services for drivers. Keywords: shortest path routing algorithm, global position system, route navigation system. 1 Introduction Traffic congestion has increased steadily in most cities of high-tech countries. To solve congestion problems is not always feasible either by physically constructing new road facilities or by traditional transportation management systems. Therefore, it is important to develop more efficient methods to search an appropriate path on a road network. This is especially useful because no left (right) turns, one-way roads, and congestion roads are frequently encountered in everyday driving situations in big cities. Most road-vehicle cooperative driving systems are able to avoid the one-way roads. However, the systems do not solve


shortest path routing algorithm, global position system, route navigation system.