IEEE Computational Intelligence Magazine - May 2021 - 84

and path utility. Through simple path
ranking, the path having the highest
path utility while not exceeding the
travel time budget is picked as the
final result.
B. Edge Reachability Computing

Without loss of generality, we introduce
the computing method of reachability
for all edges in the road network. However, as discussed, only the reachability
computing of utility edges is required.
1) Edge Reachability Timezone
Identification
Definition 10 (Edge reachability). Edge
reachability is defined on top of the user
query. More specifically, given a user query
G n o, n d, t 0, b H, an edge is reachable if and
only if it can be included by at least one path
from n o to n d , at the departure time of t 0 ,
making the total travel time less than b. It is
challenging and time-consuming to determine
the edge reachability by the user query since
many paths can include the given edge, costing different travel times.
It is easy to understand that only
reachable edges can be included in the
planned path. In order to determine the
edge reachability more efficiently, we
introduce three more key time concepts
for an edge, i.e., its earliest arrival time,
latest departure time and critical departure time, detailed as follows.
Definition 11 (Earliest arrival time).
For a given user query (G n o, n d, t 0, b H) and
an edge (e ij ), the earliest arrival time of the
edge is defined as the earliest time when the
edge can be reached from the origin.
The accurate computation of the earliest arrival time is non-trivial, since the
time cost from the given origin at the
departure time to the given edge mainly
depends on the specific travel path and
real-time traffic conditions on each edge
included in that path. However, we can
estimate a lower bound for the earliest
arrival time. Specifically, the shortest
path from the given origin to the edge
can be discovered. On top of the discovered path, it is also easy to know the
maximum travel speed on each included
edge (e.g., OpenSreetMap platform provides the information about speed limits
for each edge in the road network). Ide-

84

ally, the least time cost from the origin
to the given edge (Tmin (n o, e ij) ) can be
obtained by summarizing the ratios of
the distance of each edge ( dist (e mn) )
included in the shortest path to its
allowed speed limit ( v max (e mn)), as shown
in Eq. 11. We can safely claim that the
edge is not reachable when Tmin 2 b .
The lower bound of the earliest arrival
time ( Lt (e ij) ) can also be tr ivially
derived according to Eq. 12. For simplicity, we suppose that the earliest arrival time is equal to its lower bound.
	
	

Tmin (n o, e ij) = /

dist (e mn)
(11)
v max (e mn)

Lt (e ij) = t 0 + Tmin (n o, e ij)(12)

Definition 12 (Latest departure
time). The latest departure time for an edge
(e ij ) under a given user query (G n o, n d, t 0, b H)
is defined as the latest departure time from the
given edge to the destination. In other words, if
the user departs from the edge eij later than
that time, then he/she cannot arrive at the
destination (nd) by the deadline.
Similarly, it is also challenging to
accurately compute the latest departure
time. We also estimate the upper bound
and use it to approximate its value,
according to Eq. 13.
	

Ut (e ij) = t 0 + b - Tmin (e ij, n d)(13)

where Tmin (e ij, n d) refers to the least
travel time cost from the edge (e ij ) to
the destination n d that is calculated
based on Eq. 11. We can also safely
claim that the user cannot arrive at the
destination within the time budget if
he/she departs from the edge (e ij ) later
than Ut (e ij).
Definition 13 (Critical departure
time). The critical departure time for an edge
(e ij ) under a given user query (G n o, n d, t 0, b H)
is defined as the critical time that the user
should depart from the edge. In other words, if
the user departs before that time, he/she can
arrive at the destination by the deadline safely.
Ideally, the critical departure time
should equal the difference between
t 0 + b and Tmax, in which Tmax refers to
the largest time cost from the given
edge to the destination. The case when
the user chooses the longest driving

IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE | MAY 2021

path from the given edge to the destination with the lowest travel speed should
generate the largest time cost. Compared to the other two time concepts, it
is even more challenging to compute
Tmax. First of all, it is difficult to find the
longest driving path and compute the
corresponding distance. Worse still, the
lowest speed on each edge included in
the longest dr iving path is also
unknown. Here, we simply use Tavg to
approximate, which is obtained by summarizing the ratios of distance of each
edge included in the shortest path from
the given edge to the destination to the
average travel speed on that edge, as
shown in Eq. 14.
	

Tavg = /

dist (e mn)
(14)
v avg (e mn)

Afterwards, the critical departure time
can be computed as follows:
	

Ct (e ij) = t 0 + b - Tavg (e ij, n d)(15)

Theorem 1. For any reachable edges (e ij )
under the given user query (G n o, n d, t 0, b H), the
following inequation holds.
t 0 # Lt (e ij) # Ct (e ij) # Ut (e ij) # (t 0 + b)
On the contrary, if the three key times of an
edge does not satisfy the above inequation, we
can also definitely claim that it is not reachable under the given user query.
Proof. The theorem can be proved
by simple comparisons, as illustrated in
Fig. 2. 
o
Based on the three key time concepts,
we can not only determine edge reachability efficiently (according to Theorem
1), but also divide the trip time duration
(i.e., [t 0, t 0 + b] ) into three non-overlapped timezones, as shown in Fig. 2.
The three timezones correspond to three
cases, respectively. Specifically, when the
user departs the given edge at the time
in the range of reachable timezone, the user
can arrive at the destination by the deadline at hundred percent; when the user
departs the given edge at the time in the
range of unreachable timezone, the user
cannot reach the destination by the
deadline for sure; when the user departs
IEEE Computational Intelligence Magazine - May 2021

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