ISPRS, Vol.34, Part 2W2, “Dynamic and Multi-Dimensional GIS”, Bangkok, May 23-25, 2001 
120 
3.3 DATA STRUCTURE 
Data structure is an alternative way of representing network 
without changing the topology of the road network. Defining 
a new data structure to indicate the relationship of the 
intersection movements. The shortest path algorithm can be 
modified based on the new data structure. The most 
commonly used representation is a list structure, called star 
structure [Dial et.al, 1979]. The star data structure can be 
classified to forward star structure and backward star 
structure. In this study a forward star structure (FSS) is 
employed, with no loss of generality, as indications for 
extrapolating the approach to a backward star structure are 
given. 
Let G=(V, A) be directed graph consisting of a finite set V of 
nodes and finite set A of arcs connecting the nodes. In the 
forward star structure (FSS), a pointer is kept for each node 
of the network, indicating the position in the arc list, of arcs 
beginning at this node. Fig 3b illustrates this pointer 
representation for the network sketched in Fig 3a. 
In this example, a pointer can be viewed as an array, 
ForwardPointer(), of size |V|=4 with the following entries: 
ForwardPointer(1 )=1 
ForwardPointer(2)=3 
ForwardPointer(3)=5 
ForwardPointer(4)=7 
This structure allows easy processing of the link emanating 
from a given node. This structure is probably the most 
widely used network representation for transportation 
applications. 
82. 
Fig. 3a A network example diagrammatically 
Node ForwardPomter PointedNodes TravdTime 
*(i J) 
1 
2 
3 
4 
■>2 
3 
—*2 
4 
—>2 
30 
42 
54 
73 
42 
64 
82 
Fig 3b. The forward star structure of the network 
Base on the forward star structure, extended forward star 
structure (EFSS) is presented by Ziliaskopoulos 
[Ziliaskopoulos A.K. & Mahmassani H.S., 1996]. Extended 
forward star structure utilizes the feature of the forward 
star structure, which contains the synthesis of the 
intersection movements. In other word, the movements 
that a vehicle approaching a given intersection can follow 
are implicitly Included in, and can be identified from, the 
FSS. The penalties associated with each of these 
movements can be added to the FSS, as shown in Fig 3c. 
Node 
ForwardPomter 
PomtedNode 
Travel Time 
Penalties 
r (U) 
t ) 
2 
30 
3 
7 0 
2 
3 
5 
23 
16 0 
3 
4 
42 
54 
5 — 
0 
4 
7— 
3 
73 
17 
12 0 
2 
42 
4 
16 0 
A 
64 
11 
0 
► 
2 
82 
19 
9 0 
Fig 3c. The extended forward star structure that includes 
intersection movement representation. 
For each position in the PointedNodes() array, the 
associated turning movement penalties are included in a 
two-dimensional array format—called Penalties(). The first 
dimension of the array Penalties() has a size equal to 
PointedNodes() array and associates the penalties with the 
nodes the movement are performed at (see Fig. 3c); the 
second dimension, with size equal to the out degree 
PointedNodes() of the approached node plus one. The 
additional dimension corresponds to the case that the 
vehicle terminates its trip at the intersection. The penalty 
value for this position could be a cost that represents the 
time that a vehicle needs to abandon the network, e.g. 
parking time at this location. If a movement is prohibited, 
then a very large cost can be set at the corresponding 
position. 
3.4 ALGORITHM 
Kirby and Potts made the most important contribution in 
algorithm design with turn penalties or banned [Kirby & 
Potts, 1969]. They presented an algorithm that efficiently 
computes shortest paths considering intersection 
movement delays without dramatically altering the network 
structure, which is based on the previous work by Caldwell 
[Caldwell, 1961]. The key of their algorithm is the following 
functional equation: 
C(Uj) = min {C(! l ,l t ) + c(/J + P (l k ,/,)},/, * /,,C(/„/,) = 0 
Eq.3 
Where C(/„iy is the cost of an admissible path from the end 
of link /, to the beginning of link /y, c(li<) is the travel time on 
link k, p(l k ,lj) is the delay associated with the movement 
from link /, to link /y and B(lj) is the set of links upstream of /y. 
From the formulation, Kirby and Potts describe a path as a 
sequence of arcs instead of a sequence of nodes and 
modified Bellman’s classical conditions. Having the new 
conditions, the core of the algorithm does not required to be 
modified and the original network need not to be 
transferred. But no method for Implementing this approach 
was proposed by the authors, and therefore no interfaces 
can be made on its computational performance. 
Easa (1985), inspired by Kirby and Potts approach, 
proposed a(Tgb) implemented a scheme that computes 
shortest paths considering prohibited movements, but not 
intersection delays. He uses a modified label-correcting 
scheme that maintains two lists of links with the potential to 
improve the label of their downstream node. The links from 
the first list are scanned in a first-in-first-out order, while the 
new scan eligible links are entered in the second list. When 
the first list empties, all the links from the second list are 
transferred to the first one. The algorithm requires the 
network to be in a link structure form, and categorizes the 
nodes in two sets, based on whether they have prohibited 
movements or not. The scheme appears to be efficient, but 
limited in applicability because it does not consider 
penalties for intersection movements. 
4.