IEEE Computational Intelligence Magazine - May 2021 - 90

time values for a given edge tt (t, e i)
according to the following equation, as
shown in Eq. 16.
tt	 (t, e i) = bt (e i) # (1 + e i (t)) = bt (e i)
Z
J
N
] 0 if mod `8 t B, 3 j = 0O
K
tc
]
K
O
]
# K1 + [ - a if mod `8 t B, 3 j = 1O
tc
K
O
]
KK
] a if mod `8 t B, 3 j = 2OO
tc
L
P
\
(16)
where bt (e i) is the basic travel time of ei;
e i (t) refers to the time-dependent increment at the given time t; 6 · @ and
mod (·, ·) are the round down and modulus operators respectively; tc refers to
the time-sensitivity of the travel time,
which is set to 5 minutes; a is also a
constant. a is set to the range (0,0.122)
for simulating the time-dependent
travel time under the range of minimum and maximum vehicle speeds, i.e.,
19 km/h and 25 km/h. Thus, each edge
has three different values in total. For
different edges, we choose a different
value of a randomly in the range to
simulate different traffic conditions,
while tc is the same and unique for all
edges at all times.
Compared to the travel time property, the simulation of time-dependent
utility values is more complicated since
it contains more parameters. The first
parameter is t , which refers to the utility density and determines the number
of total utility edges. We uniformly
select a number of utility edges according to t . The second parameter is
bu (e i), which is used to determine the
basic utility value for the utility edge ei.
Note that the utility value for non-utilTABLE I Statistics of road networks
used in the paper.

ROAD
NETWORK

AVERAGE
EDGE
LENGTH
# NODE # EDGE (M)

SYNTHETIC

600

2,542

800.9

SFC

5,101

7,378

78.9

NYC

6,735

10,560

113.9

CD

5,056

7,355

399.8

CQ

4,819

6,385

666.1

90

ity edge is set to 0. The third parameter
is u c (e i) , which refers to the utility
time-sensitivity of the utility edge e i.
Unlike the travel time-sensitivity (tc)
that is same and unique for all edges, we
set a number of values of uc for different
utility edges to make it more general
and closer to real life. The fourth
parameter is b , which is used to control
the range of utility changing. In summary, similar to the computing way of
time-dependent travel time values, for a
given utility edge (ei), its time-dependent values can be computed according
to the following equation, as shown in
Eq. 17.
tu (t, e i) = bu (e i) # (1 + d i (t)) = bu (e i)
Z
N
J
] 0 if mod c; t E, 3 m = 0O
K
	
u
c (e i )
]
O
K
]
# K1 + [ - b if mod c; t E, 3 m = 1O
O
K
u c (e i )
]
O
K
t
]
K
] b if mod c; u (e ) E, 3 m = 2O
c i
L
P
\
(17)

where d i (t) is the time-dependent
increment of utility at the given time t.
The real-world road networks are
crawled via the well-known OpenStreetMap platform, i.e., the city of San Francisco (SFC), the city of New York
(NYC), the city of Chengdu (CD) and
the city of Chongqing (CQ) respectively.
More details can be found in Table I. It
should be noted that CQ is a mountain
city where the distribution of nodes and
edges is extremely irregular. In total, road
networks are selected from two American
cities and two Chinese cities. The basic
travel time for each edge in SFC and
NYC is obtained via Google APIs [8]
while the basic travel time for each edge
in CD and CQ is obtained with the
same way to that in synthetic data. Other
travel time related parameters (i.e., a and
tc) for all four road networks are set the
same as the synthetic data.
For SFC road network, we implement
the time-dependent scenic score as the
utility on each edge, while for NYC, we
implement the time-dependent risky
score as the utility on each edge. To
approximate the basic utility scores for
both road networks, we rely on crowdsourced data including Flickr geo-tagged

IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE | MAY 2021

image data, Foursquare check-in data and
crime data provided by NYPD Complaint Data Current [13], [18], [39]. As a
result, t can also be fixed as well. As discussed, the major difference between
these two kinds of utility is the time--
sensitivity. The time-sensitivity of the scenic score is much larger than that of the
risky score. More precisely, the scenic
score of an edge can be stable and
unchanged within a few hours. In this
case, the scenic score is actually not timevarying at the trip time duration since the
total driving time is usually smaller than
an hour [22]. Thus, we set scenic score
time-sensitivity value to 3 hours. As a
comparison, the time-sensitivity of risky
score can be quite small on some road
segments during some time periods if
crimes occurred frequently during that
time. The frequency of crime can be different for different edges, thus we set uc to
a number of values to make it closer to
the reality. Parameter b is also set the
same to that of the synthetic road network. It should be noted that how to
quantify the time-dependent utility values
correctly with the crowdsourced data is
challenging and can be a separated
research issue [20].
The detailed settings regarding
road networks used in different experiments can be found in Table II in
Appendix B.
3) Evaluation Metrics
For each query, two common metrics
are adopted to measure the performance
of the system, that is, the path utility score
of the returned path which can be easily
calculated according to Definition 6 and
the running time of the computer needed
to respond the query.
4) Baseline Algorithms
We use two baseline algorithms to compare, detailed as follows.
❏❏ Memetic Algorithm (MA) [21].
MA consists of three main steps, i.e.,
chromosome generation, chromosome
decoding, and the local search. Chromosome generation produces a population of utility edge sequences from
the origin to destination, and the chromosome decoding coverts each utility
IEEE Computational Intelligence Magazine - May 2021

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