IEEE Computational Intelligence Magazine - February 2021 - 72

H. Discussion

The performance measures of solutions
for CARP with uncertainties can be
categorized into different groups, considering the objectives, constraints, scenarios and the dependence on variable
distribution assumptions, as summarized
in Table IV. The measures used in each
publication reviewed in this survey are
given in Table V.
Measures for evaluating solutions are
usually defined or selected by human
decision makers. A solution to UCARP
with low risk of extremely high cost can
be too conservative and leads to low
reward or high cost. Sometimes, solutions with high expected or average performance are preferred, while solutions
with low risk are favourable in the cases
that failure leads to high cost. Balancing
the trade-off between risk and cost is not
trivial. Given a set of solutions (decisions), the human decision makers need
to determine the optimal solutions using
pre-defined decision-making criteria
based on the practical consideration.
In Table IV, measures (1)-(9) and
(15)-(17) are not very practical as they
are calculated based on known variable
distributions, which are usually not
accessible in real-world applications.
Instead, measures (10)-(12) and (18)(20) over a set of given scenarios can be
calculated and then used. (14) and (22)
indicate how bad a situation the evaluated solution could lead to, while (13)
and (21) indicate how good the situation could be. They could be regarded as
pseudo lower or upper bounds. It is possible in a solution that a large number of
vehicles or trips are involved with a low
travel cost, which will lead to a high cost

of vehicle usage. In such cases, the measures related to the number of trips,
(15)-(22), are crucial. Measures (23) and
(24) help to handle stochastic constraints. As the actual lower bound of
cost is unknown in the CARP with
uncertainties, the relative performance
measure (25) assists the understanding of
solution quality. The multi-objective
measure (26) generally refers to any
measure which considers more than one
measure presented above.
V. Solution Approaches

After reviewing uncertainty models and
performance measures, this section categorizes different solution approaches to
robust optimization for the CARP with
uncertainties. CARPs can be transformed into VRPs. However, the number of vertices of the resulting VRP
triples the number of tasks of the original CARP [42], which implies an
increase in the computation time.
Therefore, the methods for solving (stochastic) VRPs [43]-[45] are often not
suitable to be applied to solving (stochastic) CARPs. Section V-A presents
the uncertainty handling techniques
designed specially for avoiding the trip
interruptions (Section V-A1) and repairing failed solutions (Section V-A2). Published work around robust optimization
in CARP with uncertainties will be
briefly divided into two categories: evaluating the robustness of solutions optimized for the deterministic CARP
transformed from the UCARP, and
approaches for directly searching for
robust solutions for UCARP. As
approaches of these two categories usually overlap, we propose a new taxono-

my as shown in Figure 3 (Sections V-B
and V-C) to facilitate our understanding
of different approaches. Finally, recent
advances in learning routing policies are
presented in Section V-D.
A. Handling Uncertainties

Uncertainties in CARP usually lead to
re-planning of routes. There are four
major sources of uncertainties: a cancelled task, an absent edge, a task on an
absent edge and a violation of vehicle
capacity. The first one is easy to understand. The second and third ones may be
due to a temporal maintenance or an
accident on a road (with a task), which
is difficult to forecast at the time of
planning. The last one is due to the perturbation of demands. A vehicle may
exhaust its capacity before completing a
trip, then a trip interruption, sometimes
called route failure, occurs. A prior and
posterior techniques (Figure 1) have
been proposed to reduce the probability
of route failure or increase the ability to
react optimally in such situations.
1) A Prior Techniques
To reduce the probability of route failure due to a violation of vehicle capacity, two a prior techniques by editing the
problem constraint [6] and objective
function [12] have been proposed,
respectively.
a) Slack Approach-Conservative
Constraint
To avoid solutions in which the total load
is close to the vehicle capacity Q, Fleury
et al. [6] reduced the vehicle capacity by
k% before the deterministic optimization
process. This technique is named as a slack

V-A Handling
Uncertainties
V-A1 A Prior
Techniques
V-A1a Slack
Approach

V-A1b
Law Approach

V-A2 Posterior
Techniques-Repair Operators
V-A2a
Skip-and-Jump

FIGURE 1 Techniques for handling uncertainties.

IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE | FEBRUARY 2021

V-A2b Alternative
Shortest Path

V-A3 Resampling
for Evaluation
V-A2c
Recourse Strategy

IEEE Computational Intelligence Magazine - February 2021

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