Nathalie Helal
email: nathaliehelal@ens.univ-artois.fr

Frédéric Pichon
email: frederic.pichon@univ-artois.fr

Daniel Porumbel
email: daniel.porumbel@cnam.fr

David Mercier
email: david.mercier@univ-artois.fr

Éric Lefèvre
email: eric.lefevre@univ-artois.fr

The Capacitated Vehicle Routing Problem with Evidential Demands $

Keywords: Vehicle routing problem, Chance constrained programming, Stochastic programming with recourse, Belief function

We propose to represent uncertainty on customer demands in the Capacitated Vehicle Routing Problem (CVRP) using the theory of evidence. To tackle this problem, we extend classical stochastic programming modelling approaches. Specifically, we propose two models for this problem. The first model is an extension of the chance-constrained programming approach, which imposes certain minimum bounds on the belief and plausibility that the sum of the demands on each route respects the vehicle capacity. The second model extends the stochastic programming with recourse approach: for each route, it represents by a belief function the uncertainty on its recourses, i.e., corrective actions performed when the vehicle capacity is exceeded, and defines the cost of a route as its classical cost (without recourse) plus the worst expected cost of its recourses. We solve the proposed models using a metaheuristic algorithm and present experimental results on instances adapted from a well-known CVRP data set.

Introduction

In the Capacitated Vehicle Routing Problem (CVRP), we are given a fleet of vehicles with identical capacity located at a depot and a set of customers with known demands located on the vertices of a graph. The goal of this problem is to determine a route for each vehicle, such that the set of routes for all the vehicles has the least total cost, all customer demands are fully serviced, the capacity of each vehicle is always respected and each customer is visited by exactly one route. The CVRP is NP-hard since it contains the traveling salesman problem as a particular case (one route and unbounded capacity). It can be written as an integer linear program. The CVRP has generated a large body of research, since it belongs to the class of local transportation or delivery problems affecting the most expensive component in the distribution network [START_REF] Bodin | Routing and scheduling of vehicles and crews: The state of the art[END_REF].

Yet, many industrial applications are confronted with uncertainty on customer demands in their distribution problems involving the CVRP, and the exact customer demands are mostly revealed when the servicing vehicles arrive at the customers. Accordingly, several authors (see, e.g., [START_REF] Gendreau | Stochastic vehicle routing[END_REF][START_REF] Gendreau | A tabu search heuristic for the vehicle routing problem with stochastic demands and customers[END_REF] and the references therein) tackled this issue by assuming that customer demands are random variables and the associated problem is the well-known Capacitated Vehicle Routing Problem with Stochastic Demands (CVRPSD). Two of the most widelyused frameworks for modelling stochastic problems, such as the CVRPSD, are the Chance-Constrained Programming (CCP) approach and the Stochastic Programming with Recourse (SPR) approach [START_REF] Birge | Introduction to Stochastic Programming[END_REF]. Modelling the CVRPSD via CCP amounts to using a probabilistic capacity constraint that requires the probability of respecting the capacity constraint to be above a certain threshold. The CCP modelling technique does not consider the additional cost of recourse (or corrective) actions necessary if capacity constraints fail to be satisfied. The SPR approach does consider situations needing recourses and it aims at minimizing the initially-planned travel cost plus the expected cost of the recourses executed along routes, e.g., returning to the depot and unloading in order to bring to feasibility a violated capacity constraint.

The probabilistic approach to modelling uncertainty is not necessarily wellsuited to all real-life situations. In particular, its ability to handle epistemic uncertainty (uncertainty arising from lack of knowledge) has been criticised [START_REF] Baudrit | Joint propagation of probability and possibility in risk analysis: Towards a formal framework[END_REF][START_REF] Ben Abdallah | Combining statistical and expert evidence using belief functions: Application to centennial sea level estimation taking into account climate change[END_REF]. The typical approach to representing basic epistemic uncertainty is the setvalued approach [START_REF] Dubois | Decision-making Process: Concepts and Methods, chapter Formal Representations of Uncertainty[END_REF]. It is sensible when, e.g., all that is known about the customer demands is that they belong to some intervals. This kind of uncertainty in the CVRP is generally addressed using robust optimisation, where one optimises against the worst-case scenario, that is, one wants to obtain solutions that are robust to all realisations of customer demands that are deemed possible (see, e.g., [START_REF] Sungur | A robust optimization approach for the capacitated vehicle routing problem with demand uncertainty[END_REF]). However, the set-valued approach to uncertainty representation may be too coarse and may thus lead to solutions that are too conservative, hence not useful.

In the last forty years, the necessity to account for all facets of uncertainty has been recognized and alternative uncertainty frameworks extending both the probabilistic and set-valued ones have appeared [START_REF] Baudrit | Joint propagation of probability and possibility in risk analysis: Towards a formal framework[END_REF]. In particular, the theory of evidence introduced by Shafer [START_REF] Shafer | A mathematical theory of evidence[END_REF], based on some previous work from Dempster [START_REF] Dempster | Upper and lower probabilities induced by a multivalued mapping[END_REF], has emerged as a theory offering a compromise between expressivity and complexity, which seems interesting in practice as its successful application in several domains testifies (see [START_REF] Denoeux | 40 years of Dempster-Shafer theory[END_REF] for a recent survey of evidence theory applications). This theory, also known as belief function theory, may be used to model various forms of information, such as expert judgements and statistical evidence, and it also offers tools to combine and propagate uncertainty [START_REF] Ben Abdallah | Combining statistical and expert evidence using belief functions: Application to centennial sea level estimation taking into account climate change[END_REF].

In the context of the CVRP, the theory of evidence may be used to represent uncertainty on customer demands leading to an optimisation problem, which will be referred to as the CVRP with Evidential Demands (CVRPED). Using the theory of evidence in this problem seems particularly interesting as it allows one to account for imperfect knowledge about customer demands, such as knowing that each customer demand belongs to one or more sets with a given probability allocated to each set -an intermediary situation between probabilistic and set-valued knowledge. In this paper, we propose to address the CVRPED by extending the CCP and SPR modelling approaches into the formalism of evidence theory. Although the focus will be to extend stochastic programming approaches, we will also connect our formulations with robust optimisation.

To our knowledge, evidence theory has not yet been considered to model uncertainty in large-scale instances of an NP-hard optimisation problem like the CVRP. Indeed, it seems that so far, only other non classical uncertainty theories, and in particular fuzzy set theory [START_REF] Teodorovic | The fuzzy set theory approach to the vehicle routing problem when demand at nodes is uncertain[END_REF][START_REF] Brito | Fuzzy optimization in vehicle routing problems[END_REF][START_REF] Peng | Vehicle routing problem with fuzzy demands and the particle swarm optimization solution[END_REF][START_REF] Chen | Particle swarm optimization for vehicle routing problem with uncertain demand[END_REF], have been used in such problems. Besides, modelling uncertainty in optimisation problems using evidence theory has concerned only continuous design optimisation problems1 [START_REF] Mourelatos | A design optimization method using evidence theory[END_REF][START_REF] Srivastava | An evolutionary algorithm based approach to design optimization using evidence theory[END_REF] and continuous linear programs [START_REF] Masri | Belief linear programming[END_REF]. Specifically in [START_REF] Mourelatos | A design optimization method using evidence theory[END_REF], the reliability of the system is optimized, while uncertainty is handled by limiting the plausibility of constraints violation into a small degree; while in [START_REF] Srivastava | An evolutionary algorithm based approach to design optimization using evidence theory[END_REF] the problem was handled differently, and the plausibility of a constraint failure was converted into a second objective to the problem that should be minimized. Of particular interest is the work of Masri and Ben Abdelaziz [START_REF] Masri | Belief linear programming[END_REF], who extended the CCP and SPR modelling approaches, in order to model continuous linear programs embedding belief functions, which they called the Belief Constrained Programming (BCP) and the recourse approaches, respectively. In comparison, in this work, we generalise CCP and SPR to an integer linear program involving uncertainty modelled by evidence theory. Borrowing from [START_REF] Masri | Belief linear programming[END_REF], we propose to model the CVRPED by methods that may be called the BCP modelling of the CVRPED and the recourse modelling of the CVRPED. For both models, the resolution algorithm is a simulated annealing algorithm; we use a metaheuristic, as the CVRPED derives from the CVRP, which is NP-hard.

The paper is structured as follows. Section 2 summarises the basic preliminaries on the CVRP and on the CVRPSD modelling via CCP and SPR, along with the necessary background on evidence theory. In section 3, the BCP model and the recourse model for the CVRPED are presented and some of their properties are studied. In Section 4 we solve the BCP model and the recourse model of the CVRPED using a simulated annealing algorithm and perform experiments on instances generated from CVRP benchmarks. In Section 5, we conclude and state the perspectives of the present work.

Background

This section recalls necessary background on the CVRP, the CVRPSD and its stochastic programming formulations, as well as some concepts of belief function theory needed in this paper.

The CVRP

In the CVRP, a fleet of m identical vehicles with a given capacity limit Q, initially located at a depot, must collect 2 goods from n customers, with d i such that 0 < d i ≤ Q the deterministic collect demand of client i, i = 1, . . . , n. The objective in the CVRP is to find a set of m routes with minimum cost to serve all the customers such that total customer demands on any route must not exceed Q, each route starts and ends at the depot, and each customer is serviced only once.

Formally, it is convenient to represent the depot by an artificial client i = 0, whose demand always equals 0, i.e., d 0 = 0. The CVRP may be defined on a graph G = (V, E) such that V = {0, . . . , n} is the vertex set and E = {(i, j) |i = j; i, j ∈ V } is the arc set. V represents the customers and the depot that corresponds to vertex 0. A travel cost (or travel time or distance -these terms are interchangeable) c i,j is associated with every edge in E. Travel costs are such that c i,j = c j,i , ∀ (i, j) ∈ E and they satisfy the triangle inequality: [START_REF] Toth | The Vehicle Routing Problem, chapter An Overview of Vehicle Routing Problems[END_REF]. Let R k be the route associated to vehicle k and w k i,j a binary variable that equals 1 if vehicle k travels from i to j and serves j (except if j is the depot), and 0 if it does not. A proper formulation for the CVRP [START_REF] Bodin | Routing and scheduling of vehicles and crews: The state of the art[END_REF][START_REF] Laporte | The vehicle routing problem: An overview of exact and approximate algorithms[END_REF] is:

c i,j ≤ c i,l + c l,j , ∀i, l, j ∈ V . Besides, c i,i = +∞, ∀i ∈ V
min m k=1 C(R k ), (1)
where

C(R k ) = n i=0 n j=0 c i,j w k i,j , (2)
subject to 2 The problem can also be presented in terms of delivery, rather than collection, of goods.

n i=0 m k=1 w k i,j = 1, j = 1, . . . , n, (3)
n i=0 w k i, = n j=0 w k ,j , k = 1, . . . , m , = 0, . . . , n, (4)
n j=1 w k 0,j ≤ 1, k = 1, . . . , m, (5)
i,j∈L i =j

