ISPRS, Vol.34, Part 2W2, “Dynamic and Multi-Dimensional GIS”, Bangkok, May 23-25, 2001 
Among these limitations, the turn movement, either banned 
or penalized, contributed significant to the total travel time 
[Dirch Van Vliet, 1977; Pallotinno S., Scutella M.G, 1997]. 
The magnitude of these movement delays may even be 
comparable to the link travel time which account for 17-35% 
in the total time [Nielson O.A et al., 1998]. So these extra 
travel cost must be taken into account when finding the 
minimum cost itinerary between two points to accurately 
describe travel times and route choice behavior. Ignoring 
them may miss essential characteristics of the network and 
lead to sub-optimal or illogical paths. We shall particular 
address the optimum path problem with turn penalties and 
prohibition out of all characteristic attributes of traffic network 
[A.K.Ziliaskopoulos and H.S Mahmassani, 1996; Pallotinno 
S., Scutella M.G, 1997; Nielson O.A. et ai, 1998]. 
required: 
d a —the minimum distance from origin S to node A; 
P a —the predecessor of A; i.e. link(P a , A) lies on the 
shortest path from S to A. 
The procedure for building a minimal tree from S to all other 
nodes may be described as follows: 
First (initialization) set all d a = °° (i.e. a suitable large 
number) except d s which is set equal to zero, all P a to 
some default value, and all entries L, in a loose-end table 
L to zero. 
Now (procedure), starting with the origin S as the current 
node 
2.2 PROBLEMS RAISED BY TURN 
Classical algorithms assume that there are no costs or 
prohibitions associated with intersection movement in road 
network. Thus the intersection movements generally are not 
included in network models, logistic models and route 
guidance systems. While taking into consideration of 
intersection movements, many problems are introduced 
sequentially, three of them are most important to path 
finding. 
(1) Traditional data models emphasize only the 
connections between nodes and arcs. In our 
application, the banned or penalty turn is the attribute 
of one node but it represents the relationship 
between arcs connected by this node. The turn 
movements of the connected arcs are attached to 
one same node. So a new method must be 
developed to efficiently specify the complicated 
network topology between nodes and arcs with turn 
restrictions. 
(2) A data structure that can represent the topology with 
turn restriction is another key difficulty. In addition, 
intersection models usually use many 
attribute/parameters to describe the turn delay. The 
number of parameters representing turns is far larger 
than the number of conventional parameters. This 
should also be considered in the data structure for 
quick path finding. 
(3) In classical algorithm, the relationship of nodes is 
used for calculating shortest paths. Since turns 
present the relationship of links, the algorithm 
required to be modified to adapt this change. 
3. KEY ISSUE OF PATH FINDING 
The most important issue of path finding is the algorithm. As 
mentioned above, the essentials of most path finding 
algorithms are based on three classical algorithms, all of 
which can be summed up to two basic parts: Bellman-Ford 
equation and label-setting or label-correcting algorithm. No 
matter how many attribute need to be added for representing 
turn restrictions, the fundamental of algorithm is still the 
classical shortest path algorithm. So the general idea of the 
classical shortest path algorithm is briefly explained in the 
first part of this section. And some methods proposed by 
previous researchers to solve turn problem are reviewed and 
commented in the other parts of this section, including 
topology, data structure, and algorithm. The kernel of the 
problem is how to representing the network in an economical, 
compact and manageable way. 
3.1 GENERAL IDEA OF CLASSICAL ALGORITHMS 
For convenience of description, the following notation is 
(1) Examine each exit link (A, B) from the current 
node A in turn thus: 
if d a d a +d(a,b) 
Eq.1 
Set db=da+d (a ,b), Pb=A 
Eq.2 
and add B to the loose-end table (provided, if through 
routing via centroids is prohibited, that B is not a 
centroid, and (in certain implementations) that B 
does not already appear in L. 
(2) Remove A from the loose-end table. If the table 
is empty, stop; otherwise: 
(3) Select another node A from the loose-end table 
(following specified rules) and return to step (1). 
At the completion of this procedure d a contains the set of 
minimum distances from S to each node/centroid a while P a 
contains the data necessary to re-construct all shortest 
paths. 
3.2 NETWORK TOPOLOGY 
Most approaches to solve the turn problem are based on the 
expanded network, which is obtained by highlighting each 
movement in the intersections, where the costs of the 
dummy arcs are the banned costs or penalties costs. So an 
intersection in network split into many dummy nodes and 
dummy arcs that restructure a sub-network, as shown in Fig 
2. 
Fig. 2 An intersection-expended network with turns penalties. 
The advantages of the expanded network approach are no 
turning delays and prohibitions are included in the large 
network, and the problem can be solved with any standard 
data structure and standard shortest path algorithm. But the 
shortage of the expanded network approach is evident, i.e. 
the resulting network is considerably larger than the original 
graph; required increased computational time and computer 
memory because of the network; moreover, time-consuming 
network updating when any modification in the movement is 
occurrence.