# A Comparison of Robust Criteria for Vehicle Routing Problem with Soft Time Windows

Authors: Thanasak Mouktonglang; Phannipa Worapun
Journal: International Journal of Mathematics and Mathematical Sciences
 (2019)

---

## Abstract

In this study, we focus on robust criteria for vehicle routing problems with soft time windows (VRPSTW). The main objective is to find a robust solution that provides the best for the worst case performance for VRPSTW under uncertain travel times. The robust criteria are used in this study such as absolute robustness, robust deviation, and relative robustness as a basis for comparison. The VRPSTW becomes complex when the travel times are uncertain. This uncertainty can be caused by traffic jams, accidents, or inclement weather conditions. The experiment uses benchmarking problems. The number of scenarios is generated randomly into intervals of travel time, equal to 4, 6, and 8 instances for each problem set. Each set of problem instances can be denoted by the percentage of uncertaintyα, equal to 0.2, 0.4, 0.6, and 0.8. This study will demonstrate that the most indicated robust criteria for these situations are robust deviation and relative robustness. The most important part of the decision maker is to determine the uncertainty percentage to cover all uncertainties that need to be considered.


---

## Body

## 1. Introduction

The vehicle routing problem (VRP) is in the field of transportation and logistics. It plays an important role for driving the smart city. The logistic for smart city should support all logistic platforms and help users to make important decisions. The problem of providing transportation routes from a central depot to customers in order to save transportation costs is presented by Dantzig and Ramser [1]. The vehicle routing problem with soft time windows (VRPSTW) is a variant of the VRP. The solution of the VRPSTW is a set of routes consisting of sequences of customers. Each route is designed to insure delivery within specified time frames called windows. Moreover, in VRPSTW, the time windows can be adjusted if a penalty is paid. Therefore, the objective of the VRPSTW problem is to find transportation routes to save the travel costs and penalty costs of transportation. The service time interval in VRPSTW is shown in Figure 1. Kabcome and Mouktonglang [2] presented an explicitly written mathematical model for VRPSTW and the problem was solved efficiently. From the numerical result, it was clear that by adding the service penalty constraints, the problem could be solved sufficiently and it provided another solution to the problem. Taillard et al. [3] used tabu search, metaheuristic approach, for the vehicle routing problem with soft time windows. Min [4] solved a multiobjective vehicle routing problem with soft time windows for the public library distribution system.Figure 1
Service time interval in VRPSTW.This VRPSTW becomes complex when the travel times are uncertain due to traffic conditions such as traffic jams, accidents, or bad weather conditions. Agra et al. [5] considered a robust counterpart for the VRP. They consider the problem that arises in maritime transportation where delays should be taken into account. Therefore, we are interested in studying the VRPSTW problem with uncertain travel time. The general principles used for solving a problem with uncertainties are divided into two types: the deterministic optimization approach and the stochastic optimization approach. The deterministic optimization approach has some good properties such as the mathematical models are so much easier to write and to understand. The size of the deterministic optimization problem is usually smaller than the stochastic ones. However, it also has some disadvantages when the problem contains uncertainties because this method finds solutions by estimating uncertainty to some value or by using the most frequent situation to represent the problem. The solution is to solve only the selected situation. When the uncertainty is higher, the efficiency of this method is immediately decreased. The stochastic optimization approach is to find solutions from more than one uncertainty estimation. See [6] for more details where the authors considered stochastic version for VRP with time windows. This method requires historical uncertainty data that are analyzed using statistical methods and expressed in terms of probability values to represent uncertainty. In this way, the stochastic method has the ability to resolve several problems containing uncertainty. However, if we consider the actual application, the stochastic method presents difficulties and does not respond to the needs of the decision maker because data collection requires a long period of time. The major disadvantage of the stochastic method is that the solution can only be a solution that comes from the expected value. In this situation, the decision maker must assume a risk when the actual situation occurs at the minimum or maximum range. Even if this situation occurs only once, it may have serious consequences in terms of reliability or lost opportunity.This study focuses on responding to the actual use of decision makers by offering a robust optimization approach. The solutions must be applicable to different conditions of use. Robustness approach is an important objective of this research, which is to find the most suitable route that is able to withstand the uncertainty of travel time. This paper proposes an approach to the robust discrete optimization of VRPSTW with uncertain travel times. By solving the VRPSTW multiple times, the minimax optimization problem becomes the main objective of this paper (i.e., to find a robust solution under robust criteria).In the following section, we provide a review of relevant literature in robust discrete optimization problems. Section3 presents the method of solving the problems. Section 4 represents the results and related discussion. The numerical experiments use benchmark data from the VRP problem in Solomon’s VRPTW [7]. Finally, the conclusions are presented in Section 5.


