IEEE Computational Intelligence Magazine - May 2021 - 91

edge sequence to a real operational
driving path on the road network.
During the chromosome generation, at
each iteration, a new utility edge is
inserted and the origin is updated by
the tail node of the added utility edge.
The utility edge with a smaller geographical distance to the origin will be
selected with a higher probability.Thus,
the population of chromosomes grows dramatically if there are many utility edges.
The local search aims to improve the
path utility score locally for each chromosome via crossover and mutation

is the very beginning. Only user queries with such travel time less than the
time budget need further processing.
Secondly, a utility edge " nearby " with
the highest ratio of its utility value to
travel time (i.e., best) is selected and
inserted, resulting in two gaps, i.e., from
the origin to the utility edge and from
the utility edge to the destination. At
each iteration, only one best utility
edge will be inserted and one more
gap will be generated simultaneously.
New best utility edge and new gaps
are recursively inserted and generated

operators. MA returns the chromosome with the highest path utility
score among all population after
decoding. Readers can refer to [21] for
more algorithm details.
❏❏ Scenic Route Now (SRN) [22].
SRN returns the path in a divide-andconquer manner by recursive insertions,
of which the core parts are the timedependent A) algorithm [40] and
the utility edge inserting. To be more
specific, finding the time-dependent
path and the corresponding total travel time from the origin to destination

Appendix B
Notations and Road Network Settings
Table I summarizes the notations appeared in the paper and their meanings, while Table II overviews the road
networks used and the detailed settings in different experiments.

TABLE I Notations and their meanings.

TABLE II Road network settings.

NOTATION

MEANING

EXPERIMENT

ROAD NETWORK USED AND SETTINGS

G

a road network

VARYING t

Synthetic

N

a set of nodes

E

a set of directed edges

ni

a node in N

eij

a directed edge from node ni to nj in E

p

a path over G

no, nd

the origin and the destination of a path

t

the departure time

b

the time budget of a trip

dti

the departure time from ni

tu

the time-dependent utility

tt

the time-dependent travel time

Tmin, Tavg

the minimum and average time cost

dist

the driving distance that corresponds to the
shortest path

vmax, vavg

the minimum and average vehicle speed

Ct

the critical departure time

Lt

the lower bound of the arrival time

Ut

the upper bound of the arrival time

bt

the basic travel time

tc

the time-sensitivity of the travel time

a

the changing-range of the travel time

bt = dist/22 , t c = 5,
a ! (0, 0.122), bu ! (0, 1) ,

u c ! {5, 10, 15, 20, 30} ,
b ! (0, 1), t = 10%
VARYING uc

Synthetic

bt = dist/22 , t c = 5,
a ! (0, 0.122), bu ! (0, 1) ,

u c ! {5, 10, 15, 20, 25, 30, 45} ,
b ! (0, 1), t = 10%
VARYING t

Synthetic

bt = dist/22 , t c = 5,
a ! (0, 0.122), bu ! (0, 1) ,
u c ! {5, 10, 15, 20, 30}, b ! (0, 1) ,
t ! {5%, 30%, 55%, 80%, 100%}

VARYING dist

SFC

bt is obtained via Google
APIs,
t c = 5, a ! (0, 0.122) ,
bu is modelled as the
scenic score.
uc = 180, b ! (0, 1) ,
t = 18.9% (based on the
crowdsourced data)

VARYING b

NYC

bt is obtained via Google
APIs.
t c = 5, a ! (0, 0.122) ,
bu is modelled as the risky
score.
u c ! {5, 10, 15, 20, 30}, b ! (0, 1) ,
t = 54.9% (based on the crime
data)

VARYING G

SFC
NYC
CD
CQ

u c ! {5, 10, 15, 20, 30} ,
b ! (0, 1), t = 10%

bt = dist/22 , t c = 5,
a ! (0, 0.122), bu ! (0, 1) ,

bu

the basic utility

uc

the time-sensitivity of the utility

b

the changing-range of the utility

UTILITY EDGE

SFC

the same as VARYING dist

the utility edge density

SELECTION

NYC

the same as VARYING b

t

MAY 2021 | IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE

91
IEEE Computational Intelligence Magazine - May 2021

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