# Robust Optimisation Approach for Vehicle Routing Problems with Uncertainty

Authors: Liang Sun; Bing Wang
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

We formulated a solution procedure for vehicle routing problems with uncertainty (VRPU for short) with regard to future demand and transportation cost. Unlike E-SDROA (expectation semideviation robust optimisation approach) for solving the proposed problem, the formulation focuses on robust optimisation considering situations possibly related to bidding and capital budgets. Besides, numerical experiments showed significant increments in the robustness of the solutions without much loss in solution quality. The differences and similarities of the robust optimisation model and existing robust optimisation approaches were also compared.


---

## Body

## 1. Introduction

Nowadays, vehicle routing problem (VRP for short) is a crucial and critical issue in industrial and systems engineering [1, 2]. The vehicle routing problem involves routing a fleet of vehicles from a depot to service a set of customers. If one or both of the demand and edge costs (distance, transportation cost, travel time, etc.) are uncertain, the variant vehicle routing problem becomes a vehicle routing problem with uncertainty (VRPU for short). VRPU is faced daily by courier services, local trucking companies, demand-response transportation services, and so forth. From the perspective of managers, the expected total transportation cost in failure scenarios given the coexistence of failure and successful scenarios results in a number of practical contexts where the routes followed by different drivers remain almost the same from day to day.The sum of all demands in such a scenario exceeds the capacities that the vehicles can serve by assuming that the demand is known before vehicles start their routes: such a scenario is considered as a “failure.” In contrast, if vehicles in the depot satisfy the demands of all customers when it is assumed that the demands are known before vehicles start their routes, such scenario is considered as a successful one.Contrary to existing robust optimisation models for VRPU, we summarise the contributions of this research as follows.(1)
Supposing the coexistence of failure and successful scenarios, we proposed a robust optimisation approach to minimise the sum of the expected total transportation cost in all failure scenarios and its variation multiplied by a weighted coefficient on the condition of coexistence of failure and successful scenarios.(2)
Unlike robustness measure of E-SDROA, our approach can deal with some situations involving bidding or capital budget decisions.(3)
Solving for the robust optimal solution of our approach for VRPU is no more difficult than solving a single deterministic SDVRP (split delivery vehicle routing problem) while satisfying all demands in a given bounded uncertainty set.The rest of this paper is organised as follows: Section2 reviews the relevant literature; Section 3 modifies the original SDVRP statement to incorporate the demand and transportation cost uncertainties [3–5]. Besides, a robust optimisation formulation for VRPU in demand and transportation cost is constructed and a solution method for our robust optimisation formulation is proposed. In Section 4, theoretical analysis shows the relationship between our approach and E-SDROA for the proposed problem. The computational results of some instances in Section 5 verified the effectiveness of our robust optimisation approach. Conclusions are drawn and further research topics are outlined in Section 6. To understand better our robust optimisation approach, a brief introduction to E-SDROA for the proposed problem is described in the Appendix.


## 2. The literature Reviewed

Stochastic optimisation approaches for solving VRPU were designed to optimise the expected value of all possible scenarios [6–8]. However, the approaches lead to large variations in the objective values for different scenarios even if the expected value is optimal. To compensate for the limitations of stochastic optimisation approaches for VRPU, the robustness concept has recently been introduced. The robust optimisation approaches for VRPU have many practical advantages over estimated probability distributions in a stochastic optimisation approach to the problem [9, 10]. Firstly, in many cases, it is easier to define the uncertainty set than to estimate the probability distributions. Secondly, under certain conditions, the robust approach does not significantly increase the complexity of the problem.However, robust optimisation approaches available for VRPU fail to solve situations involving either bidding or capital budget decisions [9, 11–13]. Meanwhile, robust optimisation approaches available for VRPU are doubted in their application to service industries in recent years (e.g., each customer is served by exactly one vehicle; individual demands larger than the vehicle capacity are not allowed).Generally speaking, there are two types of robust optimisation approach used for VRPU.(1) Robust optimisation based on the definition of model robustness [14]: this approach mainly focuses on the feasibility of the optimal solution from a set of scenarios. Sungur et al. introduce a robust optimisation approach to solving the VRP with demand uncertainty [9]. The approach yielded routes minimising transportation costs while satisfying all demands in a given bounded uncertainty set. They solved the problem directly by using an off-the-shelf mixed integer programming solver. Their results indicated that the robust optimisation approach is attractive as it produced a much more robust solution with only a small penalty in the objective value.Lee et al. investigated a vehicle routing problem with deadlines, wherein the objective is to satisfy the requirements of a given number of customers with minimum travel distances while regarding both the customers’ deadlines and vehicle capacities [13]. Gounaris et al. derived the robust optimisation counterparts of several deterministic CVRP formulations. At the same time, they developed robust rounded-capacity inequalities for two broad classes of demand supports and showed how they were able to be efficiently separated [12].Yao et al. designed a robust linear programming model on the basis of a robust optimisation approach wherein hard constraints are guaranteed within an appropriate uncertainty set [15]. Erera et al. created a robust optimisation framework for dynamic empty repositioning problems using time-space networks [16]. They derived necessary and sufficient conditions for the flow to be robust for three types of allowable recovery actions. Chung et al. formulated a robust network design problem as a tractable linear programming model [17, 18]. They illustrated its robustness by comparing the performance of its solution with the nominal solution of the corresponding deterministic model.Najafi et al. presented a robust approach for a multiobjective, multimodal, multicommodity, and multiperiod stochastic model to manage the logistics of both commodities and injured personnel in response to an earthquake. The model was used to ensure that the distribution plan performed well under various chaotic situations arising in the aftermath of an earthquake [19]. Agra et al. proposed two new formulations for robust VRP. The first extended the well-known resource inequalities by using adjustable robust optimisation. Another generalised a path inequalities formulation to cater for the uncertain context [20].(2) A robust optimisation approach that can measure the trade-off between solution and model robustness [14]: the objective function of the model was a utility function that embodied a trade-off between optimisation objective and variability therein [14, 21]. List et al. established a formulation and a solution procedure for fleet sizing under uncertainty in future demand and operating conditions [10]. Their formulation concentrated on robust optimisation, using a partial moment measure of risk.Naumann et al. proposed a robust optimisation approach to vehicle scheduling in public bus transport [22]. In their optimisation, the approach used typical disruption scenarios to minimise the expected sum of planned costs and costs caused by disruptions. To incorporate the stochastic disturbances of daily passenger demand that occurred in actual operations, Yan and Yang built an E-SDROA for routing buses with stochastic demand. This model combined the concept of semivariance devised by Markowitz, the robust optimisation model of Mulvey and Ruszczyński, and the actual operating characteristics of a bus company [21, 23–25]. The method aimed to minimise the sum of the expected total transportation cost (the optimisation objective) and its variability (the robustness measure) multiplied by a weighting value. Yan et al. presented a reliable, novel bus route schedule design solution by considering uncertainty in the buses’ travel times and the bus drivers’ schedule-recovery efforts [26]. The objective was to minimise the sum of the expected values of the random schedule deviation and its variability multiplied by a weighting value.Moreover, Montemanni et al. presented a new extension for solving the traveling salesman problem, where edge costs were specified as a range of possible values [11]. They applied a robust deviation criterion to propel optimisation over the interval data problem so obtained. Sungur et al. introduced scenario-based stochastic programming with recourse to model the uncertainty in customers and robust optimisation for the uncertainty in service times [27].Moreover, robust optimisation has been extended to multistage problems where the here-and-now decision is amended by a recourse decision [16]. Sun and Wang proposed a robust optimisation model for VRP under uncertainty to decrease the variability encountered in EVM (a special case of E-SDROA) [28]. The approach did not ensure the feasibility of the optimal solution for all scenarios. Meanwhile, its solution was complicated.