m k=1 w k i,j ≤ |L] -1, L ⊆ V \ {0}, (6)
n i=1 d i n j=0 w k i,j ≤ Q, k = 1, . . . , m. (7)
Constraints (3) make sure that exactly one vehicle arrives at client j, j = 1, . . . , n. Constraints (4) ensure the continuity of the routes (flow): if vehicle k leaves vertex , vehicle k must also enter vertex , ensuring that the route is a proper unbroken cycle in the graph. Constraints (5) oblige vehicle k, k = 1, . . . , m, to leave at most one time the depot. The choices of the arcs that are represented by w k i,j is also restricted by constraints [START_REF] Bertsimas | Theory and applications of robust optimization[END_REF], that forbids subtours solutions [START_REF] Bodin | Routing and scheduling of vehicles and crews: The state of the art[END_REF]. Without these latter constraints, we can have a vehicle performing the path (i 1 , i 2 , . . . , i t ) with 0 / ∈ {i 1 , i 2 , . . . , i t }. Constraints [START_REF] Birge | Introduction to Stochastic Programming[END_REF] state that every vehicle cannot carry more than its capacity limit. We note that constraints [START_REF] Augerat | Approche polyédrale du problème de tournées de vehicules[END_REF] and ( 4 w k i,0 ≤ 1, k = 1, . . . , m, i.e., vehicle k is obliged to return at most one time to the depot. Finally, we remark that this model requires using at most m vehicles, since for some k, we might have w k i,j = 0, i, j = 1, . . . , n. Example 1. Suppose m = 2 vehicles with capacity limit Q = 10, which must collect the demands of n = 4 customers with demands d 1 = 3, d 2 = 4, d 3 = 5, d 4 = 6. These customers are illustrated in Figure 1a (the depot is denoted by "0"), along with their associated travel cost matrix in Figure 1b. A candidate solution, i.e., a set of routes satisfying constraints (3)- [START_REF] Birge | Introduction to Stochastic Programming[END_REF], to this problem is shown in Figure 1c; the total travel cost (the value of the objective function in Equation (1)) of this solution is 24.1. An optimal solution, i.e., a set of routes satisfying constraints (3)- [START_REF] Birge | Introduction to Stochastic Programming[END_REF] and with minimum cost among the candidate solutions, is provided in Figure 1d; its total travel cost is 17.8.

The CVRPSD

The CVRPSD is a variation of the CVRP, which introduces stochastic demands in the CVRP, i.e., d i , i = 1, . . . , n, are now random variables, such that

P (d i ≤ Q) = 1 (
these random variables are usually assumed to be independent). The CVRPSD is typically handled using the framework of stochastic programming, which models stochastic programs in two stages: an "a priori" solution is established in the first stage, and then in the second stage the realisations of the random variables -the actual demands in the case of the CVRPSD -are revealed and corrective actions are carried out if necessary on the first stage solution [START_REF] Gendreau | Stochastic vehicle routing[END_REF]. More precisely, the CVRPSD is either modelled as a so-called chance-constrained program [START_REF] Charnes | Cost horizons and certainty equivalents: an approach to stochastic programming of heating oil[END_REF] or as a stochastic program with recourse [START_REF] Birge | Introduction to Stochastic Programming[END_REF]; these two models are detailed in the next two sections.

The CVRPSD modelled by CCP

Chance constrained programming consists in finding a first stage solution for which the probability that the total demand on any route exceeds the capacity is constrained to be below a given threshold. Formally, a CCP formulation for the CVRPSD corresponds to the same optimisation problem described for the CVRP in Section 2.1 except that deterministic constraints represented by [START_REF] Birge | Introduction to Stochastic Programming[END_REF] are replaced by the following so called chance-constraints:

P   n i=0 d i n j=0 w k i,j ≤ Q   ≥ 1 -β, k = 1, . . . , m, (8)
where 1 -β is the minimum allowable probability that any route respects vehicle capacity and thus succeeds. Note that this model represents a so-called individual chance-constrained model, since the inequality must be satisfied for every k separately; see [START_REF] Sengupta | A generalization of some distribution aspects of chance-constrained linear programming[END_REF][START_REF] Birge | Introduction to Stochastic Programming[END_REF] for more details.

This model does not consider the cost of corrective actions that may be necessary when the first stage solution is implemented. Indeed, when implementing this solution, it is unlikely yet possible that the vehicle capacity is exceeded, i.e., route failures occur, when the actual demands are revealed and thus corrective actions may have to be carried out in the second stage.

The CVRPSD modelled by SPR

Stochastic programming with recourse deals explicitly with the possibility of a first stage solution failure, by incorporating into the objective of the problem the penalty cost of corrective, or recourse, actions such as allowing vehicles to return to the depot to unload. More specifically, in the SPR modelling of the CVRPSD, the expected penalty cost of the recourse actions happening in the second stage is considered and the problem is to find a set of routes which has the minimal expected cost defined as the cost of the first stage solution if no failures occur, plus the expected penalty cost of the recourse actions of the second stage. Formally, let C e (R k ) denote the expected cost of a route R k defined by

C e (R k ) = C(R k ) + C p (R k ), (9)
with C(R k ) the cost defined by (2) representing the cost of traveling along R k if no recourse action is performed, and C p (R k ) the expected penalty cost on R k -C p (R k ) may be defined in many different ways depending on the recourse policy used (see, e.g., [START_REF] Christiansen | A branch-and-price algorithm for the capacitated vehicle routing problem with stochastic demands[END_REF][START_REF] Gauvin | A branch-cut-and-price algorithm for the vehicle routing problem with stochastic demands[END_REF][START_REF] Laporte | An integer l-shaped algorithm for the capacitated vehicle routing problem with stochastic demands[END_REF][START_REF] Dror | Vehicle routing with stochastic demands: Properties and solution frameworks[END_REF]). Then, a SPR model for the CVRPSD consists in modifying the CVRP model presented in Section 2.1 as follows. The objective is to find a set of routes minimizing the sum of the expected costs of routes R k , i.e.,

min m k=1 C e (R k ), (10)
subject to constraints (3)-( 6) excluding constraints [START_REF] Baudrit | Joint propagation and exploitation of probabilistic and possibilistic information in risk assessment[END_REF], which is replaced by

n j=1 w k 0,j = 1, k = 1, . . . , m, (11)
that is exactly m vehicles must be used. Constraints (5) may be considered instead of [START_REF] Chen | Particle swarm optimization for vehicle routing problem with uncertain demand[END_REF], but then the problem becomes even more difficult to solve. In addition, note that the binary variables w k i,j do not encode recourse actions: they represent only the initially planned solution routes, i.e., the first stage solution.

Evidence theory

In this section, basic concepts as well as some more advanced notions of evidence theory [START_REF] Shafer | A mathematical theory of evidence[END_REF], which are necessary in our study on the CVRPED, are recalled.

Basics of evidence theory

Let x be a variable taking its values in a finite domain X = {x 1 , . . . , x K }. In this theory, uncertain knowledge about x may be represented by a Mass Function (MF) defined as a mapping m X : 2 X → [0, 1] such that m X (∅) = 0 and A⊆X m X (A) = 1. The superscript X can be omitted when there is no risk of confusion. Each mass m X (A) represents the probability of knowing only that x ∈ A. Subsets A ⊆ X such that m X (A) > 0 are called the focal sets of m X . To be consistent with the stochastic case terminology, a variable x whose true value is known in the form of a MF will be called an evidential variable.

Mass functions generalise both probabilistic and set valued representations of uncertainty since:

• a MF whose focal sets are singletons, i.e., m X (A) > 0 iff |A| = 1, corresponds to a probability mass function and is called a Bayesian MF;

• a MF having only one focal set, i.e., m X (A) = 1 for some A ⊆ X, corresponds to a set and is called a categorical MF.

Another special case of mass functions are those whose focal sets are nested, in which case they are called consonant.

Equivalent representations of a MF m X are the belief and plausibility functions defined, respectively, as

Bel X (x ∈ A) = C⊆A m X (C), ∀A ⊆ X, P l X (x ∈ A) = C∩A =∅ m X (C), ∀A ⊆ X.
The degree of belief Bel X (x ∈ A) can be interpreted as the probability that the evidence about x and represented by m X , supports (implies) x ∈ A, whereas the degree of plausibility P l X (x ∈ A) is the probability that the evidence is consistent with x ∈ A. For all A ⊆ X, we have Bel X (x ∈ A) ≤ P l X (x ∈ A) and

P l X (x ∈ A) = 1 -Bel X (x ∈ A ), (12)
where A denotes the complement of A. Besides, if m X is Bayesian, then Bel X (x ∈ A) = P l X (x ∈ A), for all A ⊆ X, and this function is a probability measure. If m X is categorical, then Bel X (x ∈ A) ∈ {0, 1} and P l X (x ∈ A) ∈ {0, 1}, for all A ⊆ X, and the plausibility function restricted to the singletons corresponds to the indicator function of the set associated to m X . If m X is consonant, then its associated plausibility function is a possibility measure [START_REF] Zadeh | Fuzzy sets as a basis for a theory of possibility[END_REF]:

it verifies P l X (x ∈ A ∪ B) = max(P l X (x ∈ A), P l X (x ∈ B)), for all A, B ⊆ X.
Given a MF m X and a function h : X → R + , it is possible to compute the lower expected value E * (h, m X ) and upper expected value E * (h, m X ) of h relative to m X defined, respectively, as [START_REF] Denoeux | Analysis of evidence-theoretic decision rules for pattern classification[END_REF]

E * (h, m X ) = A⊆X m X (A) min x∈A h(x), (13)
E * (h, m X ) = A⊆X m X (A) max x∈A h(x). (14)
If m X is Bayesian, then E * (h, m X ) and E * (h, m X ) reduce to the classical (probabilistic) expected value of h relative to the probability mass function m X .

Comparisons of belief functions

The informative content of two set-valued pieces of information x ∈ A and x ∈ B, A, B ⊆ X, about x is naturally compared by saying that x ∈ A is more informative than x ∈ B if A ⊂ B. An extension of this to compare the informative content of mass functions in terms of specificity is the notion of specialisation [START_REF] Dubois | A set-theoretic view of belief functions: logical operations and approximations by fuzzy sets[END_REF]: a MF m X 1 defined on X is said to be at least as informative (or specific) as another MF m X 2 defined on X, which is denoted by m X 1 m X 2 , if and only if there exists a non-negative square matrix

S = [S(A, B)], A, B ∈ 2 X , verifying A⊆X S(A, B) = 1, ∀B ⊆ X, (15)
S(A, B) > 0 ⇒ A ⊆ B, A, B ⊆ X, (16)
m X 1 (A) = B⊆X S(A, B)m X 2 (B), ∀A ⊆ X. (17)
The term S(A, B) may be seen as the proportion of the mass m X 2 (B) which "flows down" to A. Let us also recall that we have [START_REF] Dubois | A set-theoretic view of belief functions: logical operations and approximations by fuzzy sets[END_REF]

m X 1 m X 2 ⇒ [Bel X 1 (x ∈ A), P l X 1 (x ∈ A)] ⊆ [Bel X 2 (x ∈ A), P l X 2 (x ∈ A)], ∀A ⊆ X. (18)
Assume now that an ordering has been defined among the elements of X. By convention, assume that x 1 < . . . < x K . Let A a,a denote the subset {x a , . . . , x a }, for 1 ≤ a ≤ a ≤ K and let I denote the set of intervals of X: I = {A a,a , 1 ≤ a ≤ a ≤ K}. Deciding whether an interval A a,a , i.e. an intervalvalued piece of information x ∈ A a,a about x, is smaller or equal to another interval B b,b can be done in several ways, and in particular the so-called lattice ordering denoted ≤ lo is defined as [START_REF] Destercke | Ranking of fuzzy intervals seen through the imprecise probabilistic lens[END_REF]:

A a,a ≤ lo B b,b if a ≤ b and a ≤ b.
This ordering can be extended to arbitrary subsets A and B of X as follows: A ≤ lo B if a ≤ b and a ≤ b, where a and b (resp. a and b) denote the indices of the lowest (resp. highest) values in A and B. More generally, following the extension above of inclusion between sets to mass functions, the ordering ≤ lo of subsets can be extended to compare mass functions in terms of ranking as follows: a MF m X 1 is said to be at least as small as another MF m X 2 , which is denoted by m X 1 m X 2 , if and only if there exists a non-negative square matrix

R = [R(A, B)], A, B ∈ 2 X , verifying A⊆X R(A, B) = 1, ∀B ⊆ X, (19)
R(A, B) > 0 ⇒ A ≤ lo B, A, B ⊆ X, (20)
m X 1 (A) = B⊆X R(A, B)m X 2 (B), ∀A ⊆ X. (21)
In other words, the mass m X 2 (B) can be shared among smaller (according to ≤ lo ) subsets than B. We note that extensions of interval rankings to belief functions were already proposed in [START_REF] Denoeux | Extending stochastic ordering to belief functions on the real line[END_REF], but in the context of belief functions on the real line and the ranking ≤ lo was not considered. To our knowledge, the definition of appears thus to be new; it will be particularly useful in conjunction with Proposition 1, which is somewhat of a counterpart to Eq. ( 18) for , to exhibit a property of the BCP model for the CVPRED:

Proposition 1. For any Q, 1 ≤ Q ≤ K, we have m X 1 m X 2 ⇒ Bel X 1 (x ∈ A 1,Q ) ≥ Bel X 2 (x ∈ A 1,Q ), P l X 1 (x ∈ A 1,Q ) ≥ P l X 2 (x ∈ A 1,Q ). (22)
The converse does not hold, i.e., the implication in [START_REF] Destercke | Cautious label ranking with label-wise decomposition[END_REF] is strict.

Proof. See Appendix A.

Proposition 1 basically says that if a MF m X 1 is at least as small as a MF m X 2 , then the belief, according to the piece of evidence m X 1 , that the value of x is smaller or equal than a value x Q is at least as great as the belief of the same event according to the piece of evidence m X 2 (and the same goes for the plausibility), as may be expected from the meaning of .

To sum up this section, m X 1 m X 2 basically means that m X 2 represents a less precise piece of uncertain knowledge about x than m X 1 , whereas m X 1 m X 2 means that m X 2 represents a piece of uncertain knowledge telling that x takes a higher value than what m X 1 tells.

Uncertainty propagation

Let x 1 , . . . , x N be N variables defined on the finite domains X 1 , . . . , X N , respectively. A MF m X1ו••×X N defined on the Cartesian product X 1 ו • •×X N represent joint knowledge about the values of these variables.

Similarly as in probability theory, one can obtain joint knowledge about a subset of the evidential variables x 1 , . . . , x N by marginalising MF m X1ו••×X N on the domains of these variables. For instance, and without lack of generality, the marginalisation of

m X1ו••×X N on X 1 × X 2 is the MF m X1ו••×X N ↓X1×X2 on X 1 × X 2 defined as, ∀A ⊆ X 1 × X 2 , m X1ו••×X N ↓X1×X2 (A) = {B⊆X1ו••×XN ,B ↓X 1 ×X 2 =A} m X1ו••×X N (B), ( 23
)
where

B ↓X1×X2 denotes the projection of B onto X 1 × X 2 . If MF m X1ו••×X N satisfies, for all A ⊆ X 1 × • • • × X N , m X1ו••×X N (A) = N i=1 m X1ו••×X N ↓Xi (A ↓Xi ) if A = × N i=1 A ↓Xi , 0 otherwise, (24)
then variables x 1 , . . . , x N are said to be evidentially independent (or independent for short) [START_REF] Shafer | A mathematical theory of evidence[END_REF]. In practice, this happens when joint knowledge about variables x 1 , . . . , x N , is built from marginal knowledge m Xi , i = 1, . . . , N , on each of these variables, supplied by sources assumed to be independent [START_REF] Pichon | Relevance and truthfulness in information correction and fusion[END_REF], as illustrated by Example 2 (other reasons for this to happen can also be found in [START_REF] Couso | A survey of concepts of independence for imprecise probabilities[END_REF][START_REF] Couso | Independence concepts in evidence theory[END_REF]).

Example 2. Let X 1 = {x 1 1 , x 1 2 , x 1 3 } and X 2 = {x 2 1 , x 2 2 }.
Furthermore, assume two sources providing the pieces of evidence m X1 and m X2 , respectively, about x 1 and x 2 , defined as m X1 ({x

1 1 , x 1 2 }) = 0.8, m X1 ({x 1 2 , x 1 3 }) = 0.2 and m X2 ({x 2 1 }) = 0.7, m X2 (X 2 ) = 0.3.
Assuming that the sources are independent, we obtain

m X1×X2 ({x 1 1 , x 1 2 } × {x 2 1 }) := m X1 ({x 1 1 , x 1 2 }) • m X2 ({x 2 1 }) = 0.56, m X1×X2 ({x 1 1 , x 1 2 } × X 2 ) := m X1 ({x 1 1 , x 1 2 }) • m X2 (X 2 ) = 0.24, m X1×X2 ({x 1 2 , x 1 3 } × {x 2 1 }) := m X1 ({x 1 2 , x 1 3 }) • m X2 ({x 2 1 }) = 0.14, m X1×X2 ({x 1 2 , x 1 3 } × X 2 ) := m X1 ({x 1 2 , x 1 3 }) • m X2 (X 2 ) = 0.06.
m X1×X2 clearly satisfies [START_REF] Dubois | A set-theoretic view of belief functions: logical operations and approximations by fuzzy sets[END_REF].

Furthermore, let y be a variable with finite domain Y , such that y = f (x 1 , . . . , x N ) for some mapping f :

X 1 × • • • × X N → Y . As shown in [25], uncertain knowledge m X1ו••×X N about variables x 1 , . . . , x N , induces MF m Y about the value of y defined as m Y (B) = f (A)=B m X1ו••×X N (A), ∀B ⊆ Y, (25)
with

f (A) = {f (x 1 k 1 , . . . , x N k N )|(x 1 k 1 , . . . , x N k N ) ∈ A} for all A ⊆ X 1 × • • • × X N .

Modelling the CVRPED

This section formalises and studies the CVRPED, which is an integer linear program involving uncertainty represented by belief functions. We obtain this problem when customer demands in the CVRP are no longer deterministic or random, but evidential, i.e., the variables d i , i = 1, ..., n, are evidential. Following what has been done for the case of linear programs involving evidential uncertainty [START_REF] Masri | Belief linear programming[END_REF], we may extend stochastic programming approaches to this integer linear program embedding belief functions: the CCP modelling of the CVRPSD is generalised into a BCP modelling of the CVRPED in Section 3.1, and the recourse modelling of the CVRPSD is generalised into a recourse modelling of the CVRPED in Section 3.2.

Note that, to simplify the exposition, we assume actual customer demands to be positive integers, hence the value of the demand of any customer belongs to the set Θ = {1, 2, . . . , Q}. In addition, since the CVPRED involves n evidential variables d i , i = 1, ..., n, with respective domains Θ i := Θ, i = 1, ..., n, then formally this means that knowledge about customer demands in this problem is represented by a MF m Θ n on Θ n := × n i=1 Θ i . In practical situations, it may be the case that only marginal knowledge in the form of a MF m Θi may be available about the individual demand of each customer i, i = 1, . . . , n. In such case, as explained in Section 2.3.3, m Θ n can be derived by assuming that these pieces of knowledge about individual customer demands have been provided by independent sources. In other words, if necessary and justified, evidential variables d i , i = 1, ..., n, may be assumed to be independent, similarly as it may be done in the stochastic case. However, let us underline that the BCP and recourse modellings of the CVRPED proposed in the next two sections, are general in that they do not rely on such independence assumption, i.e., they do not need m Θ n to satisfy a property of the form (24).

The CVRPED modelled by BCP

A generalisation of the CCP modelling of the CVRPSD to the case of evidential demands is proposed in this section. The model is provided in Section 3.1.1. Important particular cases of this model are discussed in Section 3.1.2. Influences of model parameters and of customer demand ranking on the optimal solution cost, are studied in Sections 3.1.3 and 3.1.4, respectively.

Formalisation

A BCP modelling of the CVRPED amounts to keeping the same optimisation problem described for the CVRP in Section 2.1 except that capacity constraints [START_REF] Birge | Introduction to Stochastic Programming[END_REF] are replaced by the following belief -constraints:

Bel   n i=1 d i n j=0 w k i,j ≤ Q   ≥ 1 -β, k = 1, . . . , m, (26)
P l   n i=1 d i n j=0 w k i,j ≤ Q   ≥ 1 -β, k = 1, . . . , m, (27)
with β ≥ β and where 1 -β (resp. 1 -β) is the minimum allowable degree of belief (resp. plausibility) that a vehicle capacity is respected on any route.

Remark 1. From (12), constraints (27) are equivalent to Bel   n i=1 d i n j=0 w k i,j > Q   ≤ β, k = 1, . . . , m. (28)
Hence, constraints (26) and (27) amount to requiring that for any route there is a lot (at least 1 -β) of support (belief ) of respecting vehicle capacity and not a lot (at most β) of support of violating vehicle capacity. 26) and ( 27) on the route (0, 4, 1, 2, 0) (route circled in red).

