ISPRS, Vol.34, Part 2W2, “Dynamic and Multi-Dimensional GIS", Bangkok, May 23-25, 2001 
121 
Penalties 
t) 
3 7 0 
5 16 0 
23 0 
17 12 0 
4 16 0 
11 0 
19 9 0 
includes 
array, the 
:luded in a 
). The first 
e equal to 
ies with the 
ig. 3c); the 
out degree 
; one. The 
,e that the 
The penalty 
iresents the 
itwork, e.g. 
; prohibited, 
rresponding 
ntribution in 
ed [Kirby & 
at efficiently 
intersection 
the network 
by Caldwell 
the following 
from the end 
ravel time on 
e movement 
ostream of /,. 
e a path as a 
f nodes and 
ring the new 
equired to be 
not to be 
this approach 
no interfaces 
e. 
ts approach, 
iat computes 
lents, but not 
ibel-correcting 
he potential to 
The links from 
rder, while the 
ond list. When 
econd list are 
i requires the 
ategorizes the 
ave prohibited 
ie efficient, but 
not consider 
4. METHOD PROPOSED BY THE AUTHORS 
From the previous analysis, a conclusion that changing the 
topology of network is not easy can be achieved. The 
alternative way by defining a new data structure is relative 
easy. Thus the authors of this paper proposed a new data 
structure to represent the turn restrictions. Based on this 
new data structure, a slight modification is made on the 
classical algorithm to compute the shortest path. 
4.1 THE NEW DATA STRUCTURE 
As we all know that turning left or right is banned in some 
urban roads. In statistic, the number of banned turns is 
larger than the number of permitted turns (Table 1). 
Theoretically, the value of banned turn penalties is infinite, 
meaning that the corresponding movement is prohibited. 
But in real implementation, an infinite value in data structure 
is nonsensical. Considering the store space and 
performance of looking for, it is necessary to eliminate 
these infinite values from data structure. 
Total 
turns 
Banned turns 
Permitted 
turns 
43575 
32139 
11436 
Table 1. The turns information numbers in Hong Kong Road 
In EFSS data structure, the ForwardPointer() of the next 
node must be given. Only by this pointer and the pointer of 
current node, all nodes adjacent with current node can be 
definitely found out. In Penalties() column, only the penalty 
value is given but node id is not given that the value 
attached. A quadric search must be implement in the 
process. It is necessary to append the node id in the 
PenaltiesQ column. Moreover, a best path may contain 
loops, resulting from prohibited or high cost movement 
delays. A loop route including algorithm process is a 
time-consuming work. The terminal result of a loop route 
often makes the algorithm into a deadlock. The node id 
connected Penalties() is a useful information to avoid the 
loop route problem. A quadric search is also need to find 
the nodes id with turn penalties. General speaking, these 
redundant implement will largely depress the efficient of 
algorithm. 
Because the addition of the turn feature, the meaning of 
same node come from this parent node is different the 
meaning come from that parent node. Even though come 
from the same parent node the meanings of this parent 
node are different because of turn (Fig 4). The parent and 
grandparent nodes information must be given when 
computing the shortest path. Otherwise, the shortest path 
can’t be reconstructed when the computing process is 
finished. 
Fig 4. Different turns of same node 
Let G=(N, A) be a simple directed graph, where N is the set 
of the nodes, of cardinality n, and A is the set of the arcs, of 
cardinality m. In the forward star structure (FSS), a list 
(Adjacent list) is kept for each node of the network, 
indicating the position in the arc list, of arcs beginning at this 
node. In adjacent list, three fields are included: adjacent 
node id, next adjacent node pointer and a penalty list 
pointer. Another list (Penalties list) is kept for indicating next 
moving towards nodes in network after leaving the adjacent 
node. In Penalties list, three basic fields are included: 
penalty value, node id connect penalty and next pointer. Fig 
5. illustrates this list representation for the network sketched 
in Fig 2a. 
Fig 5. One node presentation 
4.2 THE MODIFIED ALGORITHM 
On the graph G defined in the previous section, let assume 
that all cycles have nonnegative cost and that there exists a 
path from s(source node) to every other vertex of N. For 
notation convenience, let sc(s) be shortest path cost from 
s(source node) to d(destination), pred(v) the predecessor of 
v and ppred(v) the parent of the predecessor of v in road 
network. T will represent the set of vertices marked as 
temporary and pc(v) will represent the penalty cost between 
arcs connected node v. adj(v) represent the set of vertices 
which connected with node v; 
Then the algorithm can be formalized: 
Step 1: Initializations. 
Set sc(s)<r 0 and pred(src)<r 0. 
For each vertex ie adj(s), set sc(i)<r+°° and pred(i)<r i. 
Finally, set T4-N 
Step 2: Selecting and updating. 
Find vertex / in T verifying 
If the minimum is not unique, select any i that achieves the 
minimum. 
For each vertex j eadj(i), scan all processors node of i, if 
none of them is j, then test if sc(i)+Wi+pc(i)<sc(j), then 
Set sc(j)<rsc(i)+Wij +pc(i). and pred(j)<ri. Else dessert j. 
Step 3: Loop or exit. 
If T is empty, then exit. 
Else if current node in T is node destination node), then 
exit. 
Else go to Step 2. 
The time performance of the algorithm is expected to be 
somewhat worse than the pure shortest path algorithms 
without intersection movements. 
5. EXPERIMENT AND CONCLUSION 
It will be difficult to defining the topology of road network