IEEE Computational Intelligence Magazine - May 2021 - 82

intensified restart mechanism. [32]
designed two insertion methods by considering the time-dependent travel time.
Specifically, the first method selected a
node which would be inserted to the
path based on the corresponding insertion cost, while the second method
involved a more global criterion since it
considered the effect of insertion on the
whole path. These algorithms improved
the route quality by the local optimization operation. Due to the time dependence of travel time, the arc insertion
causes an update of the whole path
which needs a lot of computing
resources. Moreover, the search space is
not explored thoroughly, making it difficult to find a high-quality solution. To
obtain a higher-quality of solution, some
evolutionary algorithms including the
genetic algorithm (GA), the memetic
algorithm (MA) and the ant colony system (ACS) are proposed [33]. To name a
few, [34] proposed an evolutionary strategy based on GA in which chromosomes with variable lengths are used to
generate populations. [35] combined the
principles of ACS with a time-dependent local search procedure. [36] proposed MA in which problem-specific
crossover and local search operators are
designed to handle the time-dependent
travel time. These algorithms can better
explore the search space at the cost of
the computation time, since the local
search is time-consuming.
In addition to the travel time, the utility on each arc is time-dependent. Finding an optimal route considering the
two-fold time dependence is a more
realistic yet challenging problem. To the
best of our knowledge, few route planning algorithms are proposed to solve
the 2TD-AOP. For instance, [22] developed a heuristic algorithm to improve
the quality of the path by adding nearby
arcs on top of the initial path. [21] proposed MA which generates a population
consisting of multiple routes by a heuristic encoding rule. However, those two
algorithms are proved to be effective in
handling the time-dependent scenic
score which may only differ between day
and night. In other words, the scenic
score on the arc may stay unchanged

during the whole trip. When the utility
on the arc changes more frequently, such
as risky score, those algorithms cannot be
applied directly.
III. Concepts and Problem
Statement
A. Basic Concepts

Definition 1 (Road network). A road
network is a graph G = (N, E) consisting of
nodes and edges, where N denotes the set of
nodes including intersections and dead-ends;
E 3 N # N denotes the set of directed edges.
Definition 2 (Utility edge). We
define an edge having utility value bigger
than 0 as a utility edge. More generally, the
utility here can be either helpful such as the
enjoyment gained or harmful such as the risk
exposed while driving through the edge. It
should be noted that all utility values are
positive ones, indicating the degree of gain
or risk.
Unlike the travel time property that
each edge contains, we assume that the
number of utility edges in the road network is small and limited. We believe that
such assumption is well-suited to real
cases. For example, only a small fraction
of edges is beautiful and has scenic value.
Similarly, the number of risky edges in a
city is also small. Specifically, as evidenced in [1], [37], the ratio of the scenic edges is around 20% in the Bay Area,
the City of San Francisco.
Definition 3 (Utility density). We
define the ratio of the number of utility edges
to the total number of edges for a given road
network as the utility density.
Definition 4 (Two-fold time
dependence). Both utility value and travel
time value on each directed edge are timedependent.
Definition 5 (Utility time-sensitivity). The utility time-sensitivity is used to
measure the changing frequency of the utility
value, which is quantified by the time interval
of the utility value change.
According to the meaning of defined
utility on the edge, the time-sensitivity
can vary a lot. For instance, if the utility
is the scenic score on the edge, the
time-sensitivity can be hours; on the
other hand, if the utility is the risky
score on the edge, the time-sensitivity is

IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE | MAY 2021

much smaller and can be just a few minutes during some time periods.
Definition 6 (Path). A path is a
sequence of connected edges or nodes in the
road network. A path from a source node n 0
to a destination node n k when departing at t 0
can be denoted by p = G (e 0, 1, e 1, 2, g,
e k - 1, k), t 0 H . Alternatively, a path can also be
represented by a sequence of connected nodes.
Thus, depending on which one is more convenient, we may represent the path either via the
sequence of edges or via the sequence of nodes.
Definition 7 (Path utility and cost). The
utility and cost of a path p = G (e 0, 1, e 1, 2, g,
e k - 1, k), t 0 H are defined according to the following two equations:

C (p) =

/ C (e i - 1,i, t i - 1)(1)

i=1

U (p) =

/ U (e i - 1,i, t i - 1)(2)

i=1

where t i denotes the time of arrival at ni of
e i, i + 1 ; C (e i - 1, i, t i - 1) and U (e i - 1, i, t i - 1)
denote the travel time and the utility on the
edge (e i - 1, i) at the departure time of t i - 1 ,
respectively. It is easy to conclude that
t i - t i - 1 = C (e i - 1, i, t i - 1) holds.
Definition 8 (Gap and gap-filling).
A gap commonly exists between two utility
edges since they are generally disconnected in
the road network. The purpose of gap-filling
is to fill such gap using the path discovered by
some popular path-finding algorithms, e.g.,
the A ) shortest path-finding algorithm.
Note that the gap-filling shortest path can
also contain the utility edge(s).
Definition 9 (User query). A user
query is defined as a quadruple G n o, n d, t 0, b H
in which n o and n d refer to the origin and destination of the user; t 0 and b refer to the departure time and the time budget of the trip
respectively. Note that, in fact, the user may start
and end the trip at the arbitrary positions in the
road network. In this case, we simply identify
their nearest nodes as the origin and the
destination.
B. Problem Statement

As discussed, the 2TD-AOP can be
viewed as an optimal path-finding one. In
more detail, the objective is to find the
travel path p = G (e 0, 1, e 1, 2, g, e k - 1, k), t 0 H
over a road network (G) which maximizes the path utility while the path

IEEE Computational Intelligence Magazine - May 2021

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