IEEE Computational Intelligence Magazine - February 2021 - 66

on uncertainties in the CARP, from
now on, the term " static " will be omitted when referring to static and deterministic or static and stochastic CARP.
B. Variants of CARP with Uncertainties

In the past two decades, different variations of CARP with uncertainties were
proposed and studied consider ing
the non-deterministic factors in realworld problems.
1) CARP with Stochastic
Demands (CARPSD)
Motivated by the urban waste collection
problem, Fleury et al. [6], [11] proposed
the stochastic CARP (abbreviated as
" SCARP " ) in which only the demands
are stochastic, i.e., d (·) in Eq. (7) is a
random variable rather than a constant,
and follows normal distributions. Christiansen et al. [7] and Laporte et al. [8]
used the abbreviation " CARPSD " for
the CARP with stochastic demands (same
as SCARP) but assumed Poisson distributed demands in their work.
2) Uncertain CARP (uCARP)
Besides stochastic demands, many other
stochastic variables can be present in
real-world applications, such as the stochastic costs of tasks, the absence of
edges and/or tasks [3], [4]. Factors that
can affect the cost of traversing a path
include, but are not limited to, the speed
of a vehicle, the load of a vehicle, the
traffic flow and the weather. Due to
heavy traffic or road maintenance, an
edge can be considered broken, thus it is
not present. The above can be roughly
summarized into the following 4 random factors: presence of tasks, demand
of tasks, presence of paths and deadheading costs. Mei et al. [9] proposed a more
general case, uncertain CARP (uCARP),
that considers all the above. In [9], Bernoulli and Gamma distributions were
assumed for the stochastic variables.
However, in real life, some of the
uncertainties, originating from nature
or humans, cannot be modelled easily
by stationary probabilities. Their distributions are unknown a priori. Taking
the urban waste collection problem as
an example, family parties or Christmas

66

often result in a higher food consumption and a significant increase in the
amount of waste, while zero waste collection demand occurs occasionally
during spring holidays.Variables in such
scenarios can hardly be modelled by
fixed probability distr ibutions. As
pointed out by Wang et al. [10], in reality, only a set of scenarios1 is likely to
be available. Afterwards, research has
been conducted on searching robust
solutions for a set of deterministic samples of uCARP without assuming a
priori known distributions for uncertainty [10], [17].
The exact values of random variables
are known only at the time of reaching a
task or edge (road or street); therefore,
solutions optimized a priori might be
infeasible at the time of execution. Techniques for avoiding constraint violation
(summarized in Section V-A1) and repair
operators for fixing solutions during execution (Section V-A2) are essential. For
instance, if the amount of waste to collect
exceeds the available capacity of a vehicle,
the vehicle will need to return to the
depot, empty its collection, then continue
to serve the remained tasks. How to efficiently adapt a solution to the actual scenario while minimizing the cost and risk
is an important topic for research.
3) CARP with Fuzzy
Demand (CARPFD)
Instead of using probabilistic models,
fuzzy numbers have been used to model
demands in CARP [18], [19].
4) CARP with Stochastic
Time (CARPST)
Different from the above work, Chen
et al. [20], [21] considered the stochasticity of time in the road network daily
maintenance problem. In [20], the problem is formulated as a CARP with stochastic service and travel times
(CARP-SSTT) following a normal distribution, while in [21], the problem is
formulated as an ARP with stochastic

1

 Different terms, such as " replication " , " sample " and
" scenario " , have been used in the literature to refer to
a deterministic realization of a random process.

IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE | FEBRUARY 2021

service time without assuming (ARPSST) any known variable distribution.
5) Abbreviations
To be consistent with the existing publications, hereinafter, the abbreviation
" DCARP " is used to refer to the deterministic CARP and " UCARP " is used to
refer to the CARP with uncertainties. The
abbreviation " uCARP " stands for the
uncertain CARP defined by [9] considering 4 random variables. Although
" SCARP " is the first abbreviation used for
the CARP with stochastic demands [6],
the abbreviation " CARPSD " [7] will be
used as it is more informative. It is notable
that in some literature, the phrase " dynamic
CARP " is used as an alternative to
UCARP, such as [22]. However, we argue
that the use of " dynamic CARP " is not
suitable here, as discussed previously in Section III-A2). " CARPFD " and " CARPST "
stand for CARP with fuzzy demands and
CARP with stochastic times, respectively.
C. Modelling Uncertainties

A number of work on CARP with
uncertainties assumed certain distributions for non-deterministic variables.
This section presents the assumptions
considered in the reviewed work.
1) Cancelled/Unexpected Tasks
The presence of tasks is often modelled
as a Bernoulli distribution [9]. Thus,
given a set of potential tasks, the ith
task is present with probability p i ! (0, 1).
The case that a task is not present can
be considered as one with 0 demand.
When executing a solution, if a task is
no longer present, the vehicle will skip
the task and travel to the next one via
the shortest path. The presence of tasks
will affect the set of tasks to be served,
the domain of solution variables, Eqs.
(6) and (2) in the model formulated in
Section III-A1).
2) Edge Failure
The case in which an edge is not present is called an edge failure, possibly due
to a broken path or heavy traffic. When
an edge failure occurs, the cost of this
edge is set to 3. If there is a task on this
edge, the vehicle will take it as a c- ancelled
IEEE Computational Intelligence Magazine - February 2021

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