IEEE Computational Intelligence Magazine - February 2021 - 69

observed that taking into account the
standard deviation of costs in the objective function led to lower variability,
thus producing more robust solutions.
Using expectation as objectives or
measures is easy to execute and methods
for handling DCARPs can be applied
directly. However, it is less realistic in
real-world applications as the probability
distributions of random variables are
usually unknown.
B. Performance Measures Over
Multiple Simulations

When the exact distr ibutions are
unknown or the expectation and variance cannot be computed directly, multiple simulations over different scenarios
often have to be carried out in order to
estimate expectations and variances.
1) Average Performance
In practice, expectations of variables are
sometimes unknown and it is not possible to sample all the scenarios of a
CARPSD or uCARP. Statistics collected during n ! N + independent simula-

tions of x can be used to estimate some
performance measures (e.g., [6], [12]).
a) Estimation of Cost
The empirical average of the total cost
E n [C (x)], as well as the empirical standard deviation v n [C (x)], have been
widely used for estimating the expected
cost E [C (x)] and standard deviation
v [C (x)], respectively. Examples include
[6], [10], [12], [17].
b) Estimation of Number of Trips
Similar to the above, the empirical average of the number of trips E n [T (x)], as
well as the empirical standard deviation
v n [T (x)], have been used for estimating
E [T (x)] and v [T (x)], respectively.
Examples also include [6], [10], [12], [17]

number of trips in the best solution
found, is used as a performance measure
by Fleury et al. [6]. Such evaluation is
optimistic but it gives a brief idea of
how low the cost could possibly be.
3) Worst-Case Performance
A pessimistic measure is the worst-case
performance, i.e., simulating a solution on
random realizations of a UCARP
instance and its worst performance (highest total cost or highest number of trips)
used as the performance metric.Then, the
solution with the best worst-case performance is recommended. This is the classic
Wald's maximin model [41] for decision
making. Such a performance measure is
also called a robustness measure.
C. Other Robustness Measures

c) Robustness Estimator
The variability can also be estimated by
v n [C (x)] E n [C (x)] [11].
2) Best-Case Performance
The best-case performance, defined as
the cost of the best solution and the

The performance measures presented
above are used most often in the literature.
This section summarizes some other metrics for measuring robustness of solutions
other than the worst-case performance
measures, variability [6], [12] and the
robustness estimator [11]. These measures

TABLE IV Performance measures of solutions for the CARP with uncertainties. The notations used in this table and detailed
description of each measure are explained in Section IV. The t in measures (2), (8), (11), (16) and (19) is a user-specified constant
for a linear combination of expectation/average and standard deviation.
SCENARIO-BASED
TRAGET

WITH DISTRIBUTION ASSUMPTIONS

AVERAGE

COST

(1) EXPECTED COST: E [C (x)]

(10) AVERAGE COST E n [C (x)] WITHOUT
ADDITIONAL CONDITION

(2) E [C (x)] + tv [C (x)] OR v [C (x)]
(3) VARIABILITY:

v [C (x)]
E [C (x)]

(4) E [C (x)] WITH UPPER BOUNDED
PROBABILITY OF AN EXTRA RETURN

BEST-CASE
(13)

WORST-CASE
(i)

min C (x)

(14) max C (i) (x)

min T (i) (x)

(22) max T (i) (x)

i ! {1, f, n}

i ! {1, f, n}

(11) E n [C (x)] + tv n [C (x)] OR v n [C (x)]
(12) ROBUSTNESS ESTIMATOR:

v n [C (x)]
E n [C (x)]

(5) E [C (x)] WITH UPPER BOUNDED
PROBABILITY OF #TRIPS
(6) E [C (x)] WITH UPPER BOUNDED
VARIANCE OF COST
(7) EXPECTED MAKESPAN: E [M (x)]
(8) E [M (x)] + tv [M (x)] OR v [M (x)]
(9) THRESHOLD-BASED ROBUSTNESS
INDICATOR
TRIP

(15) EXPECTED #TRIP: E [T (x)]

(18) AVERAGE #TRIPS: E n [T (x)]

(16) E [T (x)] + tv [T (x)] OR v [T (x)]

(19) E n [T (x)] + tv n [T (x)] OR v n [T (x)]

(17) PROBABILITY OF TRIP INTERRUPTION

(20) PERCENTAGE OF INTERRUPTED TRIPS

CONSTRAINTS

(21)

i ! {1, f, n}

i ! {1f, n}

(23) RELIABILITY-BASED ROBUSTNESS MEASURE
(24) REPAIR-BASED ROBUSTNESS MEASURE

OTHER MEASURES

(25) RELATIVE PERFORMANCE MEASURES (APPLICABLE TO MOST OF THE ABOVE MEASURES)
(26) MULTIOBJECTIVE MEASURES (APPLICABLE TO A SET OF DIFFERENT MEASURES)

FEBRUARY 2021 | IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE

69
IEEE Computational Intelligence Magazine - February 2021

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