IEEE Computational Intelligence Magazine - May 2021 - 89

situations (e.g., road network structure
The upper bound of h is exactly equal to
and urban development) and the user
the
number of utility edges in the longest
q
query (e.g., the time budget, distance
path from n o to n d , which can be approxibetween n o and n d ). Under the given
mated according to Eq. 6.
user query, n and h are both not big,
k # dist (n o, n d)
hence, the efficiency of 2TD can be
E # tE

(6)
h = ;;
dc
guaranteed.
p
n
n
o
d
For the sake of clarity, we further provide an example to investigate the quanTaking a general scenario of the road network in
titive relationship between n and h, as
the city center as an example, in which d c = 120
shown in Fig. 2. In the example, all edges
meters, t = 10%, k = 2, dist (n o, n d) = 5 km,
are with equal length and they are evenly
we get n = 976 and h = 6.
distributed over the urban space. In this
Remarks. Although the time complexity of
FIGURE S2 Illustration of the estimation
case, the edge length is a key indicator
2TD is exponential, the planning efficiency
method of n and h.
of the density of the urban road netcan be guaranteed. We give the following
work. The smaller the edge length, the
explanations:
more denser the road network. To ease the presentation, we ❏❏ The upper bound of population size 4 h is unreachable in realiuse d c to represent the average edge length; v max refers to the
ty. In the approximation of population size, we assume that
speed limit; t refers to the utility density; dist (n o, n d) refers to
each node in the diamond-like tree has four children,
the shortest distance between n o and n d in the road network.
resulting in a 4-full tree. It means that there will always be
We set the time budget to kb, where b = dist (n o, n d) /v max .
4 child edges that can be selected from the edge timetable
Given the user query, it is trivial to get the intersection range in
and appended to each parent edge in the encoding. Howthe road network, as highlighted in the red region in Fig. 2. On
ever, in reality, there are fewer and fewer reachable edges
top of the intersection range, we draw a rectangle that tightly
in the timetable as the time budget decreases. The operacontains it. The problem now changes to the estimation of the
tion of chromosome encoding performs until there are no
number of utility edges in the rectangle. The height and width of
reachable edges in the timetable. Therefore, the actual size
the rectangle (p and q) can be computed according to the followof a diamond-like tree is much smaller than a 4-full tree.
ing equations:
❏❏ h is a very small number in the actual route planning scenarios. As shown in Fig. 1, h refers to the chromosome level.
dist (n o, n d) 2
m
p = 2 # (k $ dist (n o, n d)) 2 - c

(3)
The upper bound of h is exactly equal to the number of util2
ity edges in the longest path from the origin to the destinaq = 2 # k $ dist (n o, n d) - dist (n o, n d) (4)

tion. Equation 6 is proposed to approximate h. We firstly
calculate the longest travel distance by multiplying the travel
where k $ dist (n o, n d) is the radius value of the circles that is used
maximum speed (i.e., the road speed limit) and the given
to determine the intersection region [21].
time budget. Obviously, the actual travel distance is much
Afterwards, the number of utility edges can be calculated
smaller than the longest distance. Then, h is obtained by
according to the following equation:
multiplying the utility density and total edges in the longest
distance. Therefore, in reality, h is also much smaller than
p
q
q
p

(5)
the approximation.
n = ;;cc m - 1 m # c m + cc m - 1 m # c mE # tE
dc
dc
dc
dc
In a nutshell, the exponential parts of the time complexity of
in which 6 $ @ and ^ $ h refer to rounding down and up operations
2TD will not take up too much computing resources in actual
respectively.
route planning scenarios.

We answer the first three questions
based on one synthetic road network, and
answer the last three questions based on
four real-world road networks.
2) Data Preparation
Both synthetic and real-world road
networks are used to evaluate the per-

formance of 2TD system. Some statistics about the synthetic road network
can be found in Table I. For instance,
the edge distance ranges from 600 to
1,000 meters with an average value of
800.9 meters. For the time-dependent
travel time property on each edge, we
adopt a simple way to produce. To be

specific, we set the average driving
speed at all edges to 22 km/h, and
obtain the average travel time by
dividing the edge distance by the average speed for each edge. We name such
travel time as the basic travel time. To
simulate its time-dependence, we
obtain different time-dependent travel

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