IEEE Computational Intelligence Magazine - February 2021 - 79

cause of backhauls to the depot is route
failures. It was assumed in [6], [27] that
route failures usually occur toward the end
of routes. The closer the failure is to the
depot, the shorter the backhaul is, and
the smaller the extra cost is.To determine
the tasks closed to the depot and select the
next task to serve, the FF factor is de--
fined. For each unserved task t, FF(t) is
defined as the number of these shortest
paths that t is a member of. Tasks with
smaller FF values are preferred. No feature of the problem has been used and
for each newly sampled scenario, the
routing policy needs to be re-trained.
Very recently, Wang et al. [31], [32]
noticed that the routing policies evolved
by GPHH are hard to be interpreted. To
evolve less complex and more interpretable routing policies, two approaches
have been investigated: (i) a two-stage
GPHH [31], which takes the performance as an optimization objective during the first stage, then both the performance and the tree size are optimized
with a multi-objective GP proposed in
[31], was designed; (ii) three ensemble
methods based on GP, namely BaggingGP, BoostingGP and cooperative
coevolution GP (CCGP), were proposed and compared to the simple
GPHH [26], and the experimental study
on the tested UCARP instances showed
the potentials of CCGP on evolving
more interpretable routing policies.
Almost all the work reviewed in this
paper rely on the assumption that it is
not possible to assign another vehicle
when a route failure occurs. Thus, when
a vehicle fails to serve its assigned task t,
it should return to the depot, release its
capacity and then return to the next task
to serve; no other, even nearby, vehicle is
capable of serving the task t instead. This
assumption is not always true in reality.
To the best of our knowledge,
MacLachlan et al. [28] were the first to
split deliveries in UCARP and proposed
an enhanced GPHH with vehicle collaboration (GPHH-C). The vehicle collaboration was proved to be effective
compared to the GPHH without collaboration [25] on the ugdb, uval, uegl
benchmarks, and also to EDASLS [17]
on most of the tested instances.

2) Knowledge Transfer
More recently, Ardeh et al. [29] assumed
that the routing policies of similar scenarios share similar (sub-)trees, which
could be seen as knowledge transfers
among multiple routing policies.
3) Ensemble Methods
Wang et al. [33] proposed two novel
ensemble genetic prog ramming
approaches, namely diverse bagging
genetic programming (DivBaggingGP)
and diverse niching genetic programming (DivNichGP), to evolve policies.
The former evolves policies sequentially
while the latter evolves policies in a parallel manner. An ensemble of simpler
and more interpretable routing policies
were evolved in [33].
4) Solution-Policy Co-Evolver
The above work focused mostly on
either the evaluation of the robustness of
solutions or repairing techniques (sometimes called recourse policy) which lead
to a low extra cost due to additional trips
(backhauls to depots). Liu et al. [30] proposed a new proactive-reactive approach,
called solution-policy co-evolver. In [30],
a solution is represented as a baseline task
sequence and a recourse policy, which are
evolved simultaneously in a cooperative
coevolution manner by an estimation of
distribution algorithm (EDA) and genetic
programming (GP), respectively. This
approach was only tested on the singlevehicle case [30] but could be extended
to the multi-vehicle case.
E. Summary of Solution Approaches

Figures 1, 3 and 4 summarize the techniques for handling uncertainties, the
robust optimization approaches for
CARP with uncertainties, and the
applications of machine learning methods to routing policies.
In the early attempt to solve the
CARP with uncertainties, different
assumptions of variable distribution
have been made (Section V-A). Algorithms for solving DCARP are applied
directly to the static version or deterministic realizations of a UCARP (Section V-B1) aiming at minimizing the
expected cost, then the obtained solu-

tions are evaluated on unseen samples
using diverse performance metrics
(Tables IV and V).
Several algorithms are adapted for
solving CARP with uncertainties (Section V-B2). These approaches mostly differ in (i) the sampling methods of deterministic realizations when generating
intermediate solutions during the search
and (ii) using deterministic evaluation
(i.e., sample UCARP once and then
evaluate on the sampled DCARP) or
stochastic evaluation (i.e., sample
UCARP multiple times and then average the performance on the sampled
scenarios) during the search. Some other
work was interested in designing robust
optimization models (Section V-B3).
Scenario-based robust optimization
approaches were investigated without
assuming variable distributions (Section
V-C). As the exact values of parameters are
known only at the time of execution in
practice, the solutions obtained may
become infeasible. For example, the vehicle capacity may be exceeded due to
unexpectedly high demands of tasks. Consequently, some work focused on changing the problem formulation to reduce the
probability of route failure (e.g., [6], [12]),
and designing or learning effective and
efficient recourse strategies (also called
recourse policies or repairing operators),
such as in [30]. The routing or recourse
policies are often evaluated by the average
performance in unseen problem instances.
Techniques for handling uncertainties, including a prior techniques, posterior techniques and resampling, can be
integrated into different approaches for
solving variants of CARP with uncertainties (Figure 3).
VI Discussion and Challenges
A. Difficulties in Comparing
Approaches

Different approaches for handling
CARP with uncertainties are rarely
compared to each other in the literature,
but mostly compared to some state-ofthe-art approaches for solving DCARP
or to some techniques proposed by the
same authors, probably due to the following reasons.

FEBRUARY 2021 | IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE

79
IEEE Computational Intelligence Magazine - February 2021

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