IEEE Computational Intelligence Magazine - February 2021 - 74

B. Robust Optimization With Variable
Distribution Assumptions

This section presents the work on robust
optimization in CARP with uncertainties when known variable distributions
are assumed.
1) Deterministic Optimization,
Stochastic Evaluation-Solving
transformed DCARP
A number of existing work did not
design algorithms for solving CARP
with uncertainties directly, but addressed
UCARP as transformed DCARP and
solved it using DCARP solvers, then
evaluated the solutions on realizations
(samples) of the corresponding UCARP.
They focused more on the evaluation of
solutions for selecting optimal heuristics
for the UCARP. A two-phase framework,
deterministic optimization phase and
-stochastic evaluation phase (DOSE), has
been widely used in the robust optimization of UCARP. We illustrate this twophase framework, DOSE, in Figure 2.
During the optimization phase, algorithms for solving DCARP are applied
directly to the static version of the corresponding UCARP, where they solve the
UCARP instances by utilizing the
expectation of the random variables. In

some work, the evaluation phase is also
called the replication phase because each
solution is performed on a number of
replications of UCARP. Each replication
of a UCARP is a DCARP instance as
the random variables are replaced by
their deterministic realizations, usually via
Monte Carlo simulations. This technique
is also called " resampling " in noisy optimization aiming at reducing the probability of mis-ranking solutions [48], [49].
This framework assumes that the model
of the random variables, or at least, the
expectation of the random variables, perfectly reflects the true one in real life. In
other words, it assumes that the expectations of the random variables are known.
❏❏ Deterministic optimization process: During this stage, the given
UCARP with stochastic models for
demands of known expectations is
transformed to a DCARP instance
of which the demands are deterministic and equal to the expectations of
the stochastic demands. Then, the
resulting DCARP instance can be
solved by existing heuristics for the
DCARP.
❏❏ Stochastic evaluation process:
Then, the heuristics are evaluated
and selected based on some pre-

defined performance metrics, computed
using the simulation results of their
optimized, deterministic solutions on
a set of sampled instances of
UCARP. Some repairing techniques
may be applied during simulation if
the actual demand of a task to serve
next exceeds the vehicle's available
capacity. Section IV gives a comprehensive review of different measures
that have been used in the literature.
Core components involved in the
above framework are: (i) the stochastic
models for demands; (ii) the heuristics
for the DCARP, (iii) the performance
metrics for evaluating heuristics and
(iv) the repairing techniques. Complete lists of previously studied (i), (iii)
and (iv) have been introduced in Section III-C, Sections IV and V-A2),
respectively. Although all the heuristics
for the DCARP can be used in this
two-stage framework, we will not
cover all of them but only the ones
used by the publications with a focus
on UCARP. The cor responding
demand model and perfor mance
metric(s) will also be discussed.
The algor ithms designed for
DCARP that have been used in this
framework are summarized as follows.

Sample r Deterministic Realisations

UCARP I
Apply a Prior Techniques
DCARP I1

DCARP I2

···

DCARP Ir

Simulate x

···

Simulate x

Repair

Failure?

···

C (x, Ir) and T (x, Ir)

Replace Random Variables
DCARP IE
Yes

Optimise by Solver for DCARP

Failure?

Solution x

C(x, I1) and T (x, I1)

Repair

Failure?

Yes

No
C(x, I2) and T (x, I2)

Yes

Repair

Compute User-Specified Metrics for Evaluating x
Phase 1: Optimisation

Phase 2: Evaluation

FIGURE 2 Two-phase framework: deterministic optimization-stochastic evaluation (DOSE). DCARPE denotes the DCARP instance generated by
replacing the random variables of the given UCARP by their expectations. I 1, f, I r denote the r deterministic realizations (samples) of UCARP.
C (x, I i) and T (x, I i) denote the resulted cost and number of trips of simulating a solution x on a deterministic realization I i .

IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE | FEBRUARY 2021

IEEE Computational Intelligence Magazine - February 2021

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