ISPRS, Vol.34, Part 2W2, “Dynamic and Multi-Dimensional GIS”, Bangkok, May 23-25, 2001 
OPTIMIZING PATH FINDING IN VEHICLE NAVIGATION CONSIDERING TURN PENALTIES AND 
PROHIBITIONS 1 
Gang HAN 12 Jie JANG 1 Jun CHEN 1 
1. National Geomatics Center of China, 
No.1, Baishengcun, Zizhuyuan, 100044,Beijing, P.R.China 
E-mail: hg0001 @263.net, (jjie, chenjun)®nsdi.gov.cn 
2. Department of Computer Science, Beijing Institute of Technology; 
No.7, Baiyi Road, 100081,Beijing, P.R.China 
KEY WORDS: Turn, path, minimum cost 
ABSTRACT 
Traffic network has many characteristic attributes, which distinguish road network from general category of “directed graphs". Among 
these attributes turn movements of intersections is significant to computing optimum path in vehicle navigation. But classical shortest 
path algorithms did not take much consideration of turn restrictions when calculating optimum paths. Sometimes result in sub-optimal or 
illogical paths. This paper proposed a considerably efficient data structure to represent the turn restrictions. And a modified label-setting 
algorithm was developed to compute optimum paths in road network with turn restrictions, taking the advantages of the proposed 
structure. The approach was verified in a prototype program and compared with some existing methods. 
1. INTRODUCTION 
With the development of GPS technology, vehicle navigation 
has become a common practice within a complicated traffic 
network. One of the core issues for vehicle navigation is to 
find the optimum paths for the driver before or during the 
travel. Path finding has been a traditional topic. More than 
two thousand scientific works have been published in the 
international literature since the end of the 1950s. Most of 
these algorithms discussed classical problems, i.e., to find 
the shortest paths between some given origin/destination 
pairs in a network (represented as “directed graphs"), 
assuming no other costs within networks except the cost of 
arcs (length, cost, etc.). And most of them are based on the 
three classical algorithms proposed by Moore (1957), 
Dijkstra (1959) and DEsopo (1960). [Moore, 1957; Dijkstra, 
1959;DEsopo, 1960] 
illogical paths [A.K.Ziliaskopoulos and H.S Mahmassani, 
1996]. The classical methods which considering only the 
cost of arcs are not suitable for path finding in real traffic 
navigation application anymore. 
The authors of this paper discussed the turn prohibition 
problem in the traffic network first (section 2). And then 
analyzed the key issues in the classical path finding 
algorithms, including network topology, data structure and 
the path computing (section 3). In section 4, a data structure 
was designed to describe turn prohibitions. And the 
traditional Dijkstra algorithm was modified based on this new 
data structure to compute the optimum path in the traffic 
network with turn limitations. A prototype system was 
developed to verify the proposed method. The results and 
conclusion was given in section 5. 
2. THE TURN PROBLEM IN TRAFFIC NETWORK 
Considering the nature of the path finding problem, it 
generally means to compute optimum paths from a source 
node to every other node (one-to-all) or from every node to 
every other node (all-to-all) within a network. However, it is 
only necessary to compute the optimum paths from the start 
node to one destination node (one-to-one) or to some 
destination nodes (one-to-some) for vehicle navigation. 
More significantly, not all possible paths are practicable 
since there are often turns forbidden, right of way or other 
traffic limitations in the traffic network. And also, traffic 
lights and counter flow cause an extra cost. Actually 
intersection movement delays and restrictions contribute 
significantly to the overall travel time in congested traffic 
networks. [Pallotinno S. et al., 1997\ Nielson O.A. et al., 
1998,]. So it is crucial to take into consideration the turn 
penalties and prohibitions while computing the optimum 
paths for the real-time vehicle navigation application. 
Ignoring them may miss essential characteristics of the 
network and lead to the computation of sub-optimal or 
2.1 THE TURN RESTRICTION 
In urban traffic networks, connection is not the unique 
relationship between two roads. There are various traffic 
limitations, including restricted period of time, vehicle type 
restriction, signal, turn movement, etc. (Fig 1). 
20 
20 
Z 0 ® 0 
26 2 5 2 5 2 5 
Fig 1. Various Control Signs 
This work was supported by the National Natural Science Foundation of China under grant number: 69833010