IEEE Computational Intelligence Magazine - February 2021 - 80

1) Lack of Common Benchmarks
The proposed approaches were mostly
designed and tested on different problem
instances: different uncertainties, different
models for uncertainties, a priori known
or unknown models. Those problem
instances were designed by adapting differently from well-known DCARP
benchmarks or self-designed instances. As
shown in Tables II, III and V, diverse
variants of CARP with uncertainties
have been studied, while for each variant,
different assumptions on variable distributions have been made and different
distributions have been used for sampling
the variables. Only a few work used the
benchmarks uval, uegl, ugdb2. Most work
designed their own instances for testing.
2) Usage of Different Assumptions
a) A priori known or unknown models
As shown in Figure 3, most of the
approaches assume certain a priori
knowledge of variable distributions
while some of them do not and are scenario-based (e.g., [10], [17]).
b) Assumptions on Vehicles
Besides the differences in assumptions on
uncertainties, different assumptions have
also been made on vehicles, which implies
different designs of recourse strategies, as
detailed in Section V-A2c. For instance,
some work assumed that a vehicle can
have at most one extra trip, while some of
them do not. Only [28] considered collaboration between vehicles. In all the other
work, it is assumed that when a route failure occurs, no other vehicle is able to help,
and then a recourse is mandatory.
3) Usage of Different
Performance Measures
Table V shows a large number of different performance measures that have
been designed with particular foci and
used in the optimization and evaluation
processes. Although most of the work
reported the average cost over a number

T
he Java benchmark generator for sampling UCARP
instances, based on static instances, using the same variable assumptions as in [9], can be found in the GitHub
project: https://github.com/meiyi1986/gpucarp.

of simulations, it is impossible to compare different approaches due to the reasons listed above. Moreover, even if a
common benchmark, for example uval,
is used, using different random seeds for
sampling scenarios will introduce noise
when comparing approaches. For a fair
comparison, the solutions recommended
by different approaches should be evaluated on an identical set of scenarios.
As a conclusion, a common benchmark for studying CARP with uncertainties is needed.
B. Scalability

Most current work focused on small-scale
or medium-scale problem instances. The
instances in the UCARP benchmark sets,
ugdb, uegl and uval [9], are small compared
to the problems in reality, not to mention
other self-designed instances of smaller
size (cf. Table III). For example, the uval
instances contain no more than 50 vertices and 97 edges. Meanwhile, in the studies
of DCARP, several sets of static CARP
instances created based on real-world transport networks (e.g., Flanders district of
Belgium [56], [57], Beijing and Hefei of
China with up to 3584 tasks [58], [59])
have been used. Moreover, only [18], [34],
[35], [53] focused on multi-objective
DCARP and considered instances of small
size only in their case studies. Adapting
recent approaches for handling multiobjective large-scale DCARP, such as MA
based on route distance grouping [56], to
multi-objective large-scale UCARP is
worth investigating.
C. Computation Time

As discussed previously in Section
IV-G and shown in Table V, most of
the reviewed work did not report the
computation time. The stopping criteria were normally designed as a maximum number of iterations or when a
predefined solution for a transformed
DCARP was found. However, the
execution time is crucial in real-world
applications and it is not realistic to
obtain a transformed DCARP due to
complex uncertainties. In reality, we
often define a maximum execution
time as the budget and report the best
solution found within this budget.

IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE | FEBRUARY 2021

VII. Conclusion and
Future Directions

Our review in this paper has shown that
there has been a surprising broad range
of issues that have been addressed by
published papers on the CARP with
uncertainties. There are many places
where uncertainties can occur in the
CARP. Various techniques and algorithms have been adapted or developed
specifically for handling such uncertainties when finding a near optimal solution
to the CARP. However, in spite of the
breadth in research, the depth is largely
lacking. There are still many open
research questions that remain to be
answered. This section first draws some
conclusions and then points out possible
future research directions.
A. Conclusion

During the past decades, CARP and its
variations have been studied widely due
to its large number of real-world applications. However, most of the work
assumed deterministic problem instances, which is far from the reality. Till
2002, Fleury et al. [6] started to investigate the robustness of solutions to the
CARP with stochastic demands. To the
best of our knowledge, Mei et al. [9] was
the first to propose uncertain CARPs
with different random variables, including random demands, costs, presence of
edges and tasks. Since then, more and
more research studies have been conducted on the robust optimization of
CARPs with uncertainties. This paper
focuses on the robust optimization of
the CARP with uncertainties and
reviews the related work by discussing
the modelling of uncertainties, robustness evaluation of solutions, uncertainty
handling techniques and robust optimization approaches, as well as the learning
of routing policies.
The core components for solving
UCARP are divided into three main
steps: data prediction, problem solving
and decision making. Published work
around the CARP with uncertainties has
very different foci: problem modelling,
solvers, metrics for evaluating solutions,
creation of instances, generation of testing
scenarios, etc. These research topics rely

https://www.github.com/meiyi1986/gpucarp

IEEE Computational Intelligence Magazine - February 2021

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