IEEE Computational Intelligence Magazine - May 2021 - 85

the given edge at the time in the range
of critical timezone, uncertainty whether
the user can reach the destination or not
by the deadline exists. In this case, if the
edge is selected and added to the travel
route, the user may reach the destination
exceeding the time budget; in other
words, an invalid route may be generated. If the edge is abandoned directly, the
utility of the edge cannot be obtained,
which is not conducive to the high-utility route. The situation is identified by
critical timezone separately for the subsequent route planning.
Remarks. For all edges in the road
network, given the user query, it can
still be time-consuming to determine
their reachability due to the large scale.
In fact, there is no need to check all of
them since most of them can be safely
excluded in advance. To be more specific, based on the simple method discussed in [21], it is only necessary to
compute the reachability of the edges
lying inside the intersection between
two equal-sized circles (i.e., the origin
and destination are the two centers, and
the radius is the product of the average
speed at the departure time and the
time budget).
2) Edge Reachability Timetable
Construction
There is a set of reachable edges under
the given user query, with quite different edge reachability timezones. A
question regarding how to organize them in
an orderly fashion arises naturally. Obviously, the objective of ordering is to
facilitate the following chromosome
encoding. As discussed, the chromosome encoding is an iterative procedure by inserting an edge into the
previous chromosome at one time.
Meanwhile, validity of the newly generated chromosome needs to be
checked by chromosome decoding
(i.e., comparing the travel time of the
decoded path to the allowed time
budget). Therefore, such cumbersome
procedure wastes plenty of computation resources and time, especially
when the number of edges is large or
the time budget is long. To alleviate
the issue, we wisely propose the solu-

tion of reachability timetable construction,
consisting of insertable edge identification and edge reachability ordering,
detailed as follows.
Step 1: Insertable edge identification. For each reachable edge, we first
identify the corresponding timezone.
More importantly, we record values of
Ut for all edges, since it can be used to
quicken the validity-checking without
chromosome decoding. More specifically, whether an edge (eij) can be inserted
or not can be easily identified by comparing t (e ij) to Ut (e ij), where t (e ij) is the
time when the user departs from eij. If
t (e ij) # Ut (e ij), eij is insertable; otherwise,
eij is not insertable. It should be noted
that once an edge is inserted, t 0 is
updated by t. For example, as shown in
Fig. 3, t 0 = t (e 56) if the edge e56 is firstly inserted.
Step 2: Edge reachability ordering.
We sort all reachable edges according to
the corresponding Ut value in the
ascending order, as shown in Fig. 3. Such
ordering also facilitates the identification
of insertable edges and chromosome
encoding further. In more detail, to
identify insertable edges, one may

require to repeat Step 1 for all reachable
edges at each iteration. As a matter of
fact, reachable edges with t 0 2 U t can
be safely excluded in advance. Thus,
with the simple ordering mechanism,
the number of reachable edges input
for Step 1 shrinks gradually, leading
to the efficiency improvement on
chromosome encoding. Taking the
example shown in Fig. 3 again, there
is no need to check whether e12 and
e 34 are insertable any more, because
both Ut (e 12) and Ut (e 34) are smaller
than t (e 56) .
C. Chromosome Encoding
and Decoding

A chromosome is encoded and generated via iterative utility edge inserting,
given the user query, consisting of
utility edge selection and chromosome growing. The utility edge sequence (i.e.,
chromosome) is converted into an
operational driving path via chromosome decoding.
1) Utility Edge Selection Rules
Aiming to discover the optimal driving path with the highest utility

Reachable Timezone
Critical Timezone
Unreachable Timezone

Tavg (eij , nd )
Tmin (eij , nd )

Tmin (no , eij)

eij
t0

t0 + b

FIGURE 2 Illustrative example of three key time concepts for an edge and reachability timezone
division.

e34
e78

e12

no
e56

e78
e56
e34
e12
t0

t0 = t

t0 + b

FIGURE 3 Illustration of time table construction.

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