Note that in order to evaluate the belief-constraints ( 26) and ( 27), the total demand on every route must be determined by summing all customer demands on that route. Suppose a route R having N clients, then the sum of customer demands on R is obtained using [START_REF] Dubois | Random sets and fuzzy interval analysis[END_REF], where f is the addition of integers and where m X1ו••×X N is the marginalisation of m Θ n on the domains of the evidential variables dr 1 , . . . , dr N associated with the N clients on the route, with X i the domain of the evidential variable dr i associated with the i-th client on R. The computation of the total demand on a route as well as the evaluation of constraints ( 26) and [START_REF] Gauvin | A branch-cut-and-price algorithm for the vehicle routing problem with stochastic demands[END_REF] for that route are illustrated by Example 3.

Example 3. Suppose that β = 0.1 and β = 0.05 and that we have n = 5 customers and m = 2 vehicles with capacity limit Q = 15. Moreover, suppose knowledge about customer demands is represented by MF m Θ n defined on

Θ n = Θ 5 = Θ 1 × Θ 2 × Θ 3 × Θ 4 × Θ 5 by: m Θ 5
({(2, 3, 8, 4, 5), [START_REF] Augerat | Approche polyédrale du problème de tournées de vehicules[END_REF][START_REF] Baudrit | Joint propagation and exploitation of probabilistic and possibilistic information in risk assessment[END_REF][START_REF] Bertsimas | Theory and applications of robust optimization[END_REF][START_REF] Birge | Introduction to Stochastic Programming[END_REF][START_REF] Baudrit | Joint propagation of probability and possibility in risk analysis: Towards a formal framework[END_REF], [START_REF] Augerat | Approche polyédrale du problème de tournées de vehicules[END_REF][START_REF] Baudrit | Joint propagation of probability and possibility in risk analysis: Towards a formal framework[END_REF][START_REF] Birge | Introduction to Stochastic Programming[END_REF][START_REF] Bertsimas | Theory and applications of robust optimization[END_REF], 2)}) = 0.5, m Θ 5 ({(5, 5, 6, 4, 7), (7, 6, 5, 3, 4)}) = 0.3,

m Θ 5 ({(4, 6, 7, 4, 6), (5, 5, 6, 5, 7)}) = 0.2. ( 29
)
Consider the two routes represented in Figure 2. Let us compute the sum of the customer demands on the route (0, 4, 1, 2, 0), i.e., the route that collects the demand of customer 4, then the demand of customer 1 and finally the demand of customer 2. Call this route R. On this route, there are N = 3 clients. The first client is client 4, hence according to the above notation, we have dr 1 = d 4 and X 1 = Θ 4 . Similarly, we have

dr 2 = d 1 , X 2 = Θ 1 , dr 3 = d 2 , X 3 = Θ 2 .
The marginalisation of m Θ 5 on X 1 × X 2 × X 3 is the MF m Θ 5 ↓X1×X2×X3 defined as: [START_REF] Birge | Introduction to Stochastic Programming[END_REF][START_REF] Augerat | Approche polyédrale du problème de tournées de vehicules[END_REF][START_REF] Baudrit | Joint propagation and exploitation of probabilistic and possibilistic information in risk assessment[END_REF], (6, 3, 4)}) = 0.5,

