IEEE Computational Intelligence Magazine - February 2021 - 73
approach in [6], while the regular constraint on capacity without reduction, as
in classic DCARP, is called the tight
approach. In [6], a pseudo capacity 90% Q
is used during optimization, while the
actual capacity Q is used when evaluating
the solutions. The slack approach is capable of avoiding some violation of capacity
constraint due to stochastic demands,
however it may increase the number of
trips, which implies an increase in the
solution cost. Moreover, the control
parameter k is difficult to set. A similar
approach was used by [36] to generate
DCARP instances.
b) Law Approach-Bi-Objective Function
Different from revising the vehicle
capacity as in the slack approach, the law
approach [12] varies the objective functions to handle uncertainties. Instead of
minimizing the cost of solutions, the law
approach considers the minimization of a
weighted sum of the cost and its standard deviation.
2) Posterior Techniques-
Repairing Operators
Several operators have been designed for
repairing infeasible solutions during
execution [9].
a) Skip-and-Jump
In case of a cancelled task or when its
actual demand is 0 at the time of serving,
as well as when a task is on an absent
edge, the vehicle skips the task and
jumps to the next one.
b) Alternative Shortest Path
If an edge without task is absent, namely
no longer being present on the map, this
absent edge is replaced by the shortest
path between its two vertices.
c) Recourse Strategy-Return
and Continue
In case of a violation of vehicle capacity
before serving a task t, the vehicle must
return to the depot via the shortest path,
refill goods or unload goods, go back to
the task t and serve it, then continue its
planned trip (e.g., [7], [11]). At least one
supplementary trip will be induced
depending on the number of times of
capacity violation of a planned trip
occurred, which implies an increase in
the total cost. Note that this repairing
technique is applied under the assumptions that (i) a task's actual demand is
known before it is served and (ii) assigning another vehicle is impossible or
inefficient. Techniques like this are called
recourse strategies [11]. For instance, in the
waste collection problem, a vehicle may
be fully filled in the middle of a road
(edge), thus cost has already been caused.
For a better understanding of recourse
strategies, we translate the recourse strategy used by [9] into A lgorithm 1,
which also facilitates its reproduction.
3) Resampling for Evaluation
Techniques for handling uncertainties
are important in optimization under
uncertainties, among which sampling is
the most discussed for reducing the
probability of mis-ranking two solutions
due to uncertain test scenarios [46],
[47]. In [10], the solutions for uCARP
were evaluated on an identical set of
scenarios for a fair comparison. Wang
et al. [17] resampled uCARP instances
for evaluating each solution and used its
maximal cost obtained on the sampled
instances (thus worst-case cost) for
ordering the solutions. Chen et al. [20],
[21] used Monte Carlo simulations to
evaluate the robustness of solutions.
These techniques for handling un--
certainties are often integrated into the
robust optimization approaches for
approximately solving CARPs with
uncertainties. Sections V-B and V-C will
present the approaches when assuming
known or unknown distributions of
variables, respectively.
Algorithm 1 The recourse strategy used in [9], translated into pseudo-code by us.
Require: Planed route of tasks r = (v 0, t 1, t 2, f, t l)
Require: Current location v
Require: Current available capacity Ql
1: Locate the next task t
2:
if Next task t exists then
3:
if Ql $ E [d (t)] then
4: Traverse to head(t) through the original path
5:
else
6: Return to the depot and empty, Ql = Q
7: Traverse to head(t) through the shortest path
8:
end if
9: while tail(t) not reached do
2 t is not completed
10: Loop 1
11: Serve t progressively and update Ql
12: if Arrive at tail(t) then 2 t is completed
13: break while
14: end if
15: if Ql = 0 then
2 Capacity is exhausted on the way of service
16: Return to the depot and empty, Ql = Q
2 Neglect the remaining demand
17: Traverse to head(t) through the shortest path
from current location
18: break Loop 1
19: end if
20: End Loop
21: end while
22: else
23: Return to the depot
24: end if
FEBRUARY 2021 | IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE
73
IEEE Computational Intelligence Magazine - February 2021
Table of Contents for the Digital Edition of IEEE Computational Intelligence Magazine - February 2021
IEEE Computational Intelligence Magazine - February 2021 - Cover1
IEEE Computational Intelligence Magazine - February 2021 - Cover2
IEEE Computational Intelligence Magazine - February 2021 - 1
IEEE Computational Intelligence Magazine - February 2021 - 2
IEEE Computational Intelligence Magazine - February 2021 - 3
IEEE Computational Intelligence Magazine - February 2021 - 4
IEEE Computational Intelligence Magazine - February 2021 - 5
IEEE Computational Intelligence Magazine - February 2021 - 6
IEEE Computational Intelligence Magazine - February 2021 - 7
IEEE Computational Intelligence Magazine - February 2021 - 8
IEEE Computational Intelligence Magazine - February 2021 - 9
IEEE Computational Intelligence Magazine - February 2021 - 10
IEEE Computational Intelligence Magazine - February 2021 - 11
IEEE Computational Intelligence Magazine - February 2021 - 12
IEEE Computational Intelligence Magazine - February 2021 - 13
IEEE Computational Intelligence Magazine - February 2021 - 14
IEEE Computational Intelligence Magazine - February 2021 - 15
IEEE Computational Intelligence Magazine - February 2021 - 16
IEEE Computational Intelligence Magazine - February 2021 - 17
IEEE Computational Intelligence Magazine - February 2021 - 18
IEEE Computational Intelligence Magazine - February 2021 - 19
IEEE Computational Intelligence Magazine - February 2021 - 20
IEEE Computational Intelligence Magazine - February 2021 - 21
IEEE Computational Intelligence Magazine - February 2021 - 22
IEEE Computational Intelligence Magazine - February 2021 - 23
IEEE Computational Intelligence Magazine - February 2021 - 24
IEEE Computational Intelligence Magazine - February 2021 - 25
IEEE Computational Intelligence Magazine - February 2021 - 26
IEEE Computational Intelligence Magazine - February 2021 - 27
IEEE Computational Intelligence Magazine - February 2021 - 28
IEEE Computational Intelligence Magazine - February 2021 - 29
IEEE Computational Intelligence Magazine - February 2021 - 30
IEEE Computational Intelligence Magazine - February 2021 - 31
IEEE Computational Intelligence Magazine - February 2021 - 32
IEEE Computational Intelligence Magazine - February 2021 - 33
IEEE Computational Intelligence Magazine - February 2021 - 34
IEEE Computational Intelligence Magazine - February 2021 - 35
IEEE Computational Intelligence Magazine - February 2021 - 36
IEEE Computational Intelligence Magazine - February 2021 - 37
IEEE Computational Intelligence Magazine - February 2021 - 38
IEEE Computational Intelligence Magazine - February 2021 - 39
IEEE Computational Intelligence Magazine - February 2021 - 40
IEEE Computational Intelligence Magazine - February 2021 - 41
IEEE Computational Intelligence Magazine - February 2021 - 42
IEEE Computational Intelligence Magazine - February 2021 - 43
IEEE Computational Intelligence Magazine - February 2021 - 44
IEEE Computational Intelligence Magazine - February 2021 - 45
IEEE Computational Intelligence Magazine - February 2021 - 46
IEEE Computational Intelligence Magazine - February 2021 - 47
IEEE Computational Intelligence Magazine - February 2021 - 48
IEEE Computational Intelligence Magazine - February 2021 - 49
IEEE Computational Intelligence Magazine - February 2021 - 50
IEEE Computational Intelligence Magazine - February 2021 - 51
IEEE Computational Intelligence Magazine - February 2021 - 52
IEEE Computational Intelligence Magazine - February 2021 - 53
IEEE Computational Intelligence Magazine - February 2021 - 54
IEEE Computational Intelligence Magazine - February 2021 - 55
IEEE Computational Intelligence Magazine - February 2021 - 56
IEEE Computational Intelligence Magazine - February 2021 - 57
IEEE Computational Intelligence Magazine - February 2021 - 58
IEEE Computational Intelligence Magazine - February 2021 - 59
IEEE Computational Intelligence Magazine - February 2021 - 60
IEEE Computational Intelligence Magazine - February 2021 - 61
IEEE Computational Intelligence Magazine - February 2021 - 62
IEEE Computational Intelligence Magazine - February 2021 - 63
IEEE Computational Intelligence Magazine - February 2021 - 64
IEEE Computational Intelligence Magazine - February 2021 - 65
IEEE Computational Intelligence Magazine - February 2021 - 66
IEEE Computational Intelligence Magazine - February 2021 - 67
IEEE Computational Intelligence Magazine - February 2021 - 68
IEEE Computational Intelligence Magazine - February 2021 - 69
IEEE Computational Intelligence Magazine - February 2021 - 70
IEEE Computational Intelligence Magazine - February 2021 - 71
IEEE Computational Intelligence Magazine - February 2021 - 72
IEEE Computational Intelligence Magazine - February 2021 - 73
IEEE Computational Intelligence Magazine - February 2021 - 74
IEEE Computational Intelligence Magazine - February 2021 - 75
IEEE Computational Intelligence Magazine - February 2021 - 76
IEEE Computational Intelligence Magazine - February 2021 - 77
IEEE Computational Intelligence Magazine - February 2021 - 78
IEEE Computational Intelligence Magazine - February 2021 - 79
IEEE Computational Intelligence Magazine - February 2021 - 80
IEEE Computational Intelligence Magazine - February 2021 - 81
IEEE Computational Intelligence Magazine - February 2021 - 82
IEEE Computational Intelligence Magazine - February 2021 - 83
IEEE Computational Intelligence Magazine - February 2021 - 84
IEEE Computational Intelligence Magazine - February 2021 - 85
IEEE Computational Intelligence Magazine - February 2021 - 86
IEEE Computational Intelligence Magazine - February 2021 - 87
IEEE Computational Intelligence Magazine - February 2021 - 88
IEEE Computational Intelligence Magazine - February 2021 - 89
IEEE Computational Intelligence Magazine - February 2021 - 90
IEEE Computational Intelligence Magazine - February 2021 - 91
IEEE Computational Intelligence Magazine - February 2021 - 92
IEEE Computational Intelligence Magazine - February 2021 - 93
IEEE Computational Intelligence Magazine - February 2021 - 94
IEEE Computational Intelligence Magazine - February 2021 - 95
IEEE Computational Intelligence Magazine - February 2021 - 96
IEEE Computational Intelligence Magazine - February 2021 - 97
IEEE Computational Intelligence Magazine - February 2021 - 98
IEEE Computational Intelligence Magazine - February 2021 - 99
IEEE Computational Intelligence Magazine - February 2021 - 100
IEEE Computational Intelligence Magazine - February 2021 - 101
IEEE Computational Intelligence Magazine - February 2021 - 102
IEEE Computational Intelligence Magazine - February 2021 - 103
IEEE Computational Intelligence Magazine - February 2021 - 104
IEEE Computational Intelligence Magazine - February 2021 - 105
IEEE Computational Intelligence Magazine - February 2021 - 106
IEEE Computational Intelligence Magazine - February 2021 - 107
IEEE Computational Intelligence Magazine - February 2021 - 108
IEEE Computational Intelligence Magazine - February 2021 - Cover3
IEEE Computational Intelligence Magazine - February 2021 - Cover4
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202311
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202308
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202305
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202302
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202211
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202208
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202205
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202202
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202111
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202108
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202105
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202102
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202011
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202008
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202005
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202002
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201911
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201908
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201905
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201902
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201811
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201808
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201805
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201802
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter17
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall17
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer17
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring17
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter16
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall16
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer16
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring16
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter15
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall15
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer15
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring15
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter14
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall14
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer14
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring14
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter13
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall13
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer13
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring13
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter12
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall12
https://www.nxtbookmedia.com