IEEE Computational Intelligence Magazine - May 2021 - 83

cost should be within the time budget.
The time-dependent utility score and
travel time from n i to n j (i.e., edge e ij )
at departure time t are denoted as tu i, j (t)
and tt i, j (t) respectively.
Mathematically, the 2TD-AOP can
be formulated as a non-linear mixed
integer programming model:

max U (p) =

	

k

k

/ / tu ij (dt i) # e ij (3)

j=0 i=0

subject to:
	

e ij ! {0, 1}(4)

	

/ e 0j = / e ik = 1(5)

	
	

k

k-1

j=1

i=0

k

k-1

i=1

j=0

/ e i0 = / e ki = 0 (6)
k

k

i=0

i=0

/ e ij = / e ji # 1, j = 1, ..., k - 1(7)

	

dt 0 = t 0 (8)

	

dt k # t 0 + b (9)
k

	 dt j = / (dt i + tt ij (dt i)) # e ij, j = 1, ..., k
i=0
(10)
where e ij and dt i ( i, j = 0, g, k ) are
decision variables respectively. e ij is the
binary variable, as shown in Eq. 4.
e ij = 1 if the edge from n i to n j is
included in the planned path, and 0 otherwise. dt i refers to the departure time
from n i in the planned path.

R3

Edge Reachability
Computing

A. System Overview

In this paper, we develop the 2TD
Path-Planner (hereafter we simply use
2TD for brevity) to find the near-optimal path for each user query, which
includes three components, i.e., edge
reachability computing, chromosome encoding, and chromosome decoding, as shown in
Fig. 1. The inputs of edge reachability
computing are the user query and the
road network. Based on the information, the reachable region is first determined on top of the road network. For
each utility edge inside the region, by
the proposed timezone identification
method, the trip time duration is divided into three non-overlapped timezones, i.e., reachable timezone, critical
timezone and unreachable timezone.
Then, a timetable is constructed to
manage all reachable utility edges. The
chromosome (i.e., sequence of utility
edges) encoding is accomplished via an
iterative utility edge selection and
chromosome growing. Specifically, at
each iteration, the utility edges are
selected from the timetable based on
the four heuristic rules respectively and
inserted (appended) into the previous
chromosomes. Chromosome decoding
is to convert all chromosomes into the
operational driving paths by filling the
gap between two consecutive utility
edges in each chromosome. Once all
chromosomes are decoded into the
operational driving paths, it is easy to
get their corresponding true travel time

Selection Rules
R1 R2

Timetable

Road Network

IV. The 2TD Path-Planner System

The objective function (shown in
Eq. 3) maximizes the time-dependent
path utility. Equations 5~10 are the
constraints. The first constraint (shown
in Eq. 5) ensures that the planned path
must begin and end at the given places.
The second constraint (shown in Eq. 6)
indicates that there is no edge leaving
destination node or entering the original node in the planned path. The third
constraint (shown in Eq. 7) guarantees
that all nodes included in the planned
path must be directly connected by edges in
the road network and no node can be
visited more than once. The fourth and
fifth constraints (shown in Eq. 8 and
Eq. 9) impose the time constraints, i.e.,
they simply imply that the planned path
must departure at t 0 from the given origin and arrive at the destination no later
than t 0 + b . Equation 10 calculates the
departure time for each intermediate
node (n j ) included in the planned path.
In more detail, suppose e ij is included
in the planned path (i.e., e ij = 1, n i is
the predecessor of n j ); when calculating
the departure time of n j (i.e., dt j ), it
only needs to count a single term
dt i + tt ij (dt i) . Note that if e ij is not
included in the planned path, we can
obtain dt j = 0 according to Eq. 10,
without violating the optimality of the
model. Furthermore, the constraint
shown in Eq. 10 is the product of two
decision variables, indicating that it is
non-linear. Such a non-linear constraint
also results in the incapability of the
commercially available solvers (e.g., IBM
CPLEX).

Utility Edge

R4

Request

Chromosome Encoding

Chromosome Decoding

Timetable Construction

Utility Edge Selection

Gap-Filling

Timezone Identification

Chromosome Growing

Path Ranking

Optimal Path

User Query

FIGURE 1 Overview of the 2TD Path-Planner system.

MAY 2021 | IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE

83
IEEE Computational Intelligence Magazine - May 2021

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