m Θ 5 ↓X1×X2×X3 ({(4, 2, 3),
m Θ 5 ↓X1×X2×X3 ({(4, 5, 5), (3, 7, 6)}) = 0.3, m Θ 5 ↓X1×X2×X3 ({(4, 4, 6), (5, 5, 5)}) = 0.2. ( 30
)
Now given m Θ 5 ↓X1×X2×X3 and using Equation ( 25) such that f is the addition of integers, uncertainty on the sum of client demands on route R is represented by a MF denoted m Θ R and defined on the domain Θ R := {1, 2, . . . , N • Q} = {1, . . . , 45} by:

m Θ R ({9, 15, 13}) = 0.5, m Θ R ({14, 16}) = 0.3, m Θ R ({14, 15}) = 0.2. ( 31
)
The belief and plausibility that the sum of customer demands on R is smaller or equal than the vehicle capacity Q are then respectively:

Bel(d 4 + d 1 + d 2 ≤ 15) = m Θ R ({9, 15, 13}) + m Θ R ({14, 15}) = 0.7, P l(d 4 + d 1 + d 2 ≤ 15) = 1.
Hence, we have

Bel(dr 1 + dr 2 + dr 3 ≤ Q) < 1 -β = 0.9, P l(dr 1 + dr 2 + dr 3 ≤ Q) > 1 -β = 0.95.
In other words, constraint (27) is satisfied on R but constraint (26) is not, and thus any set of routes containing this route, such as the one shown in Figure 2, is not a candidate solution.

Suppose further that the number of focal sets of MF m X1ו••×X N is at most c, then the worst case complexity of evaluating each of the belief constraints ( 26) and [START_REF] Gauvin | A branch-cut-and-price algorithm for the vehicle routing problem with stochastic demands[END_REF]

on this route is O(N • Q N • c
). This latter complexity emerges from the following: the Q N factor is the maximal number of elements of a focal set of MF m X1ו••×X N . As we have N clients on a route, then for each element of a focal set of MF m X1ו••×X N , the addition of N integers must be performed, this explains N • Q N . The last factor in the complexity which is c, is related to performing the product N • Q N for the c focal sets of MF m X1ו••×X N . Nonetheless, in a particular case, the worst case complexity drops down significantly:

Remark 2. When the focal sets of m X1ו••×X N are all Cartesian products of N intervals, i.e., for all A ⊆ X 1 × • • • × X N such that m X1ו••×X N (A) > 0, we have A = A ↓X1 × • • • × A ↓X N with, for i = 1, . . . , N , A ↓Xi = A i ; A i for some integers A i , A i ∈ X i such that A i ≤ A i , the worst case complexity is O(N • c).
This complexity to evaluate constraint [START_REF] Dubois | Decision-making Process: Concepts and Methods, chapter Formal Representations of Uncertainty[END_REF] for route R comes from the fact that (with dr i the evidential variable associated with the i-th client on R):

Bel( N i=1 dr i ≤ Q) = {m X1ו••×X N (A)|A : max a∈A f (a) ≤ Q} = {m X1ו••×X N (A)|A : max (a1,••• ,a N )∈A N i=1 a i ≤ Q}(32) = {m X1ו••×X N (A)|A : N i=1 A i ≤ Q},
that is, at worst for each of the c focal sets of m X1ו••×X N , the addition of N integers needs to be performed. The complexity to evaluate constraint [START_REF] Gauvin | A branch-cut-and-price algorithm for the vehicle routing problem with stochastic demands[END_REF] is the same since we have

P l( N i=1 dr i ≤ Q) = {m X1ו••×X N (A)|A : min (a1,••• ,a N )∈A N i=1 a i ≤ Q} (33) = {m X1ו••×X N (A)|A : N i=1 A i ≤ Q}.
Remark 3. From (32), it is clear that the complexity to evaluate constraint [START_REF] Dubois | Decision-making Process: Concepts and Methods, chapter Formal Representations of Uncertainty[END_REF] for a given route R, depends on the complexity of finding for each focal set

A of m X1ו••×X N , the element (a 1 , • • • , a N ) ∈ A that maximises N i=1 a i . Suppose this latter complexity is at worst O(M ), 1 ≤ M ≤ Q N , for each focal set.
Then, the worst case complexity to evaluate constraint (26) for a route is O(N • M • c). Remark 2 provides a case, i.e., a particular shape for the focal sets of m X1ו••×X N , such that M = 1. We note that other, more refined yet still leading to tractable values for M , shapes for these focal sets may be considered. For instance, borrowing from robust optimisation [START_REF] Bertsimas | Theory and applications of robust optimization[END_REF], suppose that each focal set A of m X1ו••×X N can be written as

A = {(a 1 , • • • , a N )|a i ≥ A i , a i ≥ A i , N i=1 a i -A i A i ≤ Γ}, ( 34
)
for some lower bounds A i and upper bounds A i i = 1, . . . , N , and some uncertainty budget Γ [START_REF] Bertsimas | Theory and applications of robust optimization[END_REF]; budget Γ in (34) limits the sum of the deviations from the minimum demands A i , i = 1, . . . , N . Then, maximizing N i=1 a i for each focal set A is done over a more difficult, yet still manageable, shape than in Remark 2. Obviously, similar comments can be made about the complexity of constraint (27).

Particular cases of the BCP modelling of the CVRPED

It is interesting to remark that depending on the values chosen for β and β as well as the nature of the evidential demands d i , i = 1, ..., n, the BCP modelling of the CVRPED may degenerate into simpler or well-known optimisation problems.

In particular, if m Θ n is Bayesian, i.e., we are dealing really with a CVRPSD, then we have, for k = 1, . . . , m,

Bel   n i=1 d i n j=0 w k i,j ≤ Q   = P l   n i=1 d i n j=0 w k i,j ≤ Q   , (35)
and the BCP modelling of the CVRPED can be converted into an equivalent optimisation problem, which is the CCP modelling of this CVRPSD, with β in (8) set to β.

In contrast, if m Θ n is categorical and its only focal set is the Cartesian product of n intervals, i.e., we are dealing with a CVRP where each customer demand d i is only known in the form of an interval d i ; d i , then the total demand on any given route is also an interval (its endpoints are obtained by summing the endpoints of the interval demands of the customers on the route) and thus for 26) and ( 27) reduce when β < 1 to the following constraints

any k = 1, . . . , m, Bel Θ ( n i=0 d i n j=0 w k i,j ≤ Q) either equals 1 or equals 0, with the former occurring iff n i=0 d i n j=0 w k i,j ≤ Q, and P l Θ ( n i=0 d i n j=0 w k i,j ≤ Q) either equals 1 or equals 0, with the former occurring iff n i=0 d i n j=0 w k i,j ≤ Q. Then, since n i=0 d i n j=0 w k i,j ≤ Q ⇒ n i=0 d i n j=0 w k i,j ≤ Q, the belief- constraints (
n i=0 d i n j=0 w k i,j ≤ Q, k = 1, . . . , m. (36)
In other words, in the case of interval demands, the BCP modelling amounts to searching the solution which minimises the overall cost of servicing the customers (1) under constraints [START_REF] Holland | Adaptation in natural and artificial systems[END_REF], i.e., assuming the maximum (worst) possible customer demands, and thus it corresponds to the minimax optimisation procedures encountered in robust optimisation [START_REF] Sungur | A robust optimization approach for the capacitated vehicle routing problem with demand uncertainty[END_REF].

If m Θ n is consonant, then we are dealing with a CVRP where uncertainty on customer demand is really of a possibilistic nature, and the BCP modelling may then be connected to fuzzy-based approaches, that is approaches where uncertainty on customer demands is represented by fuzzy sets such as in [START_REF] Teodorovic | The fuzzy set theory approach to the vehicle routing problem when demand at nodes is uncertain[END_REF]. In addition, let us remark that if only marginal knowledge in the form of a consonant MF m Θi having interval focal sets is available about the individual demand of each customer i, i = 1, . . . , n, then, as explained in Section 2.3.3, m Θ n can be obtained by assuming (if justified) independence of the demands, in which case it will yield a tractable situation thanks to Remark 2, whose conditions are then satisfied (the focal sets of m Θ n being in this case Cartesian products of intervals). However, m Θ n may also be derived from these pieces of marginal knowledge by making other assumptions about the demand dependence and in particular by assuming that they are non-interactive [START_REF] Dubois | Random sets and fuzzy interval analysis[END_REF][START_REF] Baudrit | Joint propagation and exploitation of probabilistic and possibilistic information in risk assessment[END_REF] -a more classical independence assumption in the fuzzy setting -in which case the focal sets of m Θ n will also be Cartesian products of intervals but they will also be nested (m Θ n will then be consonant).

If β = β, then constraints ( 27) can be dropped, that is, only constraints (26) need to be evaluated (if constraints [START_REF] Dubois | Decision-making Process: Concepts and Methods, chapter Formal Representations of Uncertainty[END_REF] are satisfied then constraints [START_REF] Gauvin | A branch-cut-and-price algorithm for the vehicle routing problem with stochastic demands[END_REF] are necessarily satisfied due to the relation between the belief and plausibility functions). As a matter of fact, the BCP approach originally introduced in [START_REF] Masri | Belief linear programming[END_REF] is of this form (no constraint based on P l is considered). Most importantly, when β = β and the evidential variables d i , i = 1 . . . , n are independent, the BCP modelling of the CVRPED can be converted into an equivalent optimisation problem, which is the CCP modelling (with β in (8) set to β) of a CVRPSD where customer demands are represented by independent stochastic variables denoted d i , i = 1, . . . , n, with associated probability mass function p i obtained from m Θi := m Θ n ↓Θi as follows: for each focal set A ⊆ Θ i of m Θi , the mass m Θi (A) is transferred to the element θ = max(A). Indeed, with such a definition of p i , it is easy to show that we have, for k = 1, . . . , m,

Bel   n i=1 d i n j=0 w k i,j ≤ Q   = P   n i=1 d i n j=0 w k i,j ≤ Q   . (37)
Let us eventually remark that the case β = 1 > β is the converse of the case β = β in the sense that constraints (26) can be dropped (as they are necessarily satisfied) and only constraints [START_REF] Gauvin | A branch-cut-and-price algorithm for the vehicle routing problem with stochastic demands[END_REF] need then to be evaluated. Moreover, in this case, if the evidential variables d i , i = 1 . . . , n are independent, the BCP modelling of the CVRPED can be converted into an equivalent optimisation problem, which is the CCP modelling (with β in (8) set to β) of a CVRPSD where customer demands are represented by independent stochastic variables denoted d i , i = 1, . . . , n, with associated probability mass function p i obtained from m Θi as follows: for each focal set A ⊆ Θ i of m Θi , the mass m Θi (A) is transferred to the element θ = min(A). Indeed, with such a definition of p i , it is easy to show that we have, for k = 1, . . . , m, P l

  n i=1 d i n j=0 w k i,j ≤ Q   = P   n i=1 d i n j=0 w k i,j ≤ Q   . (38)
3.1.3. Influence of β, β and Q on the CVRPED-BCP optimal solution cost In this section, we study the influence of the parameters β, β and Q, on the optimal solution cost of the CVRPED modelled via BCP (in the remainder of this article, we will simply say CVRPED-BCP instead of CVRPED modelled via BCP).

The following propositions hold:

Proposition 2. The optimal solution cost is non increasing in Q.

Proof. See Appendix B.

Proposition 3. The optimal solution cost is non increasing in β.

Proof. See Appendix C.

Proposition 4. The optimal solution cost is non increasing in β.

Proof. The proof is similar to that of Proposition 3.

Informally, Propositions 2-4 state that if the decision maker is willing to buy vehicles with a higher capacity or to have vehicle capacity exceeded on any route more often, then he will obtain at least as good (at most as costly) solutions.

Influence of customer demand ranking on the CVRPED-BCP optimal solution cost

In this section, we study the influence on the CVRPED-BCP optimal solution cost, of considering uncertain knowledge representing a more pessimistic estimation of the demand of each customer than currently assumed, that is uncertain knowledge telling that the demand of each customer is higher than currently believed.

Specifically, let m Θ n and m Θ n + be two MF representing uncertain knowledge about customer demands, such that evidential variables d i , i = 1, . . . , n, are independent according to both these mass functions. Furthermore, let m Θi := m Θ n ↓Θi and m Θi + := m Θ n ↓Θi + , i = 1, . . . , n. Denote by ĈQ,β,β and Ĉ+ Q,β,β the costs of optimal solutions to the CVRPED-BCP when customer demands are known in the form of m Θ n and m Θ n + , respectively, for some β, β and Q. The following proposition holds:

Proposition 5. m Θi m Θi + , i = 1, . . . , n ⇒ ĈQ,β,β ≤ Ĉ+ Q,β,β .
Proof. See Appendix D.

Informally, Proposition 5 shows that the more pessimistic knowledge is about customer demands, the greater the cost of the optimal solution.

An immediate consequence of this result is:

Corollary 1. Assume that the focal sets of MF m Θi and m Θi + , i = 1, . . . , n, are all intervals and that m Θi + can be obtained from m Θi , i = 1, . . . , n, as follows: for each interval A = A; A such that m Θi (A) > 0, the mass m Θi (A) is transferred to the interval

A + = A; A + a + , with a + ∈ 0; Q -A . Then, ĈQ,β,β ≤ Ĉ+ Q,β,β .
Another immediate consequence is:

Corollary 2. Assume that the focal sets of MF m Θi and m Θi + , i = 1, . . . , n, are all intervals and that m Θi can be obtained from m Θi + , i = 1, . . . , n, as follows: for each interval

A + = A + ; A + such that m Θi + (A + ) > 0, the mass m Θi + (A + ) is transferred to the interval A = A + -a; A + , with a ∈ 0; A + -1 . Then, ĈQ,β,β ≤ Ĉ+ Q,β,β .
Remark 4. In both Corollaries 1 and 2, it is easy to show that m Θi m Θi + , i = 1, . . . , n, which is the reason why these corollaries hold. Note that for Corollary 1, we can also easily show that m Θi m Θi + , i = 1, . . . , n, whereas for Corollary 2, we have m Θi + m Θi , i = 1, . . . , n. This shows that the CVRPED-BCP optimal solution cost will not necessarily be higher if knowledge about customer demand is less specific. As will be seen in the next section, a different conclusion is reached for the recourse model, and specifically a counterpart to Proposition 5, based on rather than , holds.

The CVRPED modelled by a recourse approach

A recourse approach for the CVRPED is proposed in this section. The general model, extending the one recalled for the CVRPSD in Section 2.2.2, is presented in Section 3.2.1. Then, in Section 3.2.2, we detail how uncertainty on recourse actions is obtained in this model and in Section 3.2.3 we provide a method to compute efficiently this latter uncertainty in an important particular case. Similarly to what has been done for the BCP model, we discuss particular cases of our general model in Section 3.2.4 and study the influence of customer demands specificity on the optimal solution cost in Section 3.2.5.

Formalisation

The CVRPED may be addressed using an extension of the other main approach to modelling stochastic programs, that is the recourse approach. We propose to extend the recourse approach to the CVRPED, for the following policy and assumptions studied for the stochastic case in [START_REF] Christiansen | A branch-and-price algorithm for the capacitated vehicle routing problem with stochastic demands[END_REF][START_REF] Gauvin | A branch-cut-and-price algorithm for the vehicle routing problem with stochastic demands[END_REF][START_REF] Laporte | An integer l-shaped algorithm for the capacitated vehicle routing problem with stochastic demands[END_REF][START_REF] Dror | Vehicle routing with stochastic demands: Properties and solution frameworks[END_REF]. Each actual customer demand cannot exceed the vehicle capacity. In addition, when a vehicle arrives at a customer on its planned route, it is loaded with the actual customer demand up to its remaining capacity. If this remaining capacity is sufficient to pick-up the entire customer demand, then the vehicle continues its planned route. However, if it is not sufficient, i.e., there is a failure, then the vehicle returns to the depot, is emptied, goes back to the client to pick-up the remaining customer demand and continues its originally planned route.

Consider a given route R containing N customers and, without lack of generality, that the i-th customer on R is customer i. According to the above setting, a failure cannot occur at the first customer on R. However, it can occur at any other customer on R, and there may even be failure at multiple customers on R (at worst, if the actual demand of each customer is equal to the capacity of the vehicle, failure occurs at each customer except the first one).

Formally, let us introduce a binary variable r i that equals 1 if failure occurs at the i-th customer on R and 0 otherwise (by problem definition r 1 = 0). Then, the possible failure situations that may occur along R may be represented by the vectors (r 2 , r 3 , . . . , r N ) ∈ {0, 1} N -1 . To simplify the exposition, we define the set Ω as the space of binary vectors representing the possible failure situations along R: each failure situation (r 2 , r 3 , . . . , r N ) is then a binary vector belonging to Ω = {0, 1} N -1 . For instance, when R contains only N = 3 customers, we have Ω = {(0, 0) , (1, 0) , (0, 1) , (1, 1)}, where the binary vectors mean that the vehicle needs to perform a round trip to the depot, respectively, "never", "when it reaches the second customer", "when it reaches the third customer", and "when it reaches both the second and third customers".

Furthermore, let g : Ω → R + be a function representing the cost of each failure situation ω ∈ Ω, with ω being the binary vector (r 2 , r 3 , . . . , r N ) representing a failure situation. Since the penalty cost upon failure on customer i is 2c 0,i (a failure implies a return trip to the depot), the cost associated to failure situation ω is

g(ω) = N i=2 r i 2c 0,i . (39)
Let m Ω be a MF representing uncertainty towards the actual failure situation occurring on R -as will be shown in the next section, evidential demands may induce such a MF.

Then, adopting a similar pessimistic attitude as in the recourse approach to belief linear programming [START_REF] Masri | Belief linear programming[END_REF], the upper expected penalty cost C * p (R) of route R may be obtained using ( 14) as follows:

C * p (R) = E * (g, m Ω ). (40)
Accordingly, the upper expected cost C * e (R) of route R may be defined as

C * e (R) = C(R) + C * p (R), (41)
with C(R) the cost (2) of travelling along route R when no failure occurs. The CVRPED under the above recourse policy, may then be modelled using a modified version of the CVRP model of Section 2.1. Specifically, our recourse modelling of the CVRPED aims at

min m k=1 C * e (R k ), (42)
subject to constraints (3) -( 6), with constraints (5) replaced by constraints [START_REF] Chen | Particle swarm optimization for vehicle routing problem with uncertain demand[END_REF].

Evaluating the objective function [START_REF] Peng | Vehicle routing problem with fuzzy demands and the particle swarm optimization solution[END_REF] requires the computation for each route, of the MF m Ω representing uncertainty on the actual failure situation occurring on the route. This is detailed in the next section.

Uncertainty on recourses

Consider again a route R containing N customers. In addition, let us first assume that client demands on N are known without any uncertainty, that is we know that the demand of client i, i = 1, . . . , N , is some value θ i ∈ Θ. Then, it is clear that the above recourse policy amounts to the following definition for the binary failure variables r i :

r i = 1, if q i-1 + θ i > Q, 0, otherwise, ∀i ∈ {2, . . . , N } (43)
where q j , j = 1, . . . , N , denotes the load in the vehicle after serving the j-th customer such that q j = θ 1 for j = 1 and, for j = 2, . . . , N ,

q j = q j-1 + θ j -Q, if q j-1 + θ j > Q, q j-1 + θ j , otherwise. (44)
In other words, when it is known that the demand of the i-th customer is θ i , i = 1, . . . , N , then we have a precise demand vector on R that induces a precise binary failure situation vector (r 2 , r 3 , . . . , r N ), with r i defined by [START_REF] Pichon | Relevance and truthfulness in information correction and fusion[END_REF]. This can be encoded by a function f : Θ N → Ω, s.t. f (θ 1 , . . . , θ N ) = (r 2 , r 3 , . . . , r N ).

For example, suppose we have N = 3 customers on route R, with respective demands θ 1 = 3, θ 2 = 3 and θ 3 = 5, and the vehicle capacity limit is Q = 5. In such case, f (θ 1 , θ 2 , θ 3 ) implies the failure situation vector (r 2 = 1, r 3 = 1). In the general case, client demands on R are known in the form of a MF m X1ו••×X N , which is the marginalisation of m Θ n on the domains of the evidential variables dr 1 , . . . , dr N associated with the N clients on the route, with X i the domain of the evidential variable dr i associated with the i-th client on R. In such case, using [START_REF] Dubois | Random sets and fuzzy interval analysis[END_REF] with f defined in the preceding paragraph, uncertainty on the actual failure situation on R is represented by a MF m Ω defined as

m Ω (B) = f (A)=B m X1ו••×X N (A), ∀B ⊆ Ω. (45)
Computing m Ω defined by ( 45) involves evaluating f (A) for any focal set A of m X1ו••×X N . Evaluating f (A) for some A ⊆ X 1 ו • •×X N , implies |A| (and thus at worst Q N ) times the evaluation of function f at some point (θ 1 , . . . , θ N ) ∈ Θ N . Hence, computing Equation ( 45) is generally intractable. Nonetheless, in a particular case, it is possible to compute f (A), and thus Equation [START_REF] Sengupta | A generalization of some distribution aspects of chance-constrained linear programming[END_REF], with a much more manageable complexity:

Remark 5. When the focal sets of m X1ו••×X N are all Cartesian products of N intervals, i.e., for all A ⊆ X 1 × • • • × X N such that m X1ו••×X N (A) > 0, we have A = A ↓X1 × • • • × A ↓X N
with, for i = 1, . . . , N , A ↓Xi = A i ; A i , it becomes possible to compute f (A) with a complexity of the order 2 N , as detailed in the next section, and thus in this case if m X1ו••×X N has at most c focal sets, the worst-case complexity to evaluate Equation (45) is O(2 N • c).

Interval demands

Let us consider a route R with N customers, such that the demand of customer i, i = 1, . . . , N , is known in the form of an interval of positive integers, which we denote by A i ; A i , where A i ≥ 1 and A i ≤ Q. In this case, the failure situation on R belongs surely to f A

1 ; A 1 × • • • × A N ; A N ⊆ Ω.
Hereafter, we provide a method to efficiently compute f A

1 ; A 1 × • • • × A N ; A N .
In a nutshell, this method consists in generating a rooted binary tree, which represents synthetically yet exhaustively what can possibly happen on R in terms of failure situations. More precisely, this tree is based on the following remark. Suppose a vehicle travelling along R and all that is known about its load when it arrives at the i-th customer on R is that its load belongs to an interval q; q . Let us denote by q i its load after visiting the i-th customer. Then, there are three exclusive cases:

1. either q + A i ≤ Q, hence there will surely be no failure at that customer and all that is known is that q i ∈ q; q + A i ; A i ;

2. or q + A i > Q, hence there will surely be a failure at that customer and all that is known is that q i ∈ q; q + A i ; A i -Q;

3. or q + A i ≤ Q < q + A i , hence it is not sure whether there will be or not a failure at that customer. However, we can be sure that if there is no failure at that customer, i.e., the sum of the actual vehicle load and of the actual customer demand is lower or equal to Q, then it means that q i ∈ q + A i ; Q ; and if there is a failure at that customer, then it means that q i ∈ 1; q + A i -Q .

By applying the above reasoning repeatedly, starting from the first customer and ending at the last customer, whilst accounting for and keeping track of all possibilities and their associated failures (or absence thereof) along the way, one obtains a binary tree. The tree levels are associated to the customers according to their order on R. The nodes at a level i represent the different possibilities in terms of imprecise knowledge about the vehicle load after the i-th customer, and they also store whether these imprecise pieces of knowledge about the load were obtained following a failure or an absence of failure at the i-th customer. The pseudo code of the complete tree induction procedure is provided in Algorithm 1 and illustrated afterwards by Example 4. Input: interval load q; q , Boolean failure variable r, next customer number i Output: final tree T ree 1: create a root node containing interval load q; q and Boolean failure r 2: if i = N + 1 then

3:

return T ree = {root node} 4: else if q + A i ≤ Q then 5:

q L ; q L = q; q + A i ; A i 6:

r L = 0 7:
T ree L = RT ( q L ; q L , r L , i + 1)

8:

attach T ree L as left branch of T ree 9: else if q + A i > Q then 10:

q R ; q R = q; q + A i ; A i -Q T ree R = RT ( q R ; q R , r R , i + 1)

13:

attach T ree R as right branch of T ree 14: else 15:

q L ; q L = q + A i ; Q 16: r L = 0 17:
T ree L = RT ( q L ; q L , r L , i + 1)

18:

attach T ree L as left branch of T ree 19:

q R ; q R = 1; q + A i -Q 20: r R = 1 21: T ree R = RT ( q R ; q R , r R , i + 1) 22:
attach T ree R as right branch of T ree 23: end if Example 4. Let us illustrate Algorithm 1 on a route R where Q = 10 and containing 3 customers, with 4; 8 , 5; 7 and 7; 9 the imprecise demands of the first, second and third customers, respectively. Since the demand of the first customer is 4; 8 , and there is no failure by definition at the first customer, and the customer following the first customer is the second customer, the tree is obtained with RT ( 4; 8 , 0, 2) and is shown in Fig. 3.

For each leaf of the tree, by concatenating in a vector the Boolean failure variable r i at level i = 2, . . . , N , written on the path from the root to the leaf, we obtain the binary failure situation vector (r 2 , r 3 , . . . , r N ). Hence, all the leaves of the tree, yield the subset B ⊆ Ω. For instance, the rightmost leaf of the tree in Fig. 3 yields the failure situation vector (r 2 = 1, r 3 = 1), the leftmost leaf yields (r 2 = 0, r 3 = 1) and the remaining leaf yields (r 2 = 1, r 3 = 0). The tree in this example yields thus the set B = {(1, 0) , (0, 1) (1, 1)}. Proposition 6. The set B built using the tree generated by Algorithm 1 verifies

B = f A 1 ; A 1 × • • • × A N ; A N . Proof. See Appendix E.
The maximum number of leaf nodes in the tree is 2 N -1 . Thus, the algorithmic complexity to obtain set B ⊆ Ω is of the order 2 N .

Particular cases of the recourse modelling of the CVRPED

In this section, some comments are provided on the behaviour of our recourse modelling, especially with respect to some particular evidential demands.

If m Θ n is Bayesian, i.e., we are dealing really with a CVRPSD, then m Ω is Bayesian on any given route R. Hence, the upper expected penalty cost C * p (R) reduces to the classical (probabilistic) expected value of cost function g with respect to the probability mass function m Ω , and thus our recourse modelling of the CVRPED clearly degenerates into the recourse modelling of the aforementioned CVRPSD.

We showed in Section 3.1.2 that the CVRPED-BCP can be converted, when β = β and the evidential variables d i , i = 1 . . . , n, are independent, into an equivalent CVRPSD modelled via chance constrained programming, by transforming each evidential demand represented by MF m Θi into a stochastic demand represented by probability mass function p i obtained from m Θi by transferring the mass m Θi (A) to the element θ = max(A). Example 5 shows that under the recourse approach, this latter transformation cannot be used in general to convert a CVRPED into an equivalent CVRPSD.

Example 5. Suppose we have one available vehicle with capacity limit Q = 14, n = 3 clients with 2; 8 , 3; 8 and 3; 8 the imprecise demands of clients 1, 2 and 3, respectively. The depot is denoted by 0 and the travel cost matrix C = (c i,j ) where i, j ∈ {0, 1, 2, 3} is shown in Table 1. Under the recourse approach, the optimal solution to this CVRPED instance is the route defined by the path (0, 3, 2, 1, 0) (its upper expected cost is 9.3). Using the above-mentioned transformation to transform the evidential demands into stochastic demands, we obtain p 1 (8) = 1, p 2 (8) = 1, and p 3 (8) = 1, and under the recourse approach the optimal solution to this CVRPSD instance is either the route defined by the path (0, 2, 1, 3, 0) or (0, 3, 1, 2, 0) (the expected cost of each one of these routes being 9.2), which are different from the optimum found for the CVRPED.

Furthermore, let us remark that for a given route R containing N clients whose demands are known in the form of a MF m X1ו••×X N , its upper expected

P(m X1ו••×X N ) = {P |∀A ⊆ X 1 × • • • × X N , Bel X1ו••×X N (A) < P (A)}. (46)
However, this measure cannot be determined easily in advance; it can be exhibited once possible recourses on the route and their associated costs are known. Moreover, we note that it is impossible to find a sensible transformation of evidential demands into stochastic demands such that each solution has the same costs in both the evidential and stochastic approaches, as shown by Example 6.

Example 6. Suppose a problem where we have m = 2 available vehicles and n = 5 clients with demands represented by MF m Θ n defined as

m Θ n ( 7 × 6 × 1; 2 × 1 × 1 ) = 1. ( 47
)
Consider the two following possible solutions, containing each two routes:

S 1 = {R 1 1 , R 1 2 }, S 2 = {R 2 1 , R 2 2 }, with R 1 1 = (0, 1, 2, 3, 0), R 1 2 = (0, 4, 5, 0) and R 2 1 = (0, 1, 2, 3, 5, 0), R 2 2 = (0, 4, 0). The upper expected cost of S i , i = 1, 2, is C * E (S i ) := C * E (R i 1 )+C * E (R i 2 )
. Consider now the possible transformations of the evidential demands m Θ n into stochastic demands p Θ n : it seems sensible that p Θ n be chosen in the set of probability distributions compatible with m Θ n , that is in

P(m Θ n ) = {(p Θ n (7, 6, 1, 1, 1) = α, p Θ n (7, 6, 2, 1, 1) = 1 -α)|α ∈ [0, 1]}. ( 48
)
Let C α E (S i ) denote the expected cost of solution S i , i = 1, 2, under stochastic demands represented by probability distribution p Θ n α defined by p Θ n α (7, 6, 1, 1, 1) = 1 -α, p Θ n α (7, 6, 2, 1, 1) = α, for some α ∈ [0, 1]. Assume that customer 5 is further away from the depot than customer 3, that is c 0,5 > c 0,3 . Then, we obtain

C * E (S 1 ) -C α E (S 1 ) = 2c 0,3 • (1 -α) (49)
and

C * E (S 2 ) -C α E (S 2 ) = 2c 0,5 • α + 2c 0,3 • α. ( 50
)
The upper expected cost C * E (S 1 ) of S 1 is thus reached for probability distribution p Θ n 1 , whereas the upper expected cost C * E (S 2 ) of S 2 is reached for probability distribution p Θ n 0 . Hence, for S 1 to have the same costs in both the evidential and stochastic approaches and for S 2 to also have the same costs in both the evidential and stochastic approaches, different transformations of evidential demands into stochastic demands must be used.

The objective function [START_REF] Peng | Vehicle routing problem with fuzzy demands and the particle swarm optimization solution[END_REF] of our recourse model relies on optimising against C * e (R) which is the upper, i.e., worst, expected cost of a route. In particular, if m Θ n is categorical, then C * e (R) is the worst possible cost of R. Hence, optimising ( 42) has some similarities with the protection against the worst case popular in robust optimisation [START_REF] Sungur | A robust optimization approach for the capacitated vehicle routing problem with demand uncertainty[END_REF].

Though, another approach could be followed [START_REF] Troffaes | Decision making under uncertainty using imprecise probabilities[END_REF], where one optimises against the lower, i.e., best, expected cost C *e (R) = C(R) + C *p (R), where C *p (R) is evaluated using ( 13) such that C *p (R) = E * (g, m Ω ). This approach is appropriate when we are interested in the most optimistic solution. More complex decision schemes could also be considered, such as interval dominance [START_REF] Troffaes | Decision making under uncertainty using imprecise probabilities[END_REF], which would rely on C * e (R) and C *e (R) and yield in general a set of optimal (non-dominated) solutions. Borrowing from what is done in label ranking [START_REF] Destercke | Cautious label ranking with label-wise decomposition[END_REF], an interesting study would then be to identify from the set of non-dominated solutions, some parts of routes that would be more relevant (or preferred) to be included in a solution, over some irrelevant ones. This is left for future work.

Finally, another interesting particular case is when m Θ n is obtained from marginal knowledge about individual customer demands in the form of consonant MF m Θi , i = 1, . . . , n, having interval focal sets and the assumption that the demands are independent or non-interactive. As recalled in Section 3.1.2, the focal sets of m Θ n are then Cartesian products of intervals under both assumptions, in which case the recourse modelling of the CVRPED becomes tractable according to Remark 5.

Influence of customer demand specificity on the CVRPED-recourse optimal solution cost

In this section, we study the behaviour of the optimal solution cost of the CVPRED modelled via the recourse approach (in the remainder of this article, we will simply say CVRPED-recourse rather than the CVRPED modelled via the recourse approach), when knowledge specificity about customer demands decreases.

Specifically, let m Θ n and m Θ n be two MF representing uncertain knowledge about customer demands, such that evidential variables d i , i = 1, . . . , n, are independent according to both these mass functions. Furthermore, let m Θi := m Θ n ↓Θi and m Θi := m Θ n ↓Θi , i = 1, . . . , n. Denote by ĈRec and Ĉ

Rec the costs of optimal solutions to the CVRPED-recourse when customer demands are known in the form of m Θ n and m Θ n , respectively.

The following proposition holds:

Proposition 7. m Θi m Θi , i = 1, . . . , n ⇒ ĈRec ≤ Ĉ Rec .
Proof. See Appendix F.

Informally, Proposition 7 shows that the less specific knowledge is about customer demands, the greater the cost of the optimal solution.

An immediate consequence of this result is:

Corollary 3. Assume that for i = 1, . . . , n, m Θi is built from m Θi as follows:

for each A ⊆ Θ i such that m Θi (A) > 0, the mass m Θi (A) is transferred to a subset A such that A ⊆ A ⊆ Θ i . Then, we have ĈRec ≤ Ĉ Rec .
Proposition 7 and Propositions 2-5 provide theoretical properties of the CVRPED solutions obtained under the recourse and the BCP approaches, respectively, when using exact optimisation methods. For now, such methods can not solve large instances of the CVRP, from which the CVRPED derives. As a matter of fact, Section 4 reports solution strategies to these two CVRPED models using a metaheuristic algorithm.

Solving the CVRPED

This section presents a metaheuristic algorithm to solve the two proposed CVRPED models and reports some experimental tests of this algorithm. More precisely, a simulated annealing algorithm for both the BCP and the recourse models is first described in Section 4.1. Next, benchmarks for the CVRPED are presented in Section 4.2. Finally, experimental tests using these benchmarks are provided in Sections 4.3 and 4.4 for the BCP and the recourse models, respectively.

A simulated annealing algorithm for the CVRPED

As for many NP-hard problems like the CVRP, exact solution methods might need a prohibitively large time to solve large instances. When uncertainty is introduced into the CVRP, the problem can easily become even more difficult. Metaheuristics are algorithms built on general (meta) concepts that search the solution space in a reasonable time and thus may be employed as a successful alternative to solve such a combinatorial optimisation problem. Various metaheuristic algorithms exist like: simulated annealing [START_REF] Kirkpatrick | Optimization by simulated annealing[END_REF], genetic algorithms [START_REF] Holland | Adaptation in natural and artificial systems[END_REF], tabu search [START_REF] Glover | Tabu search-part 1[END_REF][START_REF] Glover | Tabu search-part 2[END_REF], etc. In this study, we will use simulated annealing, which is a well-known local search optimisation method. Generally speaking, a local search algorithm moves iteratively from solution to solution in the space of candidate solutions (the search space) by applying local changes, until a satisfying near-optimal solution is found.

Indeed, to try to find the global minimum of the cost function, the simulated annealing moves from solution to solution using either descent (improving) moves or deterioration moves, hoping that these non-improving moves will eventually help the process escape local optima [START_REF] Kirkpatrick | Optimization by simulated annealing[END_REF]. One can say that it starts from a known initial configuration of a system (candidate solution) with a high temperature and then uses general neighbourhood search strategies to explore other candidate solutions by following neighbourhood transitions (moves). For every temperature, the configuration of the system (candidate solution) is rearranged (transformed) by a series of neighbourhood moves. A rearranged configuration becomes the new candidate solution with a probability depending on the current temperature, i.e., the lower the temperature, the lower the probability to accept non-improving moves. The temperature of the system is gradually lowered, and the process continues until reaching the freezing temperature of the system.

Our instantiation of simulated annealing for the CVRPED is provided by Appendix G (see in particular its pseudo-code given by Algorithm 2). The same pseudo-code is used for both the BCP and the recourse approaches. One can find in Algorithm 2 a modelling technique parameter M D that takes the value M D ="BCP" when the CVRPED-BCP is solved. In this case, the initial configuration is generated either randomly or using a first-fit greedy approach3 while respecting the constraints of the BCP model from Section 3.1.1. The neighbourhood configuration(...) routine generates a neighbourhood configuration that respects the CVRPED-BCP constraints, and is based on the following two operators that are applied consecutively on the current configuration C at each iteration. These operators are called fix minimum and replace highest average. They are described below and illustrated using examples in Appendix H.

-Fix minimum: This operator is applied on 80% of the iterations. It is based on selecting and freezing the positions in routes of the five customers, with the shortest distances to their right side customer 4 . This is done by computing distances between each pair of consecutive customers on all routes, including distances to the depot. Accordingly, fix minimum selects the five smallest distances values and fixes their corresponding left side customers. Next, fix minimum selects five random customers that exclude the depot and the customers fixed before, and removes them from their route. Subsequently, every customer removed will be inserted in a random route, while satisfying the problem constraints. The insert position of each customer on the selected route is determined based on the shortest distance separating it from its new left side customer.

-Replace highest average: This neighbourhood operator calculates the average distance separating every customer from its neighbours in a current route configuration. Computing the average distance for a client i reduces to calculating

ci-1,i+ci,i+1 2
, assuming clients i-1, i and i+1 are consecutive in the route 5 . Afterwards, replace highest average selects five customers having the five highest average distances and removes them from their routes. The removed clients are then randomly inserted in the available routes, as long as the problem constraints are respected. Furthermore, every removed customer i is inserted into the route position leading to the smallest average distance that will separate this customer from its new (i -1) th and (i + 1) th neighbours.

If the above operators do not lead to a new neighbourhood configuration that satisfies the CVRPED-BCP constraints, we apply the operators a second time. If the second attempt fails as well, then the configuration C is not modified, i.e., C * = C.

The complexity of an iteration for the BCP model emerges from evaluating the CVRPED-BCP constraints for the neighboring configuration, in particular the belief constraints ( 26) and ( 27), the complexity of which is provided in Section 3.1.1.

We solve the CVRPED-recourse with the same simulated annealing, by setting the modelling technique parameter to M D ="recourse" in Algorithm 2. The initial config(...) method proceeds by generating initial configurations that are subject to the CVRPED-recourse constraints mentioned in Section 3.2.1, using either a first fit greedy approach or randomly. The routine neighbourhood configuration(...) applies three consecutive neighbourhood operators to each iteration: fix minimum, replace highest average and flip route.

-Fix minimum and replace highest average operate similarly as in the BCP case, except that the problem constraints are now the CVRPED-recourse constraints. Recall that the recourse model lifts the capacity constraints, in the sense that any capacity excess (overflow) is addressed by the objective function using recourse decisions. This means that as fix minimum and replace highest average are iteratively applied by the simulated annealing, we may end up with routes holding excessive total demands. Consequently, these routes will systematically fail, while other routes will hold limited total customer demands. Therefore, we incorporate to each of the fix minimum and replace highest average operators, a method that maintains relatively balanced total demands on routes, during the process of moving customers from a route to another. More specifically, before a customer is inserted into a new route, total customer demands on each route yields a probability, indicating if a route is favourable for servicing an additional customer. The probability associated to each route is inversely proportional to the total customer demands on a route, i.e., the smaller the total customer demands is on a route, the more it is probable to choose this route to include an additional customer.

-The operator flip route is applied on 25% of the iterations. It reverses the order of a route if this improves its upper expected cost. Indeed, a route R having the path (0, 1, . . . , N, 0) and its reverse R -1 with the path (0, N, . . . , 1, 0) do not have necessarily the same upper expected penalty cost.

The complexity of an iteration for the recourse model corresponds to evaluating the uncertainty on the recourses of each one of the m routes of a configuration C, the complexity of which is given in Section 3.2.2.

Let us finally emphasize that the evidential approaches proposed in this paper are not limited to using simulated annealing or metaheuristics. Some of the exact methods used for the CVRPSD could be extended to these approaches. This is the case, for instance, of the Column Generation (CG) algorithm proposed in [START_REF] Christiansen | A branch-and-price algorithm for the capacitated vehicle routing problem with stochastic demands[END_REF] for the recourse modelling of the CVRPSD. A CG algorithm relies on a linear program with prohibitively many variables (columns) associated to feasible routes. One could use our evidential approach to evaluate the total cost (base cost plus recourse cost) of each generated column (route), especially when the columns are constructed by Dynamic Programming (DP).

More exactly, each column (route) can be constructed by generating a cycle in a graph of DP states associated to sub-problems satisfying the Bellman principle of optimality. Assuming joint focal sets about customer demands are Cartesian products of intervals, one could define a DP state v, q v , q v for each vertex v ∈ V and for each interval of residual supply [q v , q v ] at v (quantity remaining in a vehicle after servicing clients up to v and performing recourses). The total cost of a route in a given state can be determined, for instance, as the sum of the traversed edges plus the upper expected cost of the recourse actions. In a loose sense, this is similar to the DP approach from [START_REF] Christiansen | A branch-and-price algorithm for the capacitated vehicle routing problem with stochastic demands[END_REF] that constructs a state for each vertex v and for each possible value of the cumulative expected demand (of all the clients in the route up to v) and of the variation of this cumulative demand.

The CVRPED benchmarks

We generated two instance sets CVRPED and CVRPED + , based on the set A of the Augerat test bed for the CVRP [START_REF]Vehicle Routing Data sets[END_REF]. Each instance in these two sets corresponds to an instance in Augerat set A and has the same customer coordinates and capacity limit as this instance.

For each instance of the first CVRPED set, the knowledge on customer demands m Θ n is obtained by assuming that the evidential client demands d i , i = 1, . . . , n of this instance are independent. Moreover, each d i is associated to the mass function m Θi defined by

m Θi ({d det i }) = 0.8, (51)
m Θi ([z i , z i ]) = 0.2, ( 52
)
with d det i the original deterministic demand of client i in the corresponding instance of Augerat set A, and with z i and z i drawn at random in (d det i , Q] and [z i , Q], respectively.

For each instance of the second set CVRPED + , the evidential client demands d i are also assumed to be independent, and their associated mass function is denoted by m Θi + and defined from m Θi as follows:

m Θi + ([d det i , d det i + a + i ]) = 0.8, (53)
m Θi + ([z i , z i ]) = 0.2, (54)
with a + i drawn randomly in [0, z i -d det i -1]. Note that m Θi m Θi + and m Θi m Θi + , i = 1, . . . , n. In the next sections, an experimental study based on the CVRPED and CVRPED + instances6 is presented for the BCP and recourse models solved using the algorithm described in Section 4.1. The programs were written in Java and the experiments were conducted on the 5 nodes of a cluster. The configuration of each node is as follows: 2 processors Intel R Xeon R E5-2630 v3 with 8 cores per processor having a 48GB memory shared between the 2 × 8 cores of the node. Each instance was executed on one core that has a memory of 2.8 GB.

Experimental study for the CVRPED-BCP

Our set of experiments on the CVRPED-BCP involve varying the values β and β involved in the constraints ( 26) and ( 27) for the CVRPED and the CVRPED + instances separately, where for each variation each instance was solved 30 times.

The CVRPED-BCP cost variation based on β and β

In this first part, we show results of our experiments for the CVRPED and the CVRPED + instances in Tables 2 and3, respectively. Indeed, we solved the CVRPED-BCP for two different values that we chose for the pair (β, β), such that β ≥ β, and both values were employed for the CVRPED and the CVRPED + instances, separately. The columns figuring in each of these tables, are explained in the following. The first column is the name of each instance. The first field in this column (l in Table 2 and l + in Table 3), exposes the identification number of an instance and the second field "A" stands for aleatory indicating that the coordinates of the problem graph vertices were generated randomly in the original Augerat set A [START_REF] Augerat | Approche polyédrale du problème de tournées de vehicules[END_REF]. The third field designates the number n of vertices, while the last field provides the number m of vehicles. The "Best cost", "Std. dev." and "Avg. runtime" columns show respectively, the best solution, the standard deviation and the average running time that we obtained for each indicated value of the pair (β, β).

We notice the costs of the best solutions obtained with β = 0.4, β = 0.25 are lower than the costs of the best solutions obtained with β = 0.2, β = 0.15 in Table 2 as well as in Table 3, that is, the most constraining pair (β, β) induces the worst costs, as can be expected from Propositions 3 and 4. This shows that while our solving algorithm is not an exact optimisation method, it does exhibit experimentally a sound behaviour with respect to parameters β and β.

The CVRPED-BCP cost variation based on client demand ranking

This section compares the BCP results on the CVRPED instances with the BCP results on the CVRPED + instances. Specifically, Table 4 best costs from Table 2 (CVRPED instances) with the bests costs from Table 3 (CVRPED+ instances), for the same instance id. Recall that for each client i in an l instance, its MF m Θi is at least as small as the associated MF to client i in the l + instance, i.e., m Θi m Θi + , i = 1, . . . , n. Proposition 5 (and more specifically Corollary 1) predicted an increase in the cost of an optimal solution to the CVRPED-BCP when knowledge about clients demands is more pessimistic. We can observe this behaviour in the results presented in Table 4: for each pair (β, β) the best cost obtained with the CVRPED + instances is higher than the one obtained with the CVRPED instances. This constitutes another experimental validation of the behaviour of our algorithm.

compares the

Experimental study for the CVRPED-recourse

In the experiments conducted for the CVRPED-recourse, we used the same generated CVRPED and CVRPED + instances used for the CVRPED-BCP experiments. Our results are reported in Table 5.

The columns "Instance id l" and "Instance id l + " in this table represent the CVRPED and the CVRPED + instances id, respectively. Each one of these instances was solved 30 times and the best, average and standard deviation of the costs along with the average running times are reported in the respective columns "Best cost", "Avg cost", "Stand. dev." and "Avg. runtime" for the CVRPED and the CVRPED + instances, separately. In the "Penalty cost" column for the CVRPED instances (respectively the "Penalty cost" column for the CVRPED + instances), the contribution of the expected penalty costs to the overall costs of the best solutions to the CVRPED instances (respectively the CVRPED + instances) is provided as percentages. In the case of the CVRPED instances, it varies between 16% to 25%. As for the CVRPED + instances, it varies between 11% and 23%.

Recall that for each client i in an l instance, its MF m Θi is at least as specific as the associated MF to client i in the l + instance, i.e., m Θi m Θi + , i = 1, . . . , n. As expected from Proposition 7 (and more specifically from Corollary 3), best costs obtained with the CVRPED + instances are higher than those obtained with the CVRPED instances, which shows that our algorithm for the recourse model exhibits experimentally also a sound behaviour.

Conclusions

In this article, we proposed to represent uncertainty on customer demands in the capacitated vehicle routing problem via the theory of evidence. We tackled this problem by generalising the most popular approaches to stochastic programming: chance constrained programming and stochastic programming with recourse. We obtained belief constrained programming and evidential recourse approaches. We studied the optimal solution cost behaviour with respect to the model parameters and customer demand ranking in the case of the belief constrained programming model, and with respect to customer demand specificity in the case of the recourse model. In addition, by considering particular cases of evidential demands, we were able to connect our models not only to stochastic programming but also to robust optimisation. In the last part of this article, we solved both models by a simulated annealing metaheuristic algorithm that uses a combination of operators that aim at minimising the objective function of the problem. We reported the results of our experiments on instances of this difficult optimisation problem. Our experiments showed that our algorithm behave accordingly to the theoretical results studied in this paper.

Future work will include i) comparing our evidential models to the other models, and particularly the stochastic ones, using historical data on customer demands in order to show empirically the advantages of our evidential models; ii) extending to the evidential framework other stochastic variations of the CVRP, such as the CVRP with stochastic customers [START_REF] Gendreau | Stochastic vehicle routing[END_REF]; iii) extending our evidential models to the case of incomplete knowledge about the dependency between the evidential variables [START_REF] Destercke | Idempotent conjunctive combination of belief functions: Extending the minimum rule of possibility theory[END_REF]; iv) performing a sensitivity analysis that would allow us to identify certain "key" customers, such that better knowledge about their demands leads to better solutions in each one of these models; and v) considering more general uncertainty frameworks than evidence theory to model uncertainty on customer demands. Lower previsions [START_REF] Walley | Statistical Reasoning with Imprecise Probabilities[END_REF], whose interest to model uncertainty about constraint parameters in optimisation problems has been investigated in [START_REF] Quaeghebeur | Constrained optimization problems under uncertainty with coherent lower previsions[END_REF], may be such a framework. In particular, in the case of independent demands, 2-monotone lower probabilities would offer more generality while being still tractable, thanks to the results of [START_REF] Destercke | Independence and 2-monotonicity: Nice to have, hard to keep[END_REF].

