IEEE Computational Intelligence Magazine - May 2021 - 81

utility on each edge in the road network to vary from time to time.
More generally, we further implement and investigate two typical
forms of utility (i.e., scenic and
risky) with quite distinct timechanging frequency to step closer to
real situations.
2) We propose the 2TD Path-Planner to solve the 2TD-AOP, which
belongs to the family of evolutionary algorithms. In more detail, to
avoid generating invalid paths, during chromosome encoding, we
compute the edge time-dependent
reachability in advance and generate the chromosome using the
reachable edges sequentially. A
timetable is built to manage all
reachable edges, which not only
eases the preservation of chromosome validity but also guarantees
the efficiency of the chromosome
encoding. Furthermore, we propose
four heuristic rules to guide the
chromosome encoding to control
the size of population yet still
maintain a desired degree of diversity. During chromosome decoding,
each chromosome in the population is converted into an operational dr iving path by filling gaps
between any two consecutive edges
in the chromosome. The decoded
path with the highest utility value is
returned as the final solution.
3) We conduct a series of experiments
to evaluate the effectiveness and efficiency of the 2TD Path-Planner
extensively based on one synthetic
and four real-world road networks.
On top of the synthetic road network, we mainly focus on examining
the generality and scalability issues.
Experimental results on all road networks show that the proposed algor ithm outperfor ms baselines
significantly in terms of the obtained
path utility score and the running
time. Finally, we also conduct a case
study in the City of New York
(NYC) to demonstrate the system
usability in practice.
The rest of this paper is organized as
follows. In Section II, we review the

related work and show how our work
differs from the prior research. In Section III, after introducing some basic
concepts, we present the mathematical
formulation of our 2TD-AOP. In Section IV, we briefly overview the proposed system and further elaborate its
details sequentially. We thoroughly evaluate the system performance in Section V.
Finally, we conclude the paper and chart
the future directions in Section VI.
II. Related Work

In this section, we briefly overview
the related work which can be grouped
into two categories, i.e., multi-preference and time-dependent route planning, respectively.
A. Multi-Preference Route Planning

Multi-preference route planning optimizes routes with more than one objective. For instance, considering both cost
and the utility on arcs, many path-planners aim to find the highest-utility path
within the budget. Generally speaking,
such route planning systems aim to
handle two sub-problems, i.e., modelling the arc utility based on relevant
data sources and finding the optimal
routes according to users' travel preference or purposes. In real scenarios, arc
utility embodies the beauty score, the
safety/risky score, the happiness score,
and etc. This category of work relatively
paid more attention to arc utility modelling. Fortunately, as various kinds of
data can be obtained, those different
forms of utility can be modelled based
on the relevant information. For the
beauty score, [13] modelled it based on
the geospatial distribution of geotagged images and [1] extracted relevant
information from both geo-tagged
images and check-ins to quantify it
more accurately. Besides, taking into
account the actual views on specific
route segments, [12] classified scenic
arcs based on their visual characteristics
using Google Street View images. For
the safety/risky score, [26] modelled it
by analyzing extremely negative sentiments inferred from Twitter data. Based
on civic datasets of criminal activity and
city-dwellers mobility traces, [18] devel-

oped a risk model to compute the relative probability of a crime on all roads.
Additionally, [11] quantified the happiness score based on a crowd-sourcing
platform. The platform shows two street
scenes and a user votes on which one
looks more beautiful, quiet, and happy.
Moreover, [27] described the health
score on the route by taking environmental and individual factors into
account. On the contrary, simple path
planning algorithms are often applied to
find the optimal path for this category
of work. To name a few, [11] suggested
utility-rich routes by simply re-ranking
a top-k list of shortest paths according
to their total utility scores. In summary,
the utility score is modelled as the constant in the statistical sense and kept
unchanged over time. However, in real
life, the utility on each arc evolves with
time. In our work, we simulate the utility property in a much finer granularity
and implement two forms of timedependent utility with distinct timechanging frequency for investigation.
B. Time-Dependent Route Planning

There has been quite a bunch of work
on time-dependent route planning, but
most of them focus on one-fold time
dependence of arcs, i.e., the travel time is
time-dependent. Existing route planning
algorithms can be broadly divided into
two groups: exact and heuristic algorithms. An exact algorithm is proposed
in [28] based on the idea of network
planning and dynamic programming.
However, all exact algorithms can only
work for small-scale road networks. To
support applications on the real and
large-scale road networks, many
researchers seek to find a near-optimal
solution. Some time-dependent routing
algorithms were proposed by extending
the previous static heuristic methods. To
name a few, [29] calculated the average
travel time on arcs. With the average
travel time, iterated local search (ILS)
[30] was used to solve the time-dependent problem as a regular static problem.
A repair procedure was further introduced to account the real travel time
on arcs. [31] improved ILS with adaptive perturbation size and probabilistic

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