IEEE Computational Intelligence Magazine - May 2021 - 93

locations) at different departure times.
On one hand, different number of utility edges indicates different number of
iterations and gap-fillings. On the other
hand, different locations of utility edges
imply that the local underlying road
network is different. Under such circumstance, the running time should be
different since path-finding works
under different local road networks.
2) Varying Utility Time-Sensitivity
To demonstrate that our proposed system can work under different kinds of
utility, we conduct the experiment by
varying utility time-sensitivity based
on the synthetic road network. In this
experiment, all utility edges are set
using a unique time-sensitivity, and the
time-sensitivity is chosen from 5 minutes to 45 minutes with an equal interval of 5 minutes. The other parameter
settings are exactly the same as the
study of varying departure time, except
that we fix the departure time to 0:00.
In summary, as shown in Fig. 6, we
can draw the same overall conclusion
to the study of varying of departure
time. We will present the analysis in
detail, as follows.
In terms of the path utility score,
2TD finds the path with the highest utility score consistently under different utility time-sensitivities. In more detail, we
can clearly see three groups of utility
scores for each algorithm. The first group

has a similar high path utility score and contains the first three bars when the utility
time-sensitivity is not greater than
15 minutes; the second group has a similar
low path utility score and also contains three
bars when the utility time-sensitivity lies
in the range of [20, 30] minutes; the
third group has a similar median path utility
score and contains only one bar when the
utility time-sensitivity equals 45 minutes.
This is because: 1) for each utility edge,
according to Eq. 17, it can have three
different values within the time budget
(45 minutes) if the time-sensitivity is not
greater than 15 minutes. Our proposed
2TD is able to insert the time-dependent
best utility edges (e.g., having the value of
(1 + b) bu ) properly, leading to the highest path utility score in this group; 2) similarly, each utility edge can have two
utility values within the time budget if
setting the time-sensitivity in the range of
[20, 30] minutes, i.e., bu and (1 - b) bu
respectively. Although 2TD can still
maintain the ability of adding the timedependent best utility edges into the
driving routes, their total path utility
scores in this group should be smaller
than that in the first group; 3) each utility
edge has only one utility value (i.e., bu) if
setting the time-sensitivity to 45 minutes,
leading to a path utility score in-between
for this group. Furthermore, it can be
expected that the path utility score of the
discovered path by applying 2TD should
always be kept unchanged when time-

sensitivity is bigger than 45 minutes. In
this case, the problem of two-fold timedependent path finding degrades to only
one-fold time-dependent problem, since
the utility value remains unchanged for
all edges during the trip time. When
applying MA to solve the path-finding
problem, a similar group pattern but with
a much smaller corresponding path utility
score can be observed. Unlike the other
two algorithms, path utility scores
obtained by applying SRN do not present the similar group pattern.
In terms of the running time, with
2TD, all user queries can be responded
within 10 milliseconds. For the other
two algorithms, they take up the competitive running time. More specifically,
MA needs slightly more running time
than SRN. Although they need much
more running time when compared to
2TD, the performance is still acceptable
for almost all real time applications. We
can also observe that the average running time for all three algorithms fluctuates within a small range under different
utility time-sensitivities.
3) Varying Utility Density
Considering that the most significant difference in different city areas is the utility
density, we thus conduct the experiment
by varying the utility density based on
the synthetic road network, with the
results shown in Fig. 7. The other parameter settings are the same as the study of

0.8
2TD
MA
SRN

0.7

0.3
Running Time (s)

Path Utility Score

0.6
0.5
0.4
0.3

0.25
0.2
0.15

0.2

0.1

0.05
5

10
15
20
25
30
Utility Time-Sensitivity (mins)

2TD
MA
SRN

0.35

10
15
20
25
30
Utility Time-Sensitivity (mins)

FIGURE 6 Results of the path utility score and running time under different utility time-sensitivities for all three algorithms.

MAY 2021 | IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE

IEEE Computational Intelligence Magazine - May 2021

Table of Contents for the Digital Edition of IEEE Computational Intelligence Magazine - May 2021