## 3. CE-SDROA (Conditional Expectation Semideviation Robust Optimisation Approach) for VRPU

### 3.1. Primary Sources of Uncertainty

In practice, estimating transportation cost (a type of marginal cost) is also a difficult task except for demand uncertainty caused by many unpredictable factors, including traffic conditions, accidents, congestion, and weather conditions. For this reason, the proposed robust optimisation approach focuses on two primary sources of uncertainty: the future demands that are to be served by the vehicle fleet and the transportation cost.


### 3.2. Problem Statement

VRP with demand and transportation cost uncertainty is a variant of VRPU. It can be defined by a complete undirected graphG=(V,E) with vertex set V={0,…,n} and edge set E={(i,j)∈V×V,i≠j}. Vertex 0∈V represents a depot (with no demand) at which a fleet of m identical vehicles of capacity Q∈Z+ is located; vertices {1,…,n} correspond to customers. Let V∗=V∖{0}. Λ is a set of scenarios with respect to total demand and transportation cost. P refers to the number of scenarios. A scenario λ is a realisation of total demand for all customers and the transportation cost for each route.We introduced a cost functionc:Λ×E→R+, a demand function d:V∗×Λ→Z+, and a set of vehicles K. The transportation cost cijλ=c(λ,(i,j)) of an edge (i,j)∈E is a realisation of transportation cost between customers i and j from scenario λ. It was supposed to be nonnegative. The costs cijλ were assumed to be symmetric (although the results can easily be modified to hold even in asymmetric cases) and they satisfied the triangle inequality. diλ=d(i,λ) is a realisation of the demand of customer i from scenario λ; diλ is serviced by more than one vehicle. The total demand from scenario λ is yλ=∑i∈V∗diλ. xij is a random variable relating to cijλ, Y is a random variable with respect to yλ. The probability of scenario λ is pλ=px01=c0,1λ,…,xij=cijλ,…,xn-1,n=cn-1,nλ,Y=yλ  i<j, ∑λ∈Λpλ=1.Suppose that the total demand in a scenario is known before the vehicle begins its route; then operators attach primary importance to the expected value of total transportation cost with regard to a failure scenario on the condition of coexistence of failure and successful scenarios. The vehicle routing problem with demand and cost uncertainty consists of finding a set ofK routes, minimizing the sum of the cost threshold and risk of potentially high costs in the presence of a failure scenario and satisfying the following conditions.(1)
Each client is assigned to, at least, one route.(2)
The demanddik of every customer is totally satisfied and can be serviced by more than one vehicle.(3)
Each route must begin and end at the depot and visits at least one customer.(4)
The total demand serviced by any vehicle does not exceed its capacity.


### 3.3. Formulation of CE-SDROA for the Proposed Problem

#### 3.3.1. Optimisation Objective

The total transportation cost of a solutions due to scenario λ can be represented by(1)hs,λ=∑i∈V∑j∈V∑k∈Kcijλxijk.X is a random variable with respect to h(s,λ). Considering a feasible solution s, the expected value of the total transportation cost in all failure scenarios under the condition of coexistence of failure and successful scenarios is(2)EX=hs,λ∣Y>mQ=∑λ∈Λh(s,λ)p(X=h(s,λ),Y>mQ)p(Y>mQ)=∑λ∈Λhs,λpY>mQ-1px01=c0,1λ,…,xij=cijλ,…,xn-1,n=cn-1,nλ,Y>mQ·pY>mQ-1.To simplify the process, letCE=E(X=hs,λ∣Y>mQ). Equation (2) refers to the expected total transportation cost in all failure scenarios under the condition of coexistence of failure and successful scenarios.


