IEEE Computational Intelligence Magazine - February 2021 - 65

the CARP. Then, Section III-B briefly
reviews CARPs with uncertainties. The
modelling of uncertainties is described
in Section III-C. Section III-D presents
the benchmarks of problem instances
used in the reviewed literature.

t k, i refers to the ith task on the kth route.
We define the general formulation used in
[17] as follows, given G = (V, E), T, Q,
cost c (t k, i) and demand d (t k, i) of t k, i,
min C (x) =

1) General Formulation of CARP
Diverse extensions of CARP to the
above have been proposed depending
on the corresponding applications in the
real-world, such as the CARP with stochastic time and periodic CARP [2], the
CARP with multiple depot [15] and the
CARP with multiple vehicle capacities
[16]. Their different formulations are
outside the scope of this review as we
focus on the CARP with uncertainties.
A solution of CARP can be represented by a set of routes x = {r1, f, rm}
served by m vehicles. Each route
rk = (t k, 1, f, t k, lk) ^k ! {1, f, m} h is a
sequence of tasks served, where lk is the
number of tasks served on this route and

lk

c (t )
:

k, i
k = 1 i = 1 serving cost

+ dist (tail (t k, i - 1), head (t k, i))
1444444244444
43 m

A. Capacitated Arc Routing Problem

The basic form of CARP [1], [5] can be
described as follows. Let G = ^V, E h be
an undirected graph where V and E
denote the sets of vertices and edges,
respectively. The vertex v 0 ! V is the
depot. Each edge e ! E has a cost
c(e) > 0. If there is a task on this edge, a
positive demand is associated to e. The
task set T is the set of edges with positive demands. A fleet of vehicles with a
given capacity Q > 0 are allocated to
serve all the tasks in T, starting and terminating at the identical depot v 0 . The
objective of CARP is to efficiently allocate these vehicles and select the optimal
set of routes to serve tasks while the
total demand of tasks served on any
route does not exceed Q.

m

/ e/ c

deadheading cost

,
dist (tail (t k, lk), v 0)
m
1444
42444
43
deadheading cost from last task to depot
(1)
s.t. t k, i ! T, 6k ! {1, f, m},
	
(2)
i ! {1, f, l k},
head (t k, 1) = tail (t k, lk) = v 0,
	  
6k ! {1, f, m}, (3)
	   t k, i ! t kl, il, 6 (k, i) ! (kl , il ), (4)
	   t k, i ! inv (t kl, il), 6 (k, i) ! (kl , i l ),(5)
+

	  
	  

m

/ lk =

T , (6)

k=1
lk

/ d (t k,i) # Q, 6k ! {1, f, m},(7)

i=1

where head (t k, i) and tail (t k, i) denote the
two endpoints of the task t k, i . When
i = 1, tail (t k, 0) is defined as the depot v 0 .
inv (t k, i) denotes the reverse direction of
t k, i . Besides the serving cost c(t) of each
task t, the deadheading cost, defined as the
cost of traversing the shortest path
between a pair of tasks, is often considered as well. dist (v i, v j) denotes the
shortest distance from vertex vi to vertex
vj. Eq. (1) indicates the minimization of
C (x), the sum of the serving and deadheading costs of the set of routes x. The
domain of variables is defined in Eq. (2).
Eq. (3) indicates that each route should
start and end at the depot. Eqs. (4) and
(5) ensure that each task will be served
in one direction only, i.e., (k = kl ) and
(i = il ) won't hold simultaneously.
Together with Eq. (6), Eqs. (4) and (5)
further ensure that each task will be

served exactly once. The constraint of
vehicle capacity is implied in Eq. (7).
2) Taxonomy of CARP
Similar to the taxonomy of VRP [14],
we propose a taxonomy of CARPs as
follows:
1)	static and deterministic CARP;
2)	dynamic and deterministic CARP;
3)	static and stochastic CARP;
4)	dynamic and stochastic CARP.
A CARP instance can be dynamic, i.e.,
the variables are unknown a priori and
may change over time; otherwise, it is
static. A deterministic CARP assumes no
random element involved in the problem, thus the variables are all deterministic. Only static input (e.g., edges, tasks
and demands) is considered in the static
and deterministic CARP, while in the
dynamic and deterministic version, the
input changes over time, such as an
increasing travelling cost because of the
increasing vehicle load. The stochastic
CARP or CARP with uncertainties, in
general, considers that the input variables are random and their exact values
are only known at the time of execution. The use of terms dynamic and stochastic is sometimes ambiguous. Table I
lists some of the main differences
between the static and stochastic CARP
and the dynamic and stochastic version.
In this paper, we focus on the CARP
with uncertainties, either static or
dynamic. Studies on dynamic and deterministic CARP are out of the scope of
this paper. From the literature, we have
observed that all review studies so far
aimed at solving static and stochastic
CARP, most of which were based on
methods for solving static and deterministic CARP. Few treated a stochastic
CARP as a stochastic problem. To focus

TABLE I Comparison between static and stochastic CARP and dynamic and stochastic CARP.
STATIC AND STOCHASTIC CARP

DYNAMIC AND STOCHASTIC CARP

A PRIORI SOLUTION IS COMPUTED BY OFFLINE PLANNING

ONLINE PLANNING

ONLINE REPAIRING IS APPLIED ACCORDING TO ACTUAL
VARIABLE VALUES

RE-OPTIMIZATION WHILE TRAVELLING IN REAL TIME

TASKS/
CUSTOMERS

ALL POTENTIAL CUSTOMERS ARE KNOWN IN ADVANCE, WHILE
EACH HAPPENS WITH A PROBABILITY

SOME CUSTOMERS ARE KNOWN TO HAPPEN WITH A PROBABILITY
NEW REQUESTS CAN BE MADE DURING EXECUTION

TIMING

SOMETIMES TIME WINDOW IS CONSIDERED

URGENCY OF TASK IS USUALLY CONSIDERED

PLANNING

FEBRUARY 2021 | IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE

65
IEEE Computational Intelligence Magazine - February 2021

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