IEEE Computational Intelligence Magazine - May 2021 - 96

the time budget is significant since the
actual utility density in NYC road network is quite big.
6) Varying Road Network
To demonstrate the system performance
in different road networks, we test 2TD
algorithm together with the two baselines in different road networks, i.e.,
SFC, NYC, CD, CQ. We select 20 OD
pairs with the distance of around 4 km
in each road network. The time budget
is set to 20 minutes. We fixed the departure time to 9:00. To exclude the
potential effect caused by different utility densities, we generate utility edges in
different road networks using the same
way to that in synthetic road network.
The utility density is set to 10% for all
road networks in this study. In summary,
as shown in Fig. 10, 2TD algorithm
obtains the highest utility score taking
up the shortest running time consistently, compared to the other two baseline algorithms.
In terms of the path utility score,
2TD finds the path with the highest
utility score under different road networks, SRN obtains the driving route
with the worst utility score, while MA
returns the driving route with the utility score in-between. In addition, we
can observe that there is a significant
difference between the group of SFC
and the other groups. Specifically, the

utility group of SFC has the highest
utility score for all algorithms. This is
because the average length of edge of
SFC is smallest. In more detail, the
average edge length of SFC is about
78.9 meters while the average edge
length of NYC is about 113.9 meters.
Based on this situation, the route with
the same distance from origin to destination in SFC can contain more edges
than other cities. Since road networks
have the same utility density, the routes
in SFC include a bigger number of
utility edges.
In terms of the running time, 2TD
requires the least, MA requires the
most, while SRN needs the running
time in-between. We can also observe
that there are differences between different road network g roups. The
group of NYC requires the least for
all algor ithms, the group of SFC
requires the most, while groups of
CQ and CD need more running time
than NYC. This is because a constant
size search region contains different
numbers of edges in different city
road networks. The more edges the
search reg ion contains, the more
validity-checking times it needs. The
number of edges contained in a
search region is determined by the
following factors: 1) The edge length
in the road network. Obviously, a
search region could contain more

2.5

1.5
1

2TD
MA
SRN

15
Running Time (s)

Path Utility Score

7) Effectiveness of Utility Edge
Selection Rules and Secondary
Selection
To demonstrate the effectiveness of utility edge selection rules and secondary
selection in the chromosome encoding,
2TD is modified to other 5 variants, i.e.,
2TD without Rule 1 (w/o_R1), 2TD
without Rule 2 (w/o_R2), 2TD without
Rule 3 (w/o_R3), 2TD without Rule 4
(w/o_R4) and 2TD without secondary
selection (w/o_ss) respectively. We test
the algorithms under different departure
times based on the real-world road networks of SFC and NYC in Fig. 11. We
select 20 OD pairs from SFC with the
driving distance of around 1.5 km and
NYC with the driving distance of
around 4 km. The average value is used
to show the overall performance of all
OD pairs. We will present the analysis in
detail, as follows.

20
2TD
MA
SRN

0.5

edges when the edge is short. The
group of SFC requires the most for all
algorithms since it has the shortest
edge length among all road networks.
2) The distr ibution of nodes and
edges. Compared to the NYC, CQ
and CD have denser distribution of
nodes and edges. This is why groups
of CQ and CD need more running
time in some cases than the group of
NYC, even though they have longer
edge than NYC.

SFC

NYC
CD
Road Network

SFC

NYC
CD
Road Network

FIGURE 10 Results of the path utility score and running time under different road networks for all three algorithms.

IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE | MAY 2021

IEEE Computational Intelligence Magazine - May 2021

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