IEEE Computational Intelligence Magazine - May 2021 - 86

2) Encoding via Iterative
score within the time budget, we
Utility Edge Inserting
propose four heuristic rules to select
As discussed, we propose to encode
utility edges at each iteration, detailed
each chromosome by a sequence of
as follows.
utility edges that satisfy any one of the
❏❏ Rule 1: Number priority. Intuitiveabove-mentioned four heuristic rules.
ly, the path utility is higher if more
As a result, the encoded chromosome is
utility edges can be included in the
a combination of utility edges that are
planned path. Motivated by this,
selected based on mixed heuristic rules.
we select the spatially nearest utility
In other words, the utility edges in a chromoedge to the starting node at one
some may be selected according to different
iteration. As a result, more time is
heuristic rules. Compared to previous
expected to be left for accommoevolutionary algorithms that commonly
dating more utility edges in future
adopt a universal heuristic in generating a
iterations.
chromosome [21], [38], our proposed
❏❏ Rule 2: Value priority. Similarly, the
chromosome encoding method could
path utility is higher if the utility
yield more diverse chromosomes while
edge with higher value can be
still maintaining a suitable size of popuincluded in the planned path. Thus,
lation. In more detail, the population of
we select the reachable utility edge
chromosomes is generated by an iterawith the highest utility value at one
tive procedure which mainly includes
iteration. Such selection is not easy
in practice since the utility value
is time-dependent. To simplify
the issue, we rely on the average
Algorithm 1 Encoding via iterative utility edge inserting.
utility value across all times [20],
instead of the detailed time- Input: n o, t 0, timeTable
dependent utility values.
Output: Chr
❏❏ Rule 3: Time-sensitivity and
1:
function encoding(n o, t 0, timeTable)
changing range priority. It is 2: Chr ! 4
expected that the path utility can 3: E ! 4
be potentially higher if the utili- 4: for r ! {rule1, rule2, rule3, rule4} do
ty edge with a higher changing 5: E !selectUE (n o, t 0, timeTable, r)
frequency and a wider changing 6: if E is not empty then
range can be included in the 7: for e ! E do
planned path. To account them 8: t 0 ! t 0 + Tavg (n 0, e);
comprehensively, we use the 9: Update n o
ratio of the change range to the 10: Br ! encoding (n o, t 0, timeTable)
time-sensitivity, then select the 11: if Br is not empty then
reachable utility edge with the 12: for br ! Br do
highest ratio value.
13: Chr ! Chr , (e + br)
❏❏ Rule 4: Random priority. We
14: else
randomly select a reachable utili- 15: Chr ! Chr , e
ty edge, to avoid the case where 16: return Chr
the previous three rules may be 17: function selectUE (n o, t 0, timeTable, r)
inclined to select utility edges 18: candidateE ! 4
located at a small area in the 19: t (e) ! 0
road network.
20: e ! getE(timeTable, r)
In a nutshell, based on the first 21: candidateE ! candidateE , e
three heuristic rules, we intend to 22: t (e) ! t 0 + Tavg (n 0, e)
exploit the potentials of " high-quality " 23: if t (e) $ Ct (e) and t (e) # Ut (e) then
utility edges in certain aspects to obtain 24: timeTable ! timeTable \ e
the optimal path. On the contrary, 25: if timeTable is not empty then
based on the last heuristic rule, we aim 26: e ! getE(timeTable, r)
to explore more possibilities and avoid 27: candidateE ! candidateE , e
the local optimum.
28: return candidateE

IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE | MAY 2021

the following two steps. The two steps
are performed until no reachable edges
can be selected from the edge timetable
for each chromosome.
Step 1: Utility edge selection. The
utility edge selection is conducted on
top of the chromosome. Specifically,
the last utility edge in the chromosome
is firstly set as the parent edge. Then,
the child edges E are selected from
the timetable according to the four
heuristic rules under the reachability
constraint.
Step 2: Chromosome growing. If E
is empty, the chromosome will stop
growing. Meanwhile, the iteration will
be terminated. If E is not empty, the
chromosome will continue to grow in
both size and length by inserting and
appending each utility edge in E into the
input chromosome. Thus, with respect
to the size, one chromosome would
grow into | E | new chromosomes
in total. With respect to the length,
all of the newly generated chromosomes would contain one more utility edge in the sequence.
We argue that the encoding efficiency of the iterative edge inserting
can be guaranteed. On one hand,
the pool size for the selection is relatively limited and small since the
number of utility edges is limited
and small. On the other hand, the
chromosome population size should
not be big since during one-time
chromosome growing, four new
chromosomes at most are generated.
More importantly, the number of
iterations is also upper-bounded by
the given time budget. We will give
more detailed quantitative analysis
in Appendix A.
We also provide the pseudocode of encoding via iterative utility
edge inserting, as shown in Algorithm 1. The input are n o , t 0 and
the timeTable, while the output is
the population of chromosomes
Chr. Abstractly, our proposed algor ithm encodes chromosomes
recursively. It should be noted that
n o refers to the tail node of the
parent chromosome edge, which is
updated dur ing the recursion.

IEEE Computational Intelligence Magazine - May 2021

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