## 2. Literature Review

The problem of decision-making under this uncertainty began to be discussed in 1955 by Dantzig [8] and was developed by Charnes and Cooper [9]. A lot of studies on uncertainty rely on stochastic programming techniques based on either recourse models or probabilistic constraints with uncertainty in demands, supplies, travel times, and many others. We refer to Ben-Tal et al. [10] where these two approaches are discussed in detail. In this study, the authors are interested in finding solutions that satisfy conditions to withstand uncertainty or finding the best value in a worst case scenario. Kouvelis and Yu [11] described a robust decision-making framework which can be used to find durable solutions that consist of 3 main parts: (1) creating uncertain data with various situations, (2) selecting criteria for judging durable solutions, and (3) creating the most suitable model for durable decisions.The process for finding solutions that are resistant to uncertainty is as follows: letS be a set of scenarios, s∈S, D be data sets, Ds be a set of data that are uncertain according to the situation s, Fs be the set of all possible solutions for each s and Fs≠∅, X be the set of decision variables and X∈Fs, and fX,Ds be the function used for finding solution X of each scenario Ds and Xs∗ be the optimal solution of each scenario Ds satisfying the following problem:(1)ZS=fXs∗,Ds=minX∈FsfX,Ds.From equation (1), it is known that the number to solve deterministic problems is equal to the number of situations. We used three robust criteria for finding the robust solution and are given as follows.Definition 1.
The absolute robustness criterionZA: let XA be the decision variable of absolute robustness criterion determined by(2)ZA=maxs∈SfXA,Ds=minX∈∩s∈SFsmaxs∈SfX,Ds.Definition 2.
The robust deviationZD: let XD be the decision variable of robust deviation criterion determined by(3)ZD=maxs∈SfXD,Ds−fXs∗,Ds=minX∈∩Fs∈Ssmaxs∈SfX,Ds−fXs∗,Ds.Definition 3.
The relative robustnessZR: let XR be the decision variable of robust deviation criterion determined by(4)ZR=maxs∈SfXR,Ds−fXs∗,DsfXs∗,Ds=minX∈∩Fs∈Ssmaxs∈SfX,Ds−fXs∗,DsfXs∗,Ds.


## 3. Methodology

This section presents the mathematical model for solving the robust solution, that is, the best of the worst case performance for VRPSTW under uncertain travel times. The first part presents the vehicle routing problems with soft time windows (VRPSTW). The second part presents the robust vehicle routing with soft time windows (RVRPSTW).


### 3.1. The Vehicle Routing Problems with Soft Time Windows (VRPSTW)

The VRPSTW is defined on a directed graphG=N,A, where N=o,d,1,2,3,…,n is a set of vertices (o,d is the depot) and A is a set of arcs i,j representing the connections between the depot and customers or among the customers A=i,ji,j∈N,i≠j.The following notations are introduced to formulate the mathematical model of VRPSTW.


#### 3.1.1. Indices

i
,
j
,
n index of nodes
k index of vehicle


#### 3.1.2. Sets

N
=
o
,
d
,
1,2,3
,
…
,
n be a node set (o is origin and d is destination)
N
∗
=
N
−
o
,
d be a set of customers
K
=
1,2,3
,
…
,
k be a set of vehicles


#### 3.1.3. Decision Variables

x
k
,
i
,
j
=
1
;
if vehicle
k
travels directly from node
i
to
j
;
0
;
otherwise
y
i is the violation degree of the upper bound of soft time windows at the customer i
w
i be the arrival time at the customer i


#### 3.1.4. Input Parameters

c
i
,
j be the travel cost from i to j
t
i
,
j be a time from node i to j
x
c
i be the coordinate x of i
y
c
i be the coordinate y of i,
d
s
i
,
j be a distance between customers i and j dsi,j=xci−xcj2+yci−ycj2
d
i be the demand of the customer i, and pi be penalty cost per hour for the lateness of customer i
a
i be the early time to service the node i without penalty
b
i be the last time to service the note i without penalty
b
i
′ be the last time to service the node i with penalty
v
i be a service time at the customer i
q
k be the capacity of the vehicle kThe solution to the VRPSTW must satisfy the following:(1)
Every vehicle starts and finishes only at the central depot(2)
Every customer can be served by one and only one vehicle(3)
The total demand must not exceed the capacity of the vehicle(4)
Each customer must be served in the related hard time window(5)
If the vehicle arrives early at the customeri, it can wait until the time instant to start serviceThe VRPSTW can then be stated mathematically as follows:(5)Min∑k,i,jci,jdsi,jxk,i,j+∑ipiyi,subject to(6)∑jxk,j,i−∑jxk,i,j=1;i=d,−1;i=o,0;otherwise,∀i∈N,∀k∈K,(7)∑k,jxk,i,j=1;∀i∈N∗,(8)xk,i,i=0;∀k∈K,∀i∈N,(9)∑i∈N∗di∑j∈Nxk,i,j≤qk;∀k∈K,(10)wi+ti,j+vi−wj≤1−xk,i,jmaxbi′+ti,j+vi−aj,0;∀i,j∈N,(11)ai≤wi≤bi′;∀i∈N,(12)yi=maxwi−bi,0;∀i∈N∗.We minimize the objective function (5) which consists of two components: the first component represents travel cost and the second component is the total penalties of the violation of soft time windows.The constraints (6) are the flow conservation of a vehicle. That is, for i=d, every vehicle ends only once at the depot and no arc originates from node d; for i=o, every vehicle starts only once at the depot and no arc terminates at node o; and i∈N∗ indicates that exactly one vehicle enters and leaves each customer node.The constraints (7) require that each customer is serviced exactly once.The constraints (8) are the flow conservation constraints which describe the vehicle path.The constraints (9) ensure that the vehicle capacity constraint is not violated.The constraints (10) ensure feasibility of the time schedule.The constraints (11) assure that the starting time of services does not violate the given hard time windows.The constraints (12) are the violation of soft time windows.


### 3.2. The Robust Vehicle Routing with Soft Time Windows (RVRPSTW)

The approach for solving the robust discrete optimization VRPSTW with uncertain travel times is equivalent to the minimax optimization problem. We used a robust decision-making framework of Kouvelis and Yu [11] to find durable solutions. First, the uncertainty data are created by considering situations of travel time between depot and customers and the time to travel between each customer. Indeed, letS be the set of all possible scenariost be the travel time at base case scenariots be the travel time of each scenario s dependent on α such as 0≤α≤1, and ts selected randomly from ts∈1−αt,1+αtFs be the set of all possible solutions at each scenario s, and ∩Fs∈Ss≠∅X be the decision variable and X∈FsXs∗ be the optimal solution at each scenario sfX,ts is the function used for finding solution X of each scenarioZs be the optimal value at each scenario from Xs∗So that, for each situation, we must find the optimal valueZs from the aforementioned VRPSTW problem:(13)Zs=fXs∗,ts=minX∈FsfX,ts.Therefore, we can find the optimal value of each scenario by using equation (13). Notice, we solve problem (13) as many times as the number of scenarios. Then, equation (13) is a function to represent the robust counterpart.After we have the optimal value of VRPSTW for each scenario, the next step is to find the main goal of the minimax optimization problem, which is to find the robust optimal valueZ∗.We start by finding the highest valuehxS of all scenarios. The robust criteria that are considered are absolute robustness ZA as described in Definition 1, robust deviation ZD as described in Definition 2, and relative robustness ZR as described in Definition 3.After that, we select the robust solution from the results from all possible solutions that provide the lowest value that can be obtained in the event of the worst case.The robust vehicle routing with soft time windows (RVRPSTW) can then be stated as follows:(14)Z∗=minhXSgsX≤hXS;s∈S,X∈∩Fs∈Ss,subject to(15)gsX=fX,ts,for absolute robustness,fX,ts−Zs,for robust deviation,fX,ts−ZsZs,for relative robustness,where fX,ts is the function used for finding solution X of each scenario and Zs is the optimal value of VRPSTW for each scenario.Finally, we compared the performance of the three criteria by using the relative ratio:(16)P=Z∗−ZZ,where Z∗ is the robust solution ZA or ZD or ZR and Z is the solution of base case.The process to find RVRPSTW is summarized as follows:(1)
Construct a base case scenario by fixed travel timet.(2)
Generate all possible scenarios by percentage of uncertainty0≤α≤1 by selecting ts from 1−αt,1+αt.(3)
Find optimal valueZs and optimal solution Xs of each scenario s.(4)
Finding the highest valuehxS of all scenarios with the robust criteria:(17)gsX=fX,ts,for absolute robustness,fX,ts−Zs,for robust deviation,fX,ts−ZsZs,for relative robustness.(5)
FindX∗ which is the robust solution from(18)Z∗=minhXSgsX≤hXS;s∈S,X∈∩Fs∈Ss.(6)
Comparing the performance of the three criteria by using the relative ratioP=Z∗−Z/Z.


## 3.1. The Vehicle Routing Problems with Soft Time Windows (VRPSTW)

The VRPSTW is defined on a directed graphG=N,A, where N=o,d,1,2,3,…,n is a set of vertices (o,d is the depot) and A is a set of arcs i,j representing the connections between the depot and customers or among the customers A=i,ji,j∈N,i≠j.The following notations are introduced to formulate the mathematical model of VRPSTW.


### 3.1.1. Indices

i
,
j
,
n index of nodes
k index of vehicle


### 3.1.2. Sets

N
=
o
,
d
,
1,2,3
,
…
,
n be a node set (o is origin and d is destination)
N
∗
=
N
−
o
,
d be a set of customers
K
=
1,2,3
,
…
,
k be a set of vehicles


### 3.1.3. Decision Variables

x
k
,
i
,
j
=
1
;
if vehicle
k
travels directly from node
i
to
j
;
0
;
otherwise
y
i is the violation degree of the upper bound of soft time windows at the customer i
w
i be the arrival time at the customer i


### 3.1.4. Input Parameters

c
i
,
j be the travel cost from i to j
t
i
,
j be a time from node i to j
x
c
i be the coordinate x of i
y
c
i be the coordinate y of i,
d
s
i
,
j be a distance between customers i and j dsi,j=xci−xcj2+yci−ycj2
d
i be the demand of the customer i, and pi be penalty cost per hour for the lateness of customer i
a
i be the early time to service the node i without penalty
b
i be the last time to service the note i without penalty
b
i
′ be the last time to service the node i with penalty
v
i be a service time at the customer i
q
k be the capacity of the vehicle kThe solution to the VRPSTW must satisfy the following:(1)
Every vehicle starts and finishes only at the central depot(2)
Every customer can be served by one and only one vehicle(3)
The total demand must not exceed the capacity of the vehicle(4)
Each customer must be served in the related hard time window(5)
If the vehicle arrives early at the customeri, it can wait until the time instant to start serviceThe VRPSTW can then be stated mathematically as follows:(5)Min∑k,i,jci,jdsi,jxk,i,j+∑ipiyi,subject to(6)∑jxk,j,i−∑jxk,i,j=1;i=d,−1;i=o,0;otherwise,∀i∈N,∀k∈K,(7)∑k,jxk,i,j=1;∀i∈N∗,(8)xk,i,i=0;∀k∈K,∀i∈N,(9)∑i∈N∗di∑j∈Nxk,i,j≤qk;∀k∈K,(10)wi+ti,j+vi−wj≤1−xk,i,jmaxbi′+ti,j+vi−aj,0;∀i,j∈N,(11)ai≤wi≤bi′;∀i∈N,(12)yi=maxwi−bi,0;∀i∈N∗.We minimize the objective function (5) which consists of two components: the first component represents travel cost and the second component is the total penalties of the violation of soft time windows.The constraints (6) are the flow conservation of a vehicle. That is, for i=d, every vehicle ends only once at the depot and no arc originates from node d; for i=o, every vehicle starts only once at the depot and no arc terminates at node o; and i∈N∗ indicates that exactly one vehicle enters and leaves each customer node.The constraints (7) require that each customer is serviced exactly once.The constraints (8) are the flow conservation constraints which describe the vehicle path.The constraints (9) ensure that the vehicle capacity constraint is not violated.The constraints (10) ensure feasibility of the time schedule.The constraints (11) assure that the starting time of services does not violate the given hard time windows.The constraints (12) are the violation of soft time windows.


## 3.1.1. Indices

i
,
j
,
n index of nodes
k index of vehicle


## 3.1.2. Sets

N
=
o
,
d
,
1,2,3
,
…
,
n be a node set (o is origin and d is destination)
N
∗
=
N
−
o
,
d be a set of customers
K
=
1,2,3
,
…
,
k be a set of vehicles


## 3.1.3. Decision Variables

x
k
,
i
,
j
=
1
;
if vehicle
k
travels directly from node
i
to
j
;
0
;
otherwise
y
i is the violation degree of the upper bound of soft time windows at the customer i
w
i be the arrival time at the customer i


## 3.1.4. Input Parameters

c
i
,
j be the travel cost from i to j
t
i
,
j be a time from node i to j
x
c
i be the coordinate x of i
y
c
i be the coordinate y of i,
d
s
i
,
j be a distance between customers i and j dsi,j=xci−xcj2+yci−ycj2
d
i be the demand of the customer i, and pi be penalty cost per hour for the lateness of customer i
a
i be the early time to service the node i without penalty
b
i be the last time to service the note i without penalty
b
i
′ be the last time to service the node i with penalty
v
i be a service time at the customer i
q
k be the capacity of the vehicle kThe solution to the VRPSTW must satisfy the following:(1)
Every vehicle starts and finishes only at the central depot(2)
Every customer can be served by one and only one vehicle(3)
The total demand must not exceed the capacity of the vehicle(4)
Each customer must be served in the related hard time window(5)
If the vehicle arrives early at the customeri, it can wait until the time instant to start serviceThe VRPSTW can then be stated mathematically as follows:(5)Min∑k,i,jci,jdsi,jxk,i,j+∑ipiyi,subject to(6)∑jxk,j,i−∑jxk,i,j=1;i=d,−1;i=o,0;otherwise,∀i∈N,∀k∈K,(7)∑k,jxk,i,j=1;∀i∈N∗,(8)xk,i,i=0;∀k∈K,∀i∈N,(9)∑i∈N∗di∑j∈Nxk,i,j≤qk;∀k∈K,(10)wi+ti,j+vi−wj≤1−xk,i,jmaxbi′+ti,j+vi−aj,0;∀i,j∈N,(11)ai≤wi≤bi′;∀i∈N,(12)yi=maxwi−bi,0;∀i∈N∗.We minimize the objective function (5) which consists of two components: the first component represents travel cost and the second component is the total penalties of the violation of soft time windows.The constraints (6) are the flow conservation of a vehicle. That is, for i=d, every vehicle ends only once at the depot and no arc originates from node d; for i=o, every vehicle starts only once at the depot and no arc terminates at node o; and i∈N∗ indicates that exactly one vehicle enters and leaves each customer node.The constraints (7) require that each customer is serviced exactly once.The constraints (8) are the flow conservation constraints which describe the vehicle path.The constraints (9) ensure that the vehicle capacity constraint is not violated.The constraints (10) ensure feasibility of the time schedule.The constraints (11) assure that the starting time of services does not violate the given hard time windows.The constraints (12) are the violation of soft time windows.


## 3.2. The Robust Vehicle Routing with Soft Time Windows (RVRPSTW)

The approach for solving the robust discrete optimization VRPSTW with uncertain travel times is equivalent to the minimax optimization problem. We used a robust decision-making framework of Kouvelis and Yu [11] to find durable solutions. First, the uncertainty data are created by considering situations of travel time between depot and customers and the time to travel between each customer. Indeed, letS be the set of all possible scenariost be the travel time at base case scenariots be the travel time of each scenario s dependent on α such as 0≤α≤1, and ts selected randomly from ts∈1−αt,1+αtFs be the set of all possible solutions at each scenario s, and ∩Fs∈Ss≠∅X be the decision variable and X∈FsXs∗ be the optimal solution at each scenario sfX,ts is the function used for finding solution X of each scenarioZs be the optimal value at each scenario from Xs∗So that, for each situation, we must find the optimal valueZs from the aforementioned VRPSTW problem:(13)Zs=fXs∗,ts=minX∈FsfX,ts.Therefore, we can find the optimal value of each scenario by using equation (13). Notice, we solve problem (13) as many times as the number of scenarios. Then, equation (13) is a function to represent the robust counterpart.After we have the optimal value of VRPSTW for each scenario, the next step is to find the main goal of the minimax optimization problem, which is to find the robust optimal valueZ∗.We start by finding the highest valuehxS of all scenarios. The robust criteria that are considered are absolute robustness ZA as described in Definition 1, robust deviation ZD as described in Definition 2, and relative robustness ZR as described in Definition 3.After that, we select the robust solution from the results from all possible solutions that provide the lowest value that can be obtained in the event of the worst case.The robust vehicle routing with soft time windows (RVRPSTW) can then be stated as follows:(14)Z∗=minhXSgsX≤hXS;s∈S,X∈∩Fs∈Ss,subject to(15)gsX=fX,ts,for absolute robustness,fX,ts−Zs,for robust deviation,fX,ts−ZsZs,for relative robustness,where fX,ts is the function used for finding solution X of each scenario and Zs is the optimal value of VRPSTW for each scenario.Finally, we compared the performance of the three criteria by using the relative ratio:(16)P=Z∗−ZZ,where Z∗ is the robust solution ZA or ZD or ZR and Z is the solution of base case.The process to find RVRPSTW is summarized as follows:(1)
Construct a base case scenario by fixed travel timet.(2)
Generate all possible scenarios by percentage of uncertainty0≤α≤1 by selecting ts from 1−αt,1+αt.(3)
Find optimal valueZs and optimal solution Xs of each scenario s.(4)
Finding the highest valuehxS of all scenarios with the robust criteria:(17)gsX=fX,ts,for absolute robustness,fX,ts−Zs,for robust deviation,fX,ts−ZsZs,for relative robustness.(5)
FindX∗ which is the robust solution from(18)Z∗=minhXSgsX≤hXS;s∈S,X∈∩Fs∈Ss.(6)
Comparing the performance of the three criteria by using the relative ratioP=Z∗−Z/Z.


## 4. Results and Discussion

This demonstration uses benchmarking problem of Solomon’s VRPTW [7]. We randomly generate soft time windows in VRPSTW from the time frames of VRPTW. Solomon’s VRPSTW divides the problem into 6 types of instances, including type R1, R2, C1, C2, RC1, and RC2. In this study, we find the robust solution of R101, C101, RC101, R201, C201, and RC201 with the number of customers equal to 25. The number of scenarios is generated randomly into intervals of travel time, equal to 4, 6, and 8 instances for each problem set. Each set of problem instances can be denoted by the percentage of uncertainty α, equal to 0.2, 0.4, 0.6, and 0.8.We examine the robust solution of case R101 by using 6 as the number of scenarios and 0.4 asα in order to observe the behavior of the robust solution. We import data from Solomon’s VRPSTW problem, and let ci,j=1, pi=1, and bi′=bi+20. From these imported data, we have coded and solved VRPSTW by using AIMMS 4.9. The results are given in Tables 1–4.Table 1
The optimal value of each scenario.
Base case
s
1
s
2
s
3
s
4
s
5
s
6
Z
s
608.832
590.996
601.373
614.277
620.412
589.587
596.467Table 2
The absolute robustnessZA.
Solutions
Scenarios
h
X
i
∗
S
g
s
1
X
i
∗
g
s
2
X
i
∗
g
s
3
X
i
∗
g
s
4
X
i
∗
g
s
5
X
i
∗
g
s
6
X
i
∗
X
1
∗
590.996
602.278
617.482
635.623
589.587
597.210
635.623
X
2
∗
592.897
601.373
618.865
643.133
592.149
596.467
643.133
X
3
∗
598.923
604.639
614.277
625.051
598.443
601.427
625.051
X
4
∗
618.330
618.330
618.330
620.412
618.330
618.330
620.412
X
5
∗
590.996
602.278
617.482
635.623
589.587
597.210
635.623
X
6
∗
592.897
601.373
618.865
643.133
592.149
596.467
643.133
Z
A =
620.412Table 3
The robust deviationZD.
Solutions
Scenarios
h
X
i
∗
S
g
s
1
X
i
∗
g
s
2
X
i
∗
g
s
3
X
i
∗
g
s
1
X
i
∗
g
s
2
X
i
∗
g
s
6
X
i
∗
X
1
∗
0
0.9054
3.2054
15.2109
0
0.7432
15.2109
X
2
∗
1.9012
0
4.5882
22.7209
2.5623
0
22.7209
X
3
∗
7.9277
3.2665
0
4.6388
8.8555
4.9598
8.8555
X
4
∗
27.3343
16.9572
4.0530
0
28.7428
21.8631
28.7428
X
5
∗
0
0.9054
3.2054
15.2109
0
0.7432
15.2109
X
6
∗
1.9012
0
4.5882
22.7209
2.5623
0
22.7209
Z
D =
8.8555Table 4
The relative robustnessZR.
Solutions
Scenarios
h
X
i
∗
S
g
s
1
X
i
∗
g
s
2
X
i
∗
g
s
3
X
i
∗
g
s
4
X
i
∗
g
s
5
X
i
∗
g
s
6
X
i
∗
X
1
∗
0
0.0015
0.0052
0.0245
0
0.0012
0.0245
X
2
∗
0.0032
0
0.0075
0.0366
0.0043
0
0.0366
X
3
∗
0.0134
0.0054
0
0.0075
0.0150
0.0083
0.0150
X
4
∗
0.0463
0.0282
0.0066
0
0.04875
0.0367
0.0488
X
5
∗
0
0.0015
0.0052
0.0245
0
0.0012
0.0245
X
6
∗
0.00327
0
0.0075
0.0366
0.0043
0
0.0366
Z
R =
0.0150Next, we present the minimax optimization problem, which is to find the robust optimal value.From the minimax optimization problem shown in Tables2–4, we can conclude the process and show the results in Table 5.Table 5
The result of RVRPSTW.
Criteria
Robust optimal value
Robust optimal solution
Cost
Relative ratio
Z
A
620.4120246
X
4
∗
620.4120246
0.018665753
Z
D
8.8554838
X
3
∗
598.4425665
−0.017063834
Z
R
0.015019806
X
3
∗
598.4425665
−0.017360063In addition, we consider the cost for the robust solution of the problem R101 when the number of scenarios is 4, 6, and 8. The percentage of uncertaintyα is equal to 0.2, 0.4, 0.6, and 0.8. The results are given in Tables 6–8.Table 6
The optimal value of base case problem for each percentage of uncertaintyα.
α
0.2
0.4
0.6
0.8
Optimal value
597.6814133
608.8315627
618.3299155
621.316885Table 7
The solution of RVRPSTW for R101.
Scenario
Cost
Z
A
Z
D
Z
R
S
=
4
α
=
0.2
608.7279786
610.4065438
610.4065438
α
=
0.4
620.4120246
598.9233066
598.9233066
α
=
0.6
637.7034653
618.3299155
618.3299155
α
=
0.8
672.1878165
628.1196809
628.1196809
S
=
6
α
=
0.2
609.8976676
611.9471293
611.9471293
α
=
0.4
620.4120246
598.4425665
598.4425665
α
=
0.6
637.7034653
618.3299155
618.3299155
α
=
0.8
672.1878165
628.1196809
628.1196809
S
=
8
α
=
0.2
609.8976676
611.9471293
611.9471293
α
=
0.4
621.0159409
598.4425665
598.4425665
α
=
0.6
637.7034653
618.3299155
618.3299155
α
=
0.8
672.1878165
628.1196809
628.1196809Table 8
The ratioP of performance for robust criteria.
Scenario
Relative ratio
Z
A
Z
D
Z
R
S
=
4
α
=
0.2
0.018482364
0.021290825
0.021290825
α
=
0.4
0.019020798
−0.016274216
−0.016274216
α
=
0.6
0.03133206
0
0
α
=
0.8
0.081875984
0.010948996
0.010948996
S
=
6
α
=
0.2
0.020439408
0.023868428
0.023868428
α
=
0.4
0.019020798
−0.017063827
−0.017063827
α
=
0.6
0.03133206
0
0
α
=
0.8
0.081875984
0.010948996
0.010948996
S
=
8
α
=
0.2
0.020439408
0.023868428
0.023868428
α
=
0.4
0.020012724
−0.017063827
−0.017063827
α
=
0.6
0.03133206
0
0
α
=
0.8
0.081875984
0.010948996
0.010948996In the comparison between solutions from the robust criteria, we found that the important parameter that affects the solutions is the uncertainty percentageα. The results in Table 6 show that when the uncertainty percentage α increases from 0.2 to 0.8, the optimal values are also increased. This is because the travel time in each route is determined by the minimum and maximum time periods. When the value of α increases, the ranges of times are wider, while the number of the scenarios does not impact the robust optimal value. From Table 7, we can see that when the number of the scenarios increases, the optimal value has little change and no tendency to increase. We study in the other types of Solomon problems that the result of all problems shows the same trend. Therefore, determining the number of the scenarios is not an important factor affecting the quality of the experiment’s results. From Table 8, the ratio P of performance for robust criteria clearly shows that the good decision criteria for this study are robust deviation and relative robustness. They provide the best performance for these situations.


## 5. Conclusions

In this study, we present a mathematical model of RVRPSTW to find the robust solution that provides the best of the worst case performance for VRPSTW under uncertain travel times. From the experiment, we found that the important parameter that affects the solutions is uncertainty percentage. The scenarios do not impact the robust optimal value. The good decision criteria for this study are robust deviation and relative robustness. The selection of different criteria creates different solutions which are appropriated depending on the purpose of the decision maker. The important thing for the decision maker is to determine the uncertainty percentage to cover all the uncertainties that need to be considered. In summary, the results in this paper can benefit the decision maker to make a decision for the same problem.



---

*Source: 9137458-2019-10-23.xml*