#### 3.3.2. Reference Level of CE

ω (ω>0) is a reference level of (2). Thus, ω·CE is a reference point from which deviation was measured. Besides ω=1, ω can reflect some matters of concern to decision makers at the depot, such as bidding (ω<1) and capital budget situations (ω>1).


#### 3.3.3. The Robustness Measure

The potential risk of the total transportation cost caused by demand and transportation cost uncertainty is defined as follows.Definition 1.
Potential risk with respect to a solutions caused by sources of uncertainty is expressed as(3)PRs=∑hs,λ>ω·CEhs,λ-ω·CE·pX=hs,λ,Y>mQpY>mQ.
The robustness measure of CE-SDROA is defined by(4)Γs=μPRs0≤μ≤1.In (4), μ denotes the level of concern about exceeding ω·CE. Γ(s) protects against potential scenarios that can incur extremely high costs.


#### 3.3.4. Formulation

Combining (2) and (4), we provided the following mixed integer programming formulation for the proposed problem. The notations were as follows:xijk is a boolean variable which is equal to 1 if vehicle k travels directly from i to j and to 0 otherwise;yik is the quantity of the demand of i delivered by the kth vehicle;M is a sufficiently large constant.The CE-SDROA for the proposed problem can now be formulated as follows.(CE-SDROA) Minimise(5)fCE-SDROA=ωE(X=hs,λ∣Y>mQ)+Γ(s)subject to(6)∑i=0n∑k=1mxijk≥1j=0,…,n,(7)∑i=0nxihk=∑j=0nxhjkh=0,…,n;k=1,…,m,(8)∑i∈S∑j∈Sxijk≤S-1k=1,…,m;S⊆V-0,(9)yik≤M∑j=0nxijki=1,…,n;k=1,…,m,(10)∑k=1myik≥max⁡{d11,…,diλ,…,dnn}i=1,…,n;λ∈Λ,(11)∑i=1nyik≤Qk=1,…,m,(12)xijk∈0,1i∈V;j∈V;k∈K,yik≥0i∈V;k∈K.Constraints (6)–(8) are the classical routing constraints: constraints (6) impose that each vertex is visited at least once, (7) are the flow conservation constraints, and (8) are the subtours elimination constraints. Constraints (9)–(11) concern the allocation of the demands of the customers among the vehicles: constraints (9) impose that customer i can be served by vehicle k only if k passes through i. Constraints (10) ensure that the entire demand of each vertex is satisfied while constraints (11) impose that the quantity delivered by each vehicle does not exceed the capacity.


#### 3.3.5. Solution Method

Let[x] be a unique integer n such that n≤x<n+1. This integer n is the integer part of x.M
i is expressed as follows:(13)Mi=Mi-QMiQ+MiQQ.s
∗ can be constructed as follows.Given an instanceI of CE-SDROA, one is able to build a reduced instance which denotes IR by modifying the demand Mi of each customer to Mi-QMi/Q. A solution sR for IR can be transformed into a solution s for I by adding Mi/Q direct trips for each customer. Now, given instance I of CE-SDROA, an algorithm (genetic algorithm, tabu search, etc.) that first determines an optimal solution sR∗ for the reduced instance IR was considered, and then the associated solutions s∗ for I were built.We use Nazif’s algorithm [29] to determine sR∗ for the reduced instance IR. The proposed algorithm uses an optimised crossover operator designed by a complete undirected bipartite graph to find an optimal set of delivery routes satisfying the requirements and giving minimal total cost.According to the definition ofMi, s∗ satisfies all demands in {diλ}. The method stated that solving CE-SDROA for the proposed problem was no more difficult than solving a single deterministic SDVRP while satisfying all demands in {diλ}. The solution method is not described in detail here because it was not the focus of this paper.


## 3.1. Primary Sources of Uncertainty

In practice, estimating transportation cost (a type of marginal cost) is also a difficult task except for demand uncertainty caused by many unpredictable factors, including traffic conditions, accidents, congestion, and weather conditions. For this reason, the proposed robust optimisation approach focuses on two primary sources of uncertainty: the future demands that are to be served by the vehicle fleet and the transportation cost.


## 3.2. Problem Statement

VRP with demand and transportation cost uncertainty is a variant of VRPU. It can be defined by a complete undirected graphG=(V,E) with vertex set V={0,…,n} and edge set E={(i,j)∈V×V,i≠j}. Vertex 0∈V represents a depot (with no demand) at which a fleet of m identical vehicles of capacity Q∈Z+ is located; vertices {1,…,n} correspond to customers. Let V∗=V∖{0}. Λ is a set of scenarios with respect to total demand and transportation cost. P refers to the number of scenarios. A scenario λ is a realisation of total demand for all customers and the transportation cost for each route.We introduced a cost functionc:Λ×E→R+, a demand function d:V∗×Λ→Z+, and a set of vehicles K. The transportation cost cijλ=c(λ,(i,j)) of an edge (i,j)∈E is a realisation of transportation cost between customers i and j from scenario λ. It was supposed to be nonnegative. The costs cijλ were assumed to be symmetric (although the results can easily be modified to hold even in asymmetric cases) and they satisfied the triangle inequality. diλ=d(i,λ) is a realisation of the demand of customer i from scenario λ; diλ is serviced by more than one vehicle. The total demand from scenario λ is yλ=∑i∈V∗diλ. xij is a random variable relating to cijλ, Y is a random variable with respect to yλ. The probability of scenario λ is pλ=px01=c0,1λ,…,xij=cijλ,…,xn-1,n=cn-1,nλ,Y=yλ  i<j, ∑λ∈Λpλ=1.Suppose that the total demand in a scenario is known before the vehicle begins its route; then operators attach primary importance to the expected value of total transportation cost with regard to a failure scenario on the condition of coexistence of failure and successful scenarios. The vehicle routing problem with demand and cost uncertainty consists of finding a set ofK routes, minimizing the sum of the cost threshold and risk of potentially high costs in the presence of a failure scenario and satisfying the following conditions.(1)
Each client is assigned to, at least, one route.(2)
The demanddik of every customer is totally satisfied and can be serviced by more than one vehicle.(3)
Each route must begin and end at the depot and visits at least one customer.(4)
The total demand serviced by any vehicle does not exceed its capacity.


