Information Technology Reference
In-Depth Information
Fig. 3.
Voronoi diagrams visualizing PDR and PDT. Dots mark nodes in which path computation
started, color denotes average time until shortest path completed in the enclosed region. Left:
G
RANELLI
(
n
=4
), fast but unreliable; middle: S
EET
(
n
=4
), slower but more reliable than
G
RANELLI
due to taking correlation of
G
and
G
into account; right: Our approach,
n
=4
,
taking correlation between
G
and
G
as well as local information on dynamic graph operations
into account outperforms G
RANELLI
and S
EET
.
n
.For
n
=1
this resulted in 120 path computations. We repeated every
run three times for every
n
and algorithm. This means
120
∈{
1
,
2
,
3
,
4
}
3 = 360
path computa-
tions for
n
=1
in total per algorithm and 720, 1080, 1440 for
n
=2
,
3
,
4
respectively
resulting in a total of 3600 path searches per algorithm.
∗
4.3
Results and Analysis
Results in Figure 4 and Figure 5 show that our approach outperforms S
EET
and
G
RANELLI
in means of PDR. As expected, PDR increases with increasing traffic den-
sity. S
EET
obviously benefits from the available information about the underlying city
map (the static graph
G
). G
RANELLI
lacks this kind of information which results in a
GRANELLI
SEET
Our approach
0,90
0,68
0,45
0,23
0
120
240
360
480
Fig. 4.
Path Discovery Ratio (PDR) results for all three algorithms. X-Axis gives the number
of path searches, y-axis gives the percentage of successful path searches. As expected, PDR
increases with a larger number of cars on the evaluation scenario.