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
