IEEE Computational Intelligence Magazine - May 2021 - 88

Appendix A
Complexity Analysis
The compsilexity of the proposed 2TD algorithm can be calculated as:

O (2T D) = O (E R) + O (C E) + O (C D) (1)

in which O (ER), (CE) and O (CD) refer to the complexity of operations of edge reachability computing, chromosome encoding,
and chromosome decoding respectively.
Complexity of edge reachability computing. It includes
the computation of edge reachability timezone identification
and edge reachability timetable construction, with the computation complexity of n # c 1 and O (n log 2 (n)) . n is the number of
utility edges in the intersection region. c 1 is a constant, referring
to the complexity of the reachability timezone identification for
one edge. O (n log 2 (n)) stands for the complexity of edge reachability ordering. Therefore, O (ER) = O (n + n log 2 (n)) holds.
Population size approximation. A population of chromosomes is generated by iterative operations of utility edge selection and chromosome growing. In fact, all selected utility edges
can be organized in the form of a diamond-like tree, as shown in
Fig. 1. As can be observed, a path from n o to n d containing a utility edge sequence corresponds to a resultant chromosome, such as
G e 12, e 56, e 78 H. We can also observed that the population size
is exactly equal to the number of utility edges in the h-th
level of the diamond-like tree. Thus, the population size is upperno
e12
e56
e78

bounded by the number of utility edges in the h-th level. In general, as the level number increases, the number of utility edges in each
level increases first and then decreases. In the worst case, each
node in the diamond-like tree has four children, resulting in a 4-full
tree ( n d is excluded). Therefore, the population size is upper-bounded by 4 h , which is denoted as C ub = 4 h . The size of the diamondlike tree is defined as the total nodes it contains ( n o and n d are
excluded), i.e., the sum of all utility edges in different levels. Its upper
bound is denoted by E ub, and we have E ub = R hi = 1 4 h .
Complexity of chromosome encoding. There are two basic
operations, including utility edge selection and utility edge inserting, with the computation complexity of n # c 2 and c 3, respectively. n is the average number of utility edges in the timetable that
needs to be compared during the utility edge selection (Readers
can refer to Lines 17-28 in Algorithm 1 for details). In the worst
case, all utility edges in the timetable are compared when
checked every time. Thus, n is upper-bounded by the number of
all utility edges in the road network. c 2 and c 3 are constants,
referring to the complexity of checking in the timetable and utility
edge inserting for an edge. The number of executions depends on
the total number of utility edges in the diamond-like tree shown
in Fig. 1. Therefore, in the worst case, the computation complexity
should be E ub # (n # c 2 + c 3) , i.e., O (CE) = O (n # 4 h).
Complexity of chromosome decoding. We visit all chromosomes and fill the gap between the two consecutive utility edges
for each chromosome. The basic operation is the gap-filling. Here, we
also calculate the upper bound of gap-filling
number. Specifically, in the worst case, the
number of chromosomes is C ub and all chroLevel 1
mosomes contain h levels. In other words, each
Level 2
chromosome has h + 1 gaps. Thus, the computation complexity is C ub # (h + 1) # c 4 , where
Level 3
c 4 is a constant, referring to the complexity
Level 4
of gap-filling. Therefore, O (CD) = O (h # 4 h) .
Putting all computation complexity terms
together, we have:
Level h

O (2TD) = O (n + n log 2 (n) + n # 4 h + h # 4 h)
(2)

nd
FIGURE S1 Illustration of the diamond-like tree. Each path from the origin to the destination refers to a chromosome.

❏❏ Question 4: How does the system per-

❏❏ Question 5: How does the system per-

form for OD pairs with different driving distances? The experiment is
designed to evaluate the system
scalability, since the search space
over the road network generally
grows when the driving distance
increases.

form and what are the differences when
users impose a more flexible travel budget? The experiment is to test the
potential " benefits " that can be
gained if allowed a longer travel time
budget. In addition, it also can be
served as a nice guide for users to

IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE | MAY 2021

In the actual route planning scenarios, n
and h are both affected by the real-world

better determine their time budgets
in advance.
❏❏ Question 6: Can the system work robustly for different road networks? This
experiment is to examine whether
the proposed system can be used in
different cities since the distribution
of nodes and edges varies.

IEEE Computational Intelligence Magazine - May 2021

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