IEEE Computational Intelligence Magazine - May 2021 - 95

which indicates that the number of
population cannot grow significantly
with the utility density.
4) Varying Driving Distance
To demonstrate the scalability of our
developed system, we test 2TD under
different driving distances based on the
real-world road network in SFC, with
the results shown in Fig. 8. 5 OD
groups with the driving distance from
1 km to 3 km with an equal interval of
0.5 km are used in this study. Each OD
group includes 20 OD pairs. The time
budget for each OD pair is set to double
the corresponding fastest travel time.
The departure time is set to 9:00. The
utility density t is 18.9%.
In terms of the path utility score,
2TD obtains the highest path utility
score consistently for all driving distances. For all three algorithms, their standard
deviation values are much bigger compared to the results based on the synthetic road network. This is because the
utility edge distributes quite unevenly
around the city in the real-world road
network. Furthermore, a small amount
of utility edges has an extremely high
value, as evidenced in [1], [22]. Therefore, it is obvious that the path utility
score of OD pairs selected from areas
containing such high-value utility edges
should be high. Another interesting but
counterfactual observation is that the

path utility score does not increase with
the driving distance rigidly. Again, this is
because most of OD pairs belonging to
the first group (with the driving distance
of 1 km) and the third group (with the
driving distance of 2 km) are biased
selected from dense and sparse utility
edge areas respectively.
In terms of the running time, 2TD
needs the shortest for almost all driving
distances. As predicted, for all three algorithms, the running time grows with the
driving distance, since the search space
expands. MA is most sensitive to the
search space, i.e., its running time
increases exponentially. It needs an average running time of around 25 seconds
to return results for OD pairs with the
driving distance of only 3 km. 2TD
requires slightly more running time as
the driving distance gets longer. This is
because distant OD pairs bring a big
search space which contains more
reachable edges. Based on the edges, the
running time increases from three parts,
i.e., edge reachability computing, chromosome encoding and decoding respectively. They can respond to user queries
within 4 seconds, as can be observed.
5) Varying Time Budget
To quantitatively demonstrate the potential improvement in the path utility score
when users impose a more flexible time
budget, we test the proposed system by

160

0.012
2TD
MA
SRN

2TD
MA
SRN

140
120
Running Time (s)

0.01
Path Utility Score

varying the time budget based on the
NYC real-world road network, with
the results shown in Fig. 9. In this study,
we select 20 OD pairs with the driving
distance around 4 km. The departure
time is set to 9:00. The utility density t
is 54.9%.
In terms of the path utility score,
both 2TD and MA get a consistently
higher path utility score if the time
budget gets longer. It is because they
are able to insert more and better utility edges when increasing the time
budget. However, such case does not
happen to SRN. This is because SRN
can insert only one utility edge at
each iteration, probably resulting in
the local optimum. More specifically,
with the increase of the time budget,
SRN may insert a much better utility
edge at the very beginning, but it may
also use up the time budget which
forbids adding more utility edges in
next iterations.
In terms of the running time, both
2TD and MA require even more as the
time budget gets longer while SRN
needs the least running time and is
almost unchanged for all time budgets.
Compared to 2TD, the running time
of MA grows exponentially. This is
because a longer time budget also
implies a bigger search space. The number of utility edges in the expanded
search space caused by the increase of

0.008
0.006
0.004
0.002

100
80
60

20
15
10
5

20
12

16
18
Time Budget (min)

FIGURE 9 Results of the path utility score and running time under different travel budgets 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