-Or L ω i + A i+1 ≤ Q < L ω i + A i+1 , in which case the failure situation ω i at the i-th customer will induce a failure situation ω i+1 L ∈ B i+1 at the i + 1-th customer such that ω i+1 L = (r i 1 , . . . , r i i , 0) and L ω i+1 L = L ω i +A i+1 ; Q since for q i +θ i+1 ≤ Q we have q i+1 = q i +θ i+1 . It will also induce a failure situation ω i+1 R ∈ B i+1 at the i + 1-th customer such that ω i+1 R = (r i 1 , . . . , r i i , 1) and L ω i+1 R = 1; L ω i + A i+1 -Q since for q i + θ i+1 > Q we have q i+1 = q i + θ i+1 -Q. In addition,

L ω i + A i+1 ≤ Q < L ω i + A i+1 is equivalent to L t i + A i+1 ≤ Q < L t i + A i+1
, in which case the leaf of T ree i associated to t i will induce according to Algorithm 1 the leaf of T ree i+1 with associated vector Proof. Let C * p (R) and C * p (R) denote the upper expected penalty costs of some route R, under m Ω and m Ω (denoted for simplicity m and m in this proof), respectively.

We have where we used the fact that S is stochastic so that max for iter = 0 to tot iter do until (T == f reez)

