IEEE Computational Intelligence Magazine - May 2021 - 92

until exceeding the time budget. Finally, all gaps are filled using the timedependent fastest paths by recalling the
A) algorithm again. The newly nearby
and best utility edge selection is challenging, and SRN algorithm proposes
a number of technicals to obtain it efficiently and effectively, with details
shown in [22].
5) Experimental Environment
The proposed route planning algorithm
is coded using Python language. All programs are run on an Intel(R) Xeon(R)
Gold 6151 workstation with 192-GB
RAM and running Windows Server
2019 operating system.
B. Experimental Results

1) Varying Departure Time
To demonstrate the capacity of planning 2TD driving routes, we show the
perfor mance of 2TD algor ithm,
together with the two baselines, w.r.t
different departure times based on the
synthetic road network in Fig. 5. We
select 20 OD pairs in this experiment,
each of which is with a distance of
around 10 km. The time budget and
utility density are set to 45 minutes and
10% respectively. Both the average
value and the standard deviation value
are used to show the overall performance of all OD pairs. Since the utility

and the travel time on each edge are
time-dependent, based on the same
origin, destination, and time budget,
the algorithms may generate different
paths when varying departure time.
Therefore, there is the difference
among utility scores under different
departure times for 2TD, MA and
SRN, as can be observed. Similar to
the utility score, the running time is
also different due to the different
reachable edges at different departure
times. As shown in Fig. 5, 2TD algorithm obtains the highest path utility
score taking up the shortest running
time consistently, compared to the
other two baseline algorithms.
In terms of the path utility score,
2TD can always discover the driving
route with the highest utility score,
SRN obtains the driving route with
the worst utility score, while MA
returns the driving route with the utility score in-between. This is because:
1) compared to MA, 2TD is able to
make a better tradeoff between the
population diversity and quality. To
ensure the population diversity, MA
only considers the degree of geographical reachability when inserting new
utility edges, which is the same at different departure times. The utility edge
that can truly lead to a high-quality
solution is very likely to be missed. 2)
SRN only works on top of the time-

0.35

0.8
2TD
MA
SRN

0.7

2TD
MA
SRN

0.3
Running Time (s)

0.6
Path Utility Score

dependent fastest paths when selecting
and inserting new utility edges, and
only the best utility edge can be
inserted at each iteration, resulting in
very little diversity. Moreover, approximation techniques used to determine
the best utility edge might be not
accurate adequately [22].
In terms of the running time, 2TD
requires the least, MA requires the
most, while SRN needs the running
time in-between. The result demonstrates the excellent features of our proposed 2TD algorithm. More precisely,
1) to avoid redundant validity-checking,
2TD builds a timetable clearly showing
the reachability degree of each utility
edge at different times during the trip
time. 2) Meta-heuristics are welldesigned and applied at each iteration
when inserting utility edges for the
purpose of controlling the number of
population yet ensuring the diversity.
The reason MA requires the longest
running time is due to the huge
amount of population generated. Actually, compared to SRN, the path utility
score improvement is achieved at the
cost of more running time [21]. An
interesting phenomenon is that, compared to the other two algorithms, the
average running time of SRN fluctuates
at different departure times. This is
mainly because that the inserted utility
edges are different (both number and

0.5
0.4
0.3
0.2

0.25
0.2
0.15
0.1
0.05

0.1
0:00

6:00
12:00
Departure Time

18:00

0:00

6:00
12:00
Departure Time

FIGURE 5 Results of the path utility score and running time under different departure times for all three algorithms.

IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE | MAY 2021

18:00

IEEE Computational Intelligence Magazine - May 2021

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