IEEE Computational Intelligence Magazine - May 2021 - 80

fastest path in real time is more challenging. Thanks to the sustainable development and wide proliferation of the
positioning technologies (e.g., GPS) and
mobile Internet in daily life [3], [6], [7],
traffic conditions at different times have
become easily available. For example,
based on the obtained GPS-determined
locations and the trajectory data of drivers, some applications have implemented
a real-time traffic query service for people, such as WAZE and Google Traffic
[8]. With such information at hand, the
frequent measurement used in path
planning and navigation systems has
changed from the static distance to the
time-dependent travel time [5], [9].
In addition to the concern of the
total travel time cost, in real life, people
also tend to take a utility-rich path
according to their travel preference or
purposes [10]. For instance, drivers who
stay indoors for a long time are eager to
take a driving route with a beautiful scenic view, while policemen prefer to take
a patrol route with potentially high risk
to prevent crimes in time. In real scenarios, there are many forms of utility that
drivers may expect and the path can
carry, including the beauty score, the
safety/risky score, the happiness score
and so on [1], [11]-[14]. Therefore, neither the shortest path nor the fastest path
can meet the users' diverse requirements
[15], [16]. Instead, there is often a need of
multi-preference along with included edges of
the planned path for drivers. Fortunately,
with the increasing popularity of location-based social networks (LBSNs) and
the open data released from the government [17], [18], the accurate modelling
of many forms of the utility on each
edge over the road network (also known
as the road network enrichment) has
become a reality [19], [20]. For instance,
the crime data published by the government include some basic information
such as the geographical location, time,
and the type of crime occurred [18].
Such open data can be used to enrich
the safety/risky property of a given edge.
Consequently, beyond the shortest/fastest path, the safest path planning can be
supported over the enriched road network [18]. It should be noted that while

one may prefer a utility-rich path, there
is always a limit on the time budget that
needs to be traded off. Such problem can
be viewed as a variant of the Arc Orienteering Problem (AOP), which aims to
find an optimal path maximizing the
accumulated utility along the path while
not exceeding the travel time budget
imposed by users [13], [21], [22]. Hereafter, we use " arc " and " edge " interchangeably throughout the paper. It should also
be noted that, unlike the travel time
property that each edge has, some edges
may just have no utility value.
As a matter of fact, similar to the
travel time property (i.e., cost), the utility value on each arc shall also be
dynamic and time-dependent. For
instance, some arcs are more worth traveling at night due to a more beautiful
scenic; some edges are more dangerous
during the night time but are quite safe
during the daytime. Even more complicated, according to the nature of different utility forms, the time-changing
frequency can vary significantly. More
specifically, the scenic score on an edge
may only differ between day and night,
or different seasons, while the risky
score on an edge can change more frequently. In other words, the risky score
is high only when crimes are occurring
and quickly drops to zero after crimes.
Thus, its time-changing frequency is
tightly related to the occurrence of
crimes and also varies in different city
regions as well. Consequently, at different departure times, a unique path may
present a wide range of utility values,
especially in the case that utility value
changes frequently. Thus, the time dependence of the utility on each arc cannot be
neglected during the cause of path planning.
In summary, both utility value and cost
value on each directed edge are generally time-dependent.
In this paper, considering a more
general and realistic path planning scenario over two-fold time-dependent
road networks, we focus on discovering
the optimal path from the origin to the
destination which maximizes the total
utility value while the total travel time
does not exceed the user-specified time
budget. Due to the time-dependent fea-

IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE | MAY 2021

ture of both cost and utility on the arc, it
is named the Two-fold Time-Dependent
Arc Orienteering Problem [21] (2TDAOP for short in the rest of presentation). To the best of our knowledge,
there are few path-planners that can
solve 2TD-AOP, due to the following
two main challenges.
How to efficiently solve the
2TD-AOP is challenging. Solving
the 2TD-AOP is computationally challenging since the problem can be
viewed as a variant of AOP. On one
hand, AOP itself is well-known as an
NP-hard combinatorial optimization
problem [23], [24], especially for the
path-planning over the road network
typically including hundreds of thousands of road edges and intersections.
On the other hand, the 2TD-AOP is
more complicated due to the added
two-fold time dependence characteristics of the edge, especially when the cost
and utility on the edge change frequently. The complexity of the problem hinders the exact and efficient solvers.
How to find the high-quality
solution to the 2TD-AOP is challenging. Near-optimal solvers are
usually a perfect choice to get a highquality path within an acceptable
response time for 2TD-AOP, among
which evolutionary algorithms with the
chromosome encoding and decoding
are more preferred [25]. The objective
of the chromosome encoding is to
improve the solution quality locally and
iteratively while not violating any constraints. The constraints are easily
checked and preserved for static problems during the iterative operations of
chromosome encoding. On the contrary, for the 2TD problem, due to twofold time dependence, even a small
change on the previous path (e.g., using
a nearby edge to replace one in the previous path) may exceed the total travel
time budget and result in an invalid
path eventually.
With the above-mentioned research
objective and challenges, the main contributions of the paper are:
1) We define a more realistic driving
route planning problem (i.e., 2TDAOP) which allows both cost and

IEEE Computational Intelligence Magazine - May 2021

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