C * p (R) = B⊆Ω m (

  = 1, j = 1, . . . , n, i.e., exactly one vehicle leaves client j. Constraints (5) and (4) imply n i=1

Figure 1 :

 1 Figure 1: A simple CVRP

Figure 2 :

 2 Figure 2: Evaluation of constraints (26) and (27) on the route (0, 4, 1, 2, 0) (route circled in red).

Figure 3 :Algorithm 1

 31 Figure 3: Recourse tree constructed for Example 4

== 1 ;

 1 LT t i + A i+1 ; Q . It will also induce the leaf of T ree i+1 with associated vectort i+1 R = ω i+1 R and interval LT t i+1 R LT t i + A i+1 -Q . Appendix F. Proof of Proposition 7The proof of Proposition 7 relies on the following lemma. Lemma 1. Let m Ω and m Ω be two MF representing uncertainty about the recourses on a given route R, such that m Ω m Ω . Let C * e (R) and C * e (R) denote the upper expected costs of R under m Ω and m Ω , respectively. We have C * e (R) ≤ C * e (R).

4 )

 4 A, B) = 0, ∀A ⊆ B, we can replace the condition of the second sum from A ⊆ Ω to A ⊆ B:In addition, for any A, B ⊆ Ω such that A ⊆ B,

Algorithm 2 1 : 3 :

 213 for any B ⊆ Ω. Using C * p (R) ≥ C * p (R) we obtain C * p (R) + C(R) ≥ C * p (R) + C(R) , which means C * e (R) ≥ C * e (R) .Proposition 7 may then be proved as follows.Let R denote a route containing N clients. Without lack of generality, assume that the i-th client on R is the client i. Let m Ω denote the MF representing uncertainty about recourses on R when the demand of client i, i = 1, . . . , N is known in the form of MF m Θi , and let m Ω denote the MF representing uncertainty about recourses on R when the demand of client i is known in the form of MF m Θi .Using a similar proof to that of [25, Proposition 3] (with operation * replaced by function f defined in Section 3.2.2), it is direct to show that m Θi m Θi , i = 1, . . . , n ⇒ m Ω m Ω . From Lemma 1, we obtain then C * e (R) ≤ C * e (R). Considering that the optimal solution with mass functions m Θi consists of a set S of routes {R 1 , . . . , R m }, we have thenC * e (R k ) ≥ C * e (R k ) for each k ∈ {1, . . . ,m}, Simulated annealing algorithm Input: initial temperature T , temperature reduction multiplier κ, freezing temperature f reez, total number of iterations tot iter, total number of trials tot tr, modelling technique M D (BCP or recourse) Output: Best solution ever visited Best C Best cost = ∞ 2: for tr = 0 to tot tr do if tr == 0 then 4: C = initial config(greedy, M D)