## 3.3. Formulation of CE-SDROA for the Proposed Problem

### 3.3.1. Optimisation Objective

The total transportation cost of a solutions due to scenario λ can be represented by(1)hs,λ=∑i∈V∑j∈V∑k∈Kcijλxijk.X is a random variable with respect to h(s,λ). Considering a feasible solution s, the expected value of the total transportation cost in all failure scenarios under the condition of coexistence of failure and successful scenarios is(2)EX=hs,λ∣Y>mQ=∑λ∈Λh(s,λ)p(X=h(s,λ),Y>mQ)p(Y>mQ)=∑λ∈Λhs,λpY>mQ-1px01=c0,1λ,…,xij=cijλ,…,xn-1,n=cn-1,nλ,Y>mQ·pY>mQ-1.To simplify the process, letCE=E(X=hs,λ∣Y>mQ). Equation (2) refers to the expected total transportation cost in all failure scenarios under the condition of coexistence of failure and successful scenarios.


### 3.3.2. Reference Level of CE

ω (ω>0) is a reference level of (2). Thus, ω·CE is a reference point from which deviation was measured. Besides ω=1, ω can reflect some matters of concern to decision makers at the depot, such as bidding (ω<1) and capital budget situations (ω>1).


### 3.3.3. The Robustness Measure

The potential risk of the total transportation cost caused by demand and transportation cost uncertainty is defined as follows.Definition 1.
Potential risk with respect to a solutions caused by sources of uncertainty is expressed as(3)PRs=∑hs,λ>ω·CEhs,λ-ω·CE·pX=hs,λ,Y>mQpY>mQ.
The robustness measure of CE-SDROA is defined by(4)Γs=μPRs0≤μ≤1.In (4), μ denotes the level of concern about exceeding ω·CE. Γ(s) protects against potential scenarios that can incur extremely high costs.


### 3.3.4. Formulation

Combining (2) and (4), we provided the following mixed integer programming formulation for the proposed problem. The notations were as follows:xijk is a boolean variable which is equal to 1 if vehicle k travels directly from i to j and to 0 otherwise;yik is the quantity of the demand of i delivered by the kth vehicle;M is a sufficiently large constant.The CE-SDROA for the proposed problem can now be formulated as follows.(CE-SDROA) Minimise(5)fCE-SDROA=ωE(X=hs,λ∣Y>mQ)+Γ(s)subject to(6)∑i=0n∑k=1mxijk≥1j=0,…,n,(7)∑i=0nxihk=∑j=0nxhjkh=0,…,n;k=1,…,m,(8)∑i∈S∑j∈Sxijk≤S-1k=1,…,m;S⊆V-0,(9)yik≤M∑j=0nxijki=1,…,n;k=1,…,m,(10)∑k=1myik≥max⁡{d11,…,diλ,…,dnn}i=1,…,n;λ∈Λ,(11)∑i=1nyik≤Qk=1,…,m,(12)xijk∈0,1i∈V;j∈V;k∈K,yik≥0i∈V;k∈K.Constraints (6)–(8) are the classical routing constraints: constraints (6) impose that each vertex is visited at least once, (7) are the flow conservation constraints, and (8) are the subtours elimination constraints. Constraints (9)–(11) concern the allocation of the demands of the customers among the vehicles: constraints (9) impose that customer i can be served by vehicle k only if k passes through i. Constraints (10) ensure that the entire demand of each vertex is satisfied while constraints (11) impose that the quantity delivered by each vehicle does not exceed the capacity.


### 3.3.5. Solution Method

Let[x] be a unique integer n such that n≤x<n+1. This integer n is the integer part of x.M
i is expressed as follows:(13)Mi=Mi-QMiQ+MiQQ.s
∗ can be constructed as follows.Given an instanceI of CE-SDROA, one is able to build a reduced instance which denotes IR by modifying the demand Mi of each customer to Mi-QMi/Q. A solution sR for IR can be transformed into a solution s for I by adding Mi/Q direct trips for each customer. Now, given instance I of CE-SDROA, an algorithm (genetic algorithm, tabu search, etc.) that first determines an optimal solution sR∗ for the reduced instance IR was considered, and then the associated solutions s∗ for I were built.We use Nazif’s algorithm [29] to determine sR∗ for the reduced instance IR. The proposed algorithm uses an optimised crossover operator designed by a complete undirected bipartite graph to find an optimal set of delivery routes satisfying the requirements and giving minimal total cost.According to the definition ofMi, s∗ satisfies all demands in {diλ}. The method stated that solving CE-SDROA for the proposed problem was no more difficult than solving a single deterministic SDVRP while satisfying all demands in {diλ}. The solution method is not described in detail here because it was not the focus of this paper.


## 3.3.1. Optimisation Objective

