IEEE Computational Intelligence Magazine - May 2021 - 87

Lines 2-3 are the initialization for the
set of chromosomes Chr and the set of
child edges E. Lines 4-5 correspond to
the utility edge selection. In more detail,
based on the n o and t 0 , the child edges
are selected from the timeTable according to the Rule 1, Rule 2, Rule 3 and
Rule 4 and stored in the set E. Note
that the utility edge selection is implemented by the selectUE() function.
Lines 6-15 correspond to the chromosome growing. More specifically, if E ! 4 ,
for each e ! E , we conduct the following set of updates. First, we update the
departure time t 0 to t 0 + Tavg (n 0, e)
(Line 8). Here, we simply use the
departure time of no and average travel
time from n o to e to approximate the
departure time of e (Line 9). Second,
we update the no to the tail node of e,
i.e., e is set as the parent edge in the
next iteration. Line 10 calls the function encoding() recursively to generate
the child chromosome branches for e.
Afterwards, the child branches are
combined with e one by one, resulting
in a set of complete chromosomes
(Line 13). Line 16 represents that all
chromosomes in the population are
obtained and returned after visiting all
elements in E.
Lines 17-28 descr ibe the
selectUE() function which implements the utility edge selection based on
a certain heuristic rule. Lines 18-20 are
the initialization for the candidate edge
set candidateE and the departure time
of an edge t(e). Line 20 obtains the
edge e from the timetable according to
the given rule. Line 21 indicates that e
is stored in set candidateE. To ensure
that e is reachable, we need to identify
which timezone the departure time of
e (i.e., t(e)) is located at. Here, we
approximate t(e) by t 0 + Tavg (n 0, e)
(Line 22). Lines 23-27 represent that if
t(e) is located at the critical timezone
[Ct (e), Ut (e)] , the utility edge secondary
selection is applied based on the same
given rule to make sure at least one
valid chromosome is generated. Specifically, we choose the second candidate
edge from the timetable and store it in
the candidateE at the same time (Lines
26-27). In this case, more than four

utility edges are selected. Finally, candidateE is returned (Line 28).
To better understand the procedure of
chromosome encoding, we use an example to illustrate, as shown in Fig. 4. As for
the concrete example, four utility edges
{e12, e34, e56, e78} are selected based on the
four heuristic rules in the first iteration.
As a result, we obtain four chromosomes
{G e 12 H , G e 34 H , G e 56 H , G e 78 H} in total. In
the next iteration, the four edges are set
as parent edges in the chromosomes. For
each parent edge in the chromosome, its
child edges are selected by the utility edge
selection again. For instance, for the chromosome G e 12 H , based on the parent
edge e12, three child edges {e34, e78, e56}
are selected. It should be noted that two
utility edges are selected based on the
same Rule 1. This is because the departure time t (e 34) is located at the critical
timezone of e34. Under such circumstance, utility edge secondary selection is
triggered and the second edge e78 is also
selected. Finally, three new chromosomes {G e 12, e 34 H , G e 12, e 78 H , G e 12, e 56 H}
are growing.

into the corresponding path, it is easy
to obtain the true travel time and
path utility. It should be noted that
path utility is not just the summarization of all utility edges in the chromosome because some extra utility
edges can also be included during the
gap-filling. Finally, among all chromosomes in the population, the path
having the highest path utility while
not exceeding the total travel time
budget is returned as the final result
for the given user query.
The complexity analysis of the proposed 2TD algorithm can be found in
the Appendix A.
V. Evaluation
A. Experimental Setting

1) Experimental Objectives
We design a number of experiments to
address the following questions:
❏❏ Question 1: What are the differences if
a user starts the same trip at a different departure time? The experiment
is to demonstrate the system's
capacity of planning the 2TD driving routes.
❏❏ Question 2: Can the system work adaptively for different kinds of utility? This
experiment is to examine whether
the proposed system can handle different utilities, since the utility in real
cases may present many forms which
have quite distinct and inconsistent
time-sensitivities.
❏❏ Question 3: How does the system perform under different utility densities?
This experiment considers the fact
that users may be interested in different areas of the city while travelling,
and the utility density in different
areas is also varied.

3) Chromosome Decoding
via Gap-Filling
For an encoded chromosome, the
objective of decoding is to fill the gap
between two consecutive utility edges
since they are generally disconnected
in the road network, i.e., finding the
operational driving path over the road
network. Among all gaps, the first gap
of the chromosome is located between
the origin and the first utility edge,
and the last gap is located between the
last utility edge and the destination.
For the sake of not exceeding the
total travel time budget, we simply
adopt the shortest paths to fill gaps.
Once the chromosome is decoded

n0
e78
e56
e34
e12
t0

t (e34)

t0 + b

R1:e34

R1:e12

R2:e34

R3:e56

R1:e78

R2:e56

.....

R7:e78

FIGURE 4 Illustration of the utility edge selection.

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