23 :

 23 else if rnd ≤ e -∆ cost T then rnd is a random number in [0, 1]

Table 1 :

 1 Travel cost matrix C e (R) is necessarily reached for some probability measure P X1ו••×X N belonging to the set P(m X1ו••×X N ) of probability measures compatible with m X1ו••×X N and defined by

		0	1	2	3
	0 +∞	1	1.1	3
	1	1	+∞	1	2.1
	2 1.1	1	+∞ 2.1
	3	3	2.1	2.1 +∞
	cost C

*

Table 2 :

 2 Results of the simulated annealing algorithm for the CVRPED-BCP using the CVRPED instances

	Instance l-A-nn-mm :	β = 0.4, β = 0.25	β = 0.2, β = 0.15
	l instance id,	Best	Std.	Avg.	Best	Std.	Avg.
	n clients, m vehicles	cost	dev.	runtime	cost	dev.	runtime
	1-A-n32-m12	1418,3	3,7	3881s.	1850,9	5,3	3733s.
	2-A-n33-m13	1055,3	0	4199s.	1491,6	17,5	4496s.
	3-A-n33-m13	1073,1	6	4495s.	1480,2	0,6	4549s.
	4-A-n34-m14	1320,6	0,1	3818s.	1749,1	0	3852s.
	5-A-n36-m12	1318,9	2,7	5316s.	1718,6	0,2	4914s.
	6-A-n37-m13	1110,6	5	4918s.	1358,8	34,5	6158s.
	7-A-n37-m14	1597,9	0,5	4135s.	2113,9	2,8	3756s.
	8-A-n38-m13	1154,5	0,9	5041s.	1571,1	5,1	5002s.
	9-A-n39-m15	1485	8,1	4654s.	1944,8	0,9	4622s.
	10-A-n39-m14	1403,9	8,6	4894s.	1906,9	0,2	5108s.
	11-A-n44-m17	1693,4	10,1	4956s.	2158,2	1,2	4951s.
	12-A-n45-m17	1660,3	0,1	5093s.	2184,8	5,1	5169s.
	13-A-n45-m18	1890,1	5,7	4991s.	2573,2	0,7	5211s.
	14-A-n46-m17	1552,2	5,4	5323s.	1980,3	38	5707s.
	15-A-n48-m17	1872,4	10,8	5996s.	2397,5	3,6	6395s.
	16-A-n53-m19	1806,1	11,9	7405s.	2358,2	10	6928s.
	17-A-n54-m19	2052,6	13,8	7578s.	2636,8	60,8	6747s.
	18-A-n55-m22	1755,3	9,5	6310s.	2352,6	9,8	6172s.
	19-A-n60-m22	2263,9	17	8169s.	2969,1	34,8	7449s.
	20-A-n61-m24	1793,8	9,9	6965s.	2345	42,3	7319s.
	21-A-n62-m22	2532,3	19,1	8212s.	3207,2	32,2	7752s.
	22-A-n63-m24	2946,9	14,6	7164s.	3918,9	22	7216s.
	23-A-n63-m25	2179	8,9	6969s.	2881,1	6,9	7238s.
	24-A-n64-m23	2629,1	16,8	7979s.	3261,5	13,6	7848s.
	25-A-n65-m25	2214,7	16,4	7537s.	3070,9	6	7601s.
	26-A-n69-m25	2056,5	11,1	8876s.	2668,1	52,9	8377s.
	27-A-n80-m27	3507,2	21,5	11110s.	4524,9	21,5	9751s.

Table 4 :

 4 Results of the simulated annealing algorithm for the CVRPED-BCP for the CVRPED and CVRPED + instances

		CVRPED instances		CVRPED + instances
	Instance	Best cost	Best cost	Instance	Best cost	Best cost
	id l	β = 0.4, β = 0.25 β = 0.2, β = 0.15 id l + β = 0.4, β = 0.25 β = 0.2, β = 0.15
	1	1418,3	1850,9	1 +	1830,8	2225,4
	2	1055,3	1491,6	2 +	1428,8	1676,9
	3	1073,1	1480,2	3 +	1196	1502
	4	1320,6	1749,1	4 +	1596	1993
	5	1318,9	1718,6	5 +	1755,3	2145,7
	6	1110,6	1358,8	6 +	1379,2	1761,2
	7	1597,9	2113,9	7 +	1957	2542,6
	8	1154,5	1571,1	8 +	1437,4	1846,4
	9	1485	1944,8	9 +	1915,5	2203,5
	10	1403,9	1906,9	10 +	1759	2148,1
	11	1693,4	2158,2	11 +	2234,2	2796,6
	12	1660,3	2184,8	12 +	2165,7	2690,8
	13	1890,1	2573,2	13 +	2287,7	3099,4
	14	1552,2	1980,3	14 +	1950,4	2690,1
	15	1872,4	2397,5	15 +	2359,8	2956,3
	16	1806,1	2358,2	16 +	2411,2	3199,8
	17	2052,6	2636,8	17 +	2591	3165,7
	18	1755,3	2352,6	18 +	2237,1	2803,1
	19	2263,9	2969,1	19 +	2744,8	3415,5
	20	1793,8	2345	20 +	2313,4	3059,2
	21	2532,3	3207,2	21 +	3217,7	4291
	22	2946,9	3918,9	22 +	3833	4942,1
	23	2179	2881,1	23 +	2755	3638,6
	24	2629,1	3261,5	24 +	3311,2	4123,1
	25	2214,7	3070,9	25 +	2748,1	3509,1
	26	2056,5	2668,1	26 +	2573,4	3300,5
	27	3507,2	4524,9	27 +	4995,8	5986,3