The total transportation cost of a solutions due to scenario λ can be represented by(1)hs,λ=∑i∈V∑j∈V∑k∈Kcijλxijk.X is a random variable with respect to h(s,λ). Considering a feasible solution s, the expected value of the total transportation cost in all failure scenarios under the condition of coexistence of failure and successful scenarios is(2)EX=hs,λ∣Y>mQ=∑λ∈Λh(s,λ)p(X=h(s,λ),Y>mQ)p(Y>mQ)=∑λ∈Λhs,λpY>mQ-1px01=c0,1λ,…,xij=cijλ,…,xn-1,n=cn-1,nλ,Y>mQ·pY>mQ-1.To simplify the process, letCE=E(X=hs,λ∣Y>mQ). Equation (2) refers to the expected total transportation cost in all failure scenarios under the condition of coexistence of failure and successful scenarios.


## 3.3.2. Reference Level of CE

ω (ω>0) is a reference level of (2). Thus, ω·CE is a reference point from which deviation was measured. Besides ω=1, ω can reflect some matters of concern to decision makers at the depot, such as bidding (ω<1) and capital budget situations (ω>1).


## 3.3.3. The Robustness Measure

The potential risk of the total transportation cost caused by demand and transportation cost uncertainty is defined as follows.Definition 1.
Potential risk with respect to a solutions caused by sources of uncertainty is expressed as(3)PRs=∑hs,λ>ω·CEhs,λ-ω·CE·pX=hs,λ,Y>mQpY>mQ.
The robustness measure of CE-SDROA is defined by(4)Γs=μPRs0≤μ≤1.In (4), μ denotes the level of concern about exceeding ω·CE. Γ(s) protects against potential scenarios that can incur extremely high costs.


## 3.3.4. Formulation

Combining (2) and (4), we provided the following mixed integer programming formulation for the proposed problem. The notations were as follows:xijk is a boolean variable which is equal to 1 if vehicle k travels directly from i to j and to 0 otherwise;yik is the quantity of the demand of i delivered by the kth vehicle;M is a sufficiently large constant.The CE-SDROA for the proposed problem can now be formulated as follows.(CE-SDROA) Minimise(5)fCE-SDROA=ωE(X=hs,λ∣Y>mQ)+Γ(s)subject to(6)∑i=0n∑k=1mxijk≥1j=0,…,n,(7)∑i=0nxihk=∑j=0nxhjkh=0,…,n;k=1,…,m,(8)∑i∈S∑j∈Sxijk≤S-1k=1,…,m;S⊆V-0,(9)yik≤M∑j=0nxijki=1,…,n;k=1,…,m,(10)∑k=1myik≥max⁡{d11,…,diλ,…,dnn}i=1,…,n;λ∈Λ,(11)∑i=1nyik≤Qk=1,…,m,(12)xijk∈0,1i∈V;j∈V;k∈K,yik≥0i∈V;k∈K.Constraints (6)–(8) are the classical routing constraints: constraints (6) impose that each vertex is visited at least once, (7) are the flow conservation constraints, and (8) are the subtours elimination constraints. Constraints (9)–(11) concern the allocation of the demands of the customers among the vehicles: constraints (9) impose that customer i can be served by vehicle k only if k passes through i. Constraints (10) ensure that the entire demand of each vertex is satisfied while constraints (11) impose that the quantity delivered by each vehicle does not exceed the capacity.


## 3.3.5. Solution Method

Let[x] be a unique integer n such that n≤x<n+1. This integer n is the integer part of x.M
i is expressed as follows:(13)Mi=Mi-QMiQ+MiQQ.s
∗ can be constructed as follows.Given an instanceI of CE-SDROA, one is able to build a reduced instance which denotes IR by modifying the demand Mi of each customer to Mi-QMi/Q. A solution sR for IR can be transformed into a solution s for I by adding Mi/Q direct trips for each customer. Now, given instance I of CE-SDROA, an algorithm (genetic algorithm, tabu search, etc.) that first determines an optimal solution sR∗ for the reduced instance IR was considered, and then the associated solutions s∗ for I were built.We use Nazif’s algorithm [29] to determine sR∗ for the reduced instance IR. The proposed algorithm uses an optimised crossover operator designed by a complete undirected bipartite graph to find an optimal set of delivery routes satisfying the requirements and giving minimal total cost.According to the definition ofMi, s∗ satisfies all demands in {diλ}. The method stated that solving CE-SDROA for the proposed problem was no more difficult than solving a single deterministic SDVRP while satisfying all demands in {diλ}. The solution method is not described in detail here because it was not the focus of this paper.


## 4. Relationship between the Proposed CE-SDROA and E-SDROA

Proposition 2.
If all realisations of the total demand exceededmQ, then E-SDROA (see Appendix) becomes a special case of CE-SDROA given by setting ω=1.Proof.
If all realisations of the total demand exceededmQ, then P(Y>mQ)=1:(14)pX=hs,λ,Y>mQ=pX=hs,λ.
Then,(15)EX=hs,λ∣Y>mQ=∑λ∈Λhs,λpX=hs,λ∣Y>mQ=∑λ∈Λhs,λpX=hs,λ=EX=hs,λ.
CE-SDROA becomes(16)fCE-SDROA=EX=hs,λ+μEhs,λ-EX=hs,λ+.
Hence, Proposition2 holds.Proposition2 indicated that E-SDROA was a special case of CE-SDROA in the situation where all realisations of the total demand exceeded mQ.


## 5. Numerical Experiments

### 5.1. Introduction to Test Instances and Hardware Platform

We generated some new test instances derived from classical instances of SDVRP [5]. The name of each instance should allow one to rapidly determine its characteristics. In particular, the names have the form SDnnn-kk∗ and are composed of three positional fields.The first field of the name,nnn, is a three-digit integer that denotes the number of vertices in the problem graph, that is, including the depot vertex. The second field,kk, a two-digit integer, represents the number of scenarios. The last field of the name, ∗, is an alphabetical character that identifies the test instances differing from other test instances for SDVRP with deterministic demands and transportation cost. The demand from each vertex and the transportation cost of each edge were generated according to their Poisson distributions, which had a mean value equal to the vertex demand and edge transportation cost, respectively [3]. The probability of a failure scenario arising was defined as follows:(17)p(X=h(s,λ),Y>mQ)p(Y>mQ).It was obtained from(18)pX=hs,λ,Y>mQpY>mQ=px01=c01λ,…,xij=cijλ,…,xn,n-1=cn,n-1λ·1-∑yλ≤mQpY=yλ∣x01=c01λ,…,xij=cijλ,…,xn,n-1=cn,n-1λ∑yλ≤mQ·1-∑yλ≤mQpY=yλ-1.Simulations were carried out on a PC (Windows 7 operating system, Pentium CPU B950 running at 210 GHz, with 4 GHz internal memory) using CPLEX 12.1 software.Demand and transportation uncertainty sets are defined as follows.Transportation cost Uncertainty setUC. For each arc(i,j)∈E, the transportation cost c~ij takes values in [c^ij,c^ij+dij], where dij represents the maximum deviation from the nominal transportation cost c^ij. We introduce a nonnegative integer Γ as a parameter for controlling the degree of robustness for the transportation cost uncertainties. Then, the uncertainty set of transportation cost data is given as(19)Uc=c~∈RE∣c~ij=c^ij+dijvij,∑(i,j)∈E∑i,j∈Evij≤Γ,0≤vij≤1,∀i,j∈E.Demand Uncertainty setUD. For each customer i∈V, the demand r~i takes values in [r^i,r^i+oi]; where oi represents the maximum deviation from the nominal demand value r^i. We introduce a nonnegative integer Λ as a parameter for controlling the degree of robustness for the demand uncertainties. Then, the uncertainty set of demand data is given as(20)UD=r~∈RV∣r~i=r^i+oiwi,∑i∈V∑i∈Vwi≤Λ,0≤wi≤1,∀i∈V.The computational results of the Solomon problems are summarized in Table 1. The headings Γ and Λ refer to the degrees of robustness for the transportation cost and demand, which determine the uncertainty sets UC and UD, respectively. The solutions with Γ=0, Λ=0 are a nonrobust (deterministic) version of the problem and are used for comparison with robust aware solutions having Γ=100, Λ=80. The numbers of vehicles to be used are shown under the headings K using our solution method. The numbers of vehicles to be used are shown under the headings K′ using robust optimization approach proposed by [7]. For all instances, we set dij=c^ij, ∀(i,j)∈E, and oi=r^i, ∀i∈V. The asterisk (∗) indicates that the time limit (one hour) was reached.Table 1
Results for the Augerat problems.
Γ, Λ
Time
opt
A-n32-k5
0, 0
3600*
1041
100, 100
3600*
1028
B-n34-k5
0, 0
3600*
827
100, 100
3600*
1023
A-n34-k5
0, 0
3600*
827
100, 100
3600*
1021
P-n19-k2
0, 0
3600*
261
100, 100
3600*
278
P-n22-k8
0, 0
3.727
612
100, 100
29.268
653
B-n39-k5
0, 0
3600*
639
100, 100
3600*
842
B-n31-k5
0, 0
3600*
696
100, 100
3600*
812Table1 reports the computational results for the Augerat problems. We see significant increments in the robustness of the solutions without much loss in solution quality.


### 5.2. Comparison between Optimal Solutions of CE-SDROA and E-SDROA

For the given parametersω and μ, we generated some scenarios using the scheme mentioned in Section 5.1 Table 1 shows the effect of ω and μ on the optimal objective value and robustness measure. Headings opt and dev represent values of (5) and (3) with respect to SD096-60∗. A series of robust optimal solutions can be generated as We changed the weighting parameters, μ, ω. When we set ω=1 and μ=0, the model corresponded to, and focuses strictly on, the expected total transportation cost given that all realisations of the total demand exceeded  mQ. For illustrative purposes, we chose the solution corresponding to ω=1.1 for further discussion, but a similar discussion could be framed with a different choice of ω. For ω=1.1, the robust optimal objective value was 11136.12. This implied that it was larger than the stochastic optimal objective value by 17.9% when ω=1 and μ=0. However, dev dropped by 17.2% relative to the stochastic optimal objective value when ω=1 and μ=0.Table2 shows the relationship between the optimal objective values of CE-SDROA and E-SDROA. According to the formulation of E-SDROA for the proposed problem, the optimal objective value of the formulation was greater than or equal to the optimal objective value of the stochastic optimisation approach. Unlike the optimal objective value of E-SDROA, the optimal objective value of CE-SDROA was possibly better than that of the stochastic optimisation approach.Table 2
Effect ofω and μ on optimal objective value and robustness measure for SD096-60*.
ω
μ
opt
dev
0.6
0.1
7736.26
3566.85
0.7
0.2
7963.11
3419.80
0.8
0.3
8369.23
3180.24
0.9
0.4
8923.21
2832.48
1.0
0
9136.66
2615.06
1.1
0.6
11136.12
2165.45
1.2
0.7
10873.69
2016.27
1.3
0.8
14273.86
827.10
1.4
0.9
16523.82
2704.21
1.5
1
19216.39
2166.27The results in Tables2 and 3 showed that the optimal objective value of E-SDROA only paid attention to the level of concern about cost threshold (EV) being exceeded, while CE-SDROA for VRPU made a trade-off between the optimal objective value and the risk of potentially high costs with the aid of ω and μ.Table 3
Relationship between the optimal objective values of CE-SDROA and stochastic optimisation approach.
Test instances
ω
μ
opt
SD032-60*
0.6
0.1
1128.61 (<CE)
SD032-40*
0.7
0.2
876.32 (<CE)
SD048-60*
0.8
0.3
4972.36 (<CE)
SD064-35*
0.9
0.4
2931.27 (<CE)
SD080-50*
1.0
0.5
7527.63 (=CE)
SD120-40*
1.2
0.7
10873.69 (>CE)
SD144-30*
1.3
0.8
14273.86 (>CE)
SD160-30*
1.4
0.9
16523.82 (>CE)
SD240-30*
1.5
1
37216.39 (>CE)


### 5.3. Performance Analysis of Our Solution Method

In order to examine the performance of our solution method, PSO algorithm (determinesR∗ for the reduced instance IR, and then the associated solutions s∗ for I were built) and ant colony algorithm (determine sR∗ for the reduced instance IR, and then the associated solutions s∗ for I were built) are used for comparison with our solution method. GA is denoted as our solution method.The search methods mentioned above have been programmed in MATLAB R2013a and have ran on an Intel(R) Core(TM) i5-3337U CPU@1.80 GHz 8.00 GB-RAM.It can be observed from Table4 that the solution quality of our solution method is obviously better than PSO and ant colony algorithm. It can be explained that the crossover operator can enlarge the search space and improve the performance of PSO and Ant colony algorithm. Therefore, the crossover operator can ensure the better optimization.Table 4
The computational results on 7 test instances.
Instance name
Γ, Λ
PSO
Ant colony algorithm
GA
A-n32-k5
150, 50
977
977
977
B-n34-k5
150, 50
1026
1045
1015
A-n34-k5
150, 50
1216
1210
1197
P-n19-k2
150, 50
625
636
597
P-n22-k8
150,  50
756
765
702
B-n39-k5
150,  50
1256
1253
1156
B-n31-k5
150,  50
1123
1101
997


## 5.1. Introduction to Test Instances and Hardware Platform

We generated some new test instances derived from classical instances of SDVRP [5]. The name of each instance should allow one to rapidly determine its characteristics. In particular, the names have the form SDnnn-kk∗ and are composed of three positional fields.The first field of the name,nnn, is a three-digit integer that denotes the number of vertices in the problem graph, that is, including the depot vertex. The second field,kk, a two-digit integer, represents the number of scenarios. The last field of the name, ∗, is an alphabetical character that identifies the test instances differing from other test instances for SDVRP with deterministic demands and transportation cost. The demand from each vertex and the transportation cost of each edge were generated according to their Poisson distributions, which had a mean value equal to the vertex demand and edge transportation cost, respectively [3]. The probability of a failure scenario arising was defined as follows:(17)p(X=h(s,λ),Y>mQ)p(Y>mQ).It was obtained from(18)pX=hs,λ,Y>mQpY>mQ=px01=c01λ,…,xij=cijλ,…,xn,n-1=cn,n-1λ·1-∑yλ≤mQpY=yλ∣x01=c01λ,…,xij=cijλ,…,xn,n-1=cn,n-1λ∑yλ≤mQ·1-∑yλ≤mQpY=yλ-1.Simulations were carried out on a PC (Windows 7 operating system, Pentium CPU B950 running at 210 GHz, with 4 GHz internal memory) using CPLEX 12.1 software.Demand and transportation uncertainty sets are defined as follows.Transportation cost Uncertainty setUC. For each arc(i,j)∈E, the transportation cost c~ij takes values in [c^ij,c^ij+dij], where dij represents the maximum deviation from the nominal transportation cost c^ij. We introduce a nonnegative integer Γ as a parameter for controlling the degree of robustness for the transportation cost uncertainties. Then, the uncertainty set of transportation cost data is given as(19)Uc=c~∈RE∣c~ij=c^ij+dijvij,∑(i,j)∈E∑i,j∈Evij≤Γ,0≤vij≤1,∀i,j∈E.Demand Uncertainty setUD. For each customer i∈V, the demand r~i takes values in [r^i,r^i+oi]; where oi represents the maximum deviation from the nominal demand value r^i. We introduce a nonnegative integer Λ as a parameter for controlling the degree of robustness for the demand uncertainties. Then, the uncertainty set of demand data is given as(20)UD=r~∈RV∣r~i=r^i+oiwi,∑i∈V∑i∈Vwi≤Λ,0≤wi≤1,∀i∈V.The computational results of the Solomon problems are summarized in Table 1. The headings Γ and Λ refer to the degrees of robustness for the transportation cost and demand, which determine the uncertainty sets UC and UD, respectively. The solutions with Γ=0, Λ=0 are a nonrobust (deterministic) version of the problem and are used for comparison with robust aware solutions having Γ=100, Λ=80. The numbers of vehicles to be used are shown under the headings K using our solution method. The numbers of vehicles to be used are shown under the headings K′ using robust optimization approach proposed by [7]. For all instances, we set dij=c^ij, ∀(i,j)∈E, and oi=r^i, ∀i∈V. The asterisk (∗) indicates that the time limit (one hour) was reached.Table 1
Results for the Augerat problems.
Γ, Λ
Time
opt
A-n32-k5
0, 0
3600*
1041
100, 100
3600*
1028
B-n34-k5
0, 0
3600*
827
100, 100
3600*
1023
A-n34-k5
0, 0
3600*
827
100, 100
3600*
1021
P-n19-k2
0, 0
3600*
261
100, 100
3600*
278
P-n22-k8
0, 0
3.727
612
100, 100
29.268
653
B-n39-k5
0, 0
3600*
639
100, 100
3600*
842
B-n31-k5
0, 0
3600*
696
100, 100
3600*
812Table1 reports the computational results for the Augerat problems. We see significant increments in the robustness of the solutions without much loss in solution quality.


## 5.2. Comparison between Optimal Solutions of CE-SDROA and E-SDROA

