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.
Search WWH ::




Custom Search