Table 5 :

 5 Results of the simulated annealing algorithm for the CVRPED-recourse for the CVRPED and CVRPED + instances CVRPED instances CVRPED + instances Instance Best Penalty Avg Stand. Avg. Instance Best Penalty Avg Stand. Avg.

	id l	cost	cost	cost dev. runtime id l +	cost	cost	cost dev. runtime
	1	1750,3 16,8% 1783,9 16,1 1958s.	1 +	2252,6 18,3% 2283,5 13,2 1272s.
	2	1327,5 16,2% 1353,2 13,6 1704s.	2 +	1650,6 17,7% 1676	9,6 1329s.

  Best cost < Best cost ) then

	30: if (T 31: Best C = T Best C
	32:	Best cost = T Best cost
	33:	end if
	34: end for

Designing physical systems in the engineering field using optimisation techniques, so design costs are minimized, while the system performance is fulfilled[START_REF]Reliability Based Design Optimization: Formulations and Methodologies[END_REF].

A blind algorithm that inserts clients in routes in turn: each client is inserted in the first route that can serve it.

Given the pair of customer < i -1, i >, the right side customer is the i-th customer.

The notation c i-1,i indicates the travel cost between i -1 and i, as defined in Section 2.1, which in our algorithm is assumed to be the euclidean distance separating customers.

Our data sets can be found on the web site of the LGI2A laboratory[START_REF] Helal | CVRPED benchmarks[END_REF].

Acknowledgment

The authors thank the anonymous referees for their valuable comments that helped to improve this paper.

The proof is similar to show that P l

That the implication in Equation ( 22) is strict is indicated by the following counter-example. Let X = {x 1 , . . . , x 8 }, Q = 5 and m X 1 and m X 2 be two mass functions defined as m X 1 ({x 3 , x 4 , x 5 }) = 0.8, m X 1 ({x 1 , x 3 , x 4 }) = 0.2, m X 2 ({x 2 , x 3 , x 5 }) = 0.7, m X 2 ({x 6 , x 8 }) = 0.3.

We have

However, to have m X 1 m X 2 , it must be the case that the mass m X 2 ({x 2 , x 3 , x 5 }) = 0.7 can be shared among the focal sets of m X 1 that are smaller (according to ≤ lo ) than {x 2 , x 3 , x 5 }, which is impossible since m X 1 has only one focal set ({x 1 , x 3 , x 4 }) that is smaller than {x 2 , x 3 , x 5 } and this focal set has mass 0.2.

Appendix B. Proof of Proposition 2

Let us consider a set

such that it is not known whether this set respects the belief-constraints ( 26) and ( 27), but it is known that it respects all the other constraints of the CVRPED-BCP.

It is clear that for any β and β, as Q increases (starting from 1), it reaches necessarily a value at which constraints [START_REF] Dubois | Decision-making Process: Concepts and Methods, chapter Formal Representations of Uncertainty[END_REF] and [START_REF] Gauvin | A branch-cut-and-price algorithm for the vehicle routing problem with stochastic demands[END_REF] are satisfied, and thus at which C becomes a solution to the CVRPED-BCP. Hence, for Q ≥ Q, the set of solutions to the CVRPED-BCP associated with value Q is included in or equal to the set of solutions to the CVRPED-BCP associated with value Q .

Appendix C. Proof of Proposition 3

Let us consider a set C = {R 1 , . . . , R m } composed of m routes R k , k = 1, ..., m, such that it is not known whether this set respects the belief-constraints [START_REF] Dubois | Decision-making Process: Concepts and Methods, chapter Formal Representations of Uncertainty[END_REF], but it is known that it respects all the other constraints of the CVRPED-BCP, in particular constraints [START_REF] Gauvin | A branch-cut-and-price algorithm for the vehicle routing problem with stochastic demands[END_REF].

It is clear that for any Q, as β increases from β to 1, it reaches necessarily a value at which constraints [START_REF] Dubois | Decision-making Process: Concepts and Methods, chapter Formal Representations of Uncertainty[END_REF] are satisfied, and thus at which C becomes a solution to the CVRPED-BCP. Hence, for β ≥ β, the set of solutions to the CVRPED-BCP associated with value β is included in or equal to the set of solutions to the CVRPED-BCP associated with value β .

Appendix D. Proof of Proposition 5

Let R denote a route containing N clients. Without lack of generality, assume that the i-th client on R is the client i. Let m Θ R denote the MF defined on Θ R := {1, 2, . . . , N • Q} and representing the sum of the customer demands on R when the demand of client i is known in the form of MF m Θi , and let m Θ R + denote the MF representing the sum of the customer demands on R when the demand of client i is known in the form of MF m Θi + . Using a similar proof to that of [START_REF] Dubois | Random sets and fuzzy interval analysis[END_REF]Proposition 3] (with operation * instanciated to addition +, specialisation replaced by ranking and set inclusion ⊆ replaced by lattice ordering

Let Bel and Bel + (resp. P l and P l + ) denote the belief functions (resp. plausibility functions) associated to m Θ R and m Θ R + , respectively. From Proposition 1, we have then

The proposition follows from the fact that Equations (D.1) and (D.2) hold for any route. Appendix E. Proof of Proposition 6

. . , N , denote the set of possible failure situations that may occur at the i-th customer on route R, i.e.,

with A := A ; A , = 1, . . . , i. Let h i be the function from Θ i to N * defined by h i (θ 1 , . . . , θ i ) = q i , with q i defined by [START_REF] Quaeghebeur | Constrained optimization problems under uncertainty with coherent lower previsions[END_REF]. In other words, h i provides the load in the vehicle after serving the i-th customer given that customer demands are (θ 1 , . . . , θ i ).

Remark that any ω i ∈ B i may be obtained by several vectors (θ 1 , . . . , θ

As a consequence, when it is known that the failure situation ω i has occurred at the i-th customer, then the load in the vehicle after serving the i-th customer is known only in the form of a set L ω i such that

(E.2) Consider the tree built according to Algorithm 1 and remove all its nodes below level i. Call T ree i the resulting tree. Then, for a given leaf of T ree i , by concatenating in a vector the Boolean failure variable r at level , = 2, . . . , i, written on the path from the root to the leaf, we obtain the binary failure situation vector t i = (r 2 , r 3 , . . . , r i ) ∈ Ω i and this leaf contains also an interval LT t i of integers representing imprecise knowledge about the vehicle load after serving the i-th customer when t i has occurred. Besides, all the leaves of T ree i yield the subset BT i ⊆ Ω i .

We will now show by induction that for i = 2, . . . , N , we have: B i = BT i and ∀ω i ∈ B i , L ω i = LT t i for t i ∈ BT i such that t i = ω i . Note that from the definition of the addition of two intervals of integers I 1 and I 2 , i.e.,

• Suppose that for i < N we have: B i = BT i and ∀ω i ∈ B i , L ω i = LT t i for t i ∈ BT i such that t i = ω i . Let us show that it holds for i + 1.

From the preceding assumption, we have ∀ω i = (r i 1 , . . . , r i i ) ∈ B i that L ω i is the interval LT t i , i.e., L ω i = L ω i ; L ω i = LT t i ; LT t i for t i ∈ BT i such that t i = ω i . In addition, we have ∀ω i = (r i 1 , . . . , r i i ) ∈ B i : -Either L ω i + A i+1 ≤ Q, in which case the failure situation ω i at the i-th customer will induce a failure situation ω i+1 ∈ B i+1 at the i + 1th customer such that ω i+1 = (r i 1 , . . . , r i i , 0) and

which case the leaf of T ree i associated to t i will induce according to Algorithm 1 the leaf of T ree i+1 with associated vector t i+1 = ω i+1 and interval LT t i+1 = LT t i + A i+1 .

-Or L ω i + A i+1 > Q, in which case the failure situation ω i at the i-th customer will induce a failure situation ω i+1 ∈ B i+1 at the i + 1-th customer such that ω i+1 = (r i 1 , . . . , r i i , 1) and

which case the leaf of T ree i associated to t i will induce according to Algorithm 1 the leaf of T ree i+1 with associated vector t i+1 = ω i+1 and interval LT t i+1 = LT t i + A i+1 -Q.

Appendix G. The simulated annealing algorithm for the CVRPED

The pseudo-code of our simulated annealing algorithm is provided by Algorithm 2. It starts by generating an initial configuration (candidate solution) C using the initial config(...) routine, when the initial temperature of the system T is at its highest value. Afterwards, T is progressively decreased until reaching the freezing temperature f reez, while a sequence of iterations tot iter are performed for each T . Throughout each iteration iter, a neighbourhood configuration C * of the current configuration C is generated, and the variation in the cost ∆ cost is computed. In other words, each configuration represents an intermediate solution that has a different cost which is computed using the cost method, and ∆ cost is equal to the difference between the new cost of the neighbourhood configuration C * cost and the current cost of the current configuration C cost . If the cost decreases then the move to the new cost is accepted (lines 16 -18).

However, if ∆ cost is positive then the move is accepted or rejected with a probability that equals e -∆ cost T . Effectively, the probability of accepting inferior solutions is a function of the temperature T and the change in cost ∆ cost . We repeat this whole process for a total number of trials tot tr and the algorithm finally returns the best configuration ever visited.

The set of parameters controlling Algorithm 2 were experimentally determined using Augerat set A instances of the CVRP [START_REF]Vehicle Routing Data sets[END_REF], in which vertices coordinates were randomly constructed [START_REF] Augerat | Approche polyédrale du problème de tournées de vehicules[END_REF]. Specifically, the initial temperature T was set to 5000 and was decreased by a temperature reduction multiplier κ that was set to 0.82 until reaching a freezing temperature f reez that equals 1. The total number of iterations tot iter was regulated to 30000, while the total number of trials of the algorithm tot tr was determined to be 5. The results with our algorithm varied between 1% and 12% from the optimal solutions of the CVRP, with an average running time under 30 minutes, for all instances. This algorithm is an adaptation of the algorithm introduced in [START_REF] Harmanani | A simulated annealing algorithm for the capacitated vehicle routing problem[END_REF] for the CVRP.

Let us remark that a configuration in Algorithm 2 is a set of routes that can be generated either by the initial config(...) or the neighbourhood configuration(...) routines. Besides, the cost(...) routine evaluates the objective value of the configuration. All these routines depend on a "modelling technique parameter" M D that specifies whether we are solving the CVPRED-BCP or the CVRPED-recourse model. In particular, if M D = "BCP the cost(...) routine evaluates the objective value of the configuration in the BCP model. The objective function is thus the (classical) total travelled distance of the routes (1). If M D="recourse", the cost(...) routine corresponds to using the recourse objective function, that aims at minimising the total upper expected cost [START_REF] Peng | Vehicle routing problem with fuzzy demands and the particle swarm optimization solution[END_REF]. The descriptions of the routines initial config(...) and neighbourhood configuration(...) given the value of parameter M D, are provided in Section 4.1.

Appendix H. Examples for the neighbourhood operators Fix minimum and Replace highest average Example 7. (Fix minimum) Suppose configuration C consists of the set of three routes C = {(0, 3, 6, 10, 0) , (0, 1, 5, 8, 4, 9, 7, 0) , (0, 2, 0)}. Assume that the smallest distances between consecutive clients are those between clients < 3, 6 >, < 6, 10 >, < 1, 5 >, < 4, 9 > and < 7, 0 >. This means that customers 3, 6, 1, 4 and 7 cannot be removed from their routes by the fix minimum operator. Consequently, fix minimum selects five random customers excluding 3, 6, 1, 4, 7 and the depot. For instance customer 5 is selected and removed from the second route in C and inserted randomly in one of the three available routes in C, while respecting all problem constraints. After selecting the new route for client 5, it is inserted at the position with the resulting smallest distance to client 5. We repeat the same process to move the four other random customers which in this example cannot be other than customers 2, 5, 8, 9 and 10.

Example 8. (Replace highest average) Suppose a configuration C that consists of the set of routes C = {(0, 1, 3, 8, 0) , (0, 2, 5, 4, 9, 10, 0) , (0, 6, 7, 0)}. Suppose 1, 8, 5, 9 and 7 are the clients having the five highest average distances (separating each one of these clients from its neighbours). Then, these clients are removed from their routes, and we will have C = {(0, 3, 0) , (0, 2, 4, 10, 0) , (0, 6, 0)}. Afterwards, each removed client is inserted randomly in one of the available routes. The position where to insert a customer is chosen, such that: i) the problem constraints are respected; and ii) the new position of that customer on the chosen route has the smallest average distance, if compared to all other possible positions of this client on the chosen route. For instance, suppose the first route in C was chosen randomly for client 1. We know that inserting client 1 on that route does not violate the belief-constraints, and it can be inserted either before client 3 or right after client 3. Suppose also that inserting client 1 right after client 3 has a smallest average distance, than if client 1 was inserted right before client 3. Then, client 1 is inserted right after client 3. This same process is repeated for the remaining clients 8, 5, 9 and 7.