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)
For each vertex ie adj(s), set sc(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)
Set sc(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