For the given parametersω and μ, we generated some scenarios using the scheme mentioned in Section 5.1 Table 1 shows the effect of ω and μ on the optimal objective value and robustness measure. Headings opt and dev represent values of (5) and (3) with respect to SD096-60∗. A series of robust optimal solutions can be generated as We changed the weighting parameters, μ, ω. When we set ω=1 and μ=0, the model corresponded to, and focuses strictly on, the expected total transportation cost given that all realisations of the total demand exceeded  mQ. For illustrative purposes, we chose the solution corresponding to ω=1.1 for further discussion, but a similar discussion could be framed with a different choice of ω. For ω=1.1, the robust optimal objective value was 11136.12. This implied that it was larger than the stochastic optimal objective value by 17.9% when ω=1 and μ=0. However, dev dropped by 17.2% relative to the stochastic optimal objective value when ω=1 and μ=0.Table2 shows the relationship between the optimal objective values of CE-SDROA and E-SDROA. According to the formulation of E-SDROA for the proposed problem, the optimal objective value of the formulation was greater than or equal to the optimal objective value of the stochastic optimisation approach. Unlike the optimal objective value of E-SDROA, the optimal objective value of CE-SDROA was possibly better than that of the stochastic optimisation approach.Table 2
Effect ofω and μ on optimal objective value and robustness measure for SD096-60*.
ω
μ
opt
dev
0.6
0.1
7736.26
3566.85
0.7
0.2
7963.11
3419.80
0.8
0.3
8369.23
3180.24
0.9
0.4
8923.21
2832.48
1.0
0
9136.66
2615.06
1.1
0.6
11136.12
2165.45
1.2
0.7
10873.69
2016.27
1.3
0.8
14273.86
827.10
1.4
0.9
16523.82
2704.21
1.5
1
19216.39
2166.27The results in Tables2 and 3 showed that the optimal objective value of E-SDROA only paid attention to the level of concern about cost threshold (EV) being exceeded, while CE-SDROA for VRPU made a trade-off between the optimal objective value and the risk of potentially high costs with the aid of ω and μ.Table 3
Relationship between the optimal objective values of CE-SDROA and stochastic optimisation approach.
Test instances
ω
μ
opt
SD032-60*
0.6
0.1
1128.61 (<CE)
SD032-40*
0.7
0.2
876.32 (<CE)
SD048-60*
0.8
0.3
4972.36 (<CE)
SD064-35*
0.9
0.4
2931.27 (<CE)
SD080-50*
1.0
0.5
7527.63 (=CE)
SD120-40*
1.2
0.7
10873.69 (>CE)
SD144-30*
1.3
0.8
14273.86 (>CE)
SD160-30*
1.4
0.9
16523.82 (>CE)
SD240-30*
1.5
1
37216.39 (>CE)


## 5.3. Performance Analysis of Our Solution Method

In order to examine the performance of our solution method, PSO algorithm (determinesR∗ for the reduced instance IR, and then the associated solutions s∗ for I were built) and ant colony algorithm (determine sR∗ for the reduced instance IR, and then the associated solutions s∗ for I were built) are used for comparison with our solution method. GA is denoted as our solution method.The search methods mentioned above have been programmed in MATLAB R2013a and have ran on an Intel(R) Core(TM) i5-3337U CPU@1.80 GHz 8.00 GB-RAM.It can be observed from Table4 that the solution quality of our solution method is obviously better than PSO and ant colony algorithm. It can be explained that the crossover operator can enlarge the search space and improve the performance of PSO and Ant colony algorithm. Therefore, the crossover operator can ensure the better optimization.Table 4
The computational results on 7 test instances.
Instance name
Γ, Λ
PSO
Ant colony algorithm
GA
A-n32-k5
150, 50
977
977
977
B-n34-k5
150, 50
1026
1045
1015
A-n34-k5
150, 50
1216
1210
1197
P-n19-k2
150, 50
625
636
597
P-n22-k8
150,  50
756
765
702
B-n39-k5
150,  50
1256
1253
1156
B-n31-k5
150,  50
1123
1101
997


## 6. Conclusion and Future Work

Unlike E-SDROA, CE-SDROA made a trade-off between the expected value of total transportation cost in all failure scenarios and its variation under conditions of the coexistence of failure and successful scenarios. Compared with stochastic optimisation approaches for VRPU, CE-SDROA dealt with the expected value of total transportation cost in all failure scenarios under conditions of the coexistence of failure and successful scenarios. The existence of this trade-off was intuitive, but the model provided a means of quantifying the trade-off and determining optimal choices for varying levels of risk acceptance. This provided a basis for improved decision making in a variety of situations.We draw the following conclusions through theoretical analysis.(1)
Compared with stochastic optimisation approaches available, CE-SDROA made a trade-off between its cost threshold and accepting the risk of potentially high costs.(2)
E-SDROA failed to solve situations relevant to bidding or capital budget decisions. On the contrary, CE-SDROA considered these situations using a reference level of CE.(3)
Solving CE-SDROA for VRPU was no more difficult than solving a single deterministic SDVRP while satisfying all demands in a given bounded uncertainty set.Although CE-SDROA for VRPU does present some significant improvements over E-SDROA as described above, there remained some problems to be addressed by future research. The optimal solution of CE-SDROA yielded extra inventory costs for some customers in some scenarios.It is also worth considering the relationship of the current formulation to an explicit multistage dynamic optimization. The current model defines stages by types of decisions (i.e., fleet acquisition versus operational allocation). An alternative modeling approach might consider time stages, with both fleet acquisition and operational variables at each stage. This would make the model more similar to dynamic vehicle allocation models. This is also likely to be a useful effort for future research.



---

*Source: 901583-2015-03-31.xml*