Journal of Industrial Engineering and Management Science

Vol: 2017    Issue: 1

Published In:   January 2018

A Multi-Depot Logistics Distribution Routing Model for Unexpected Events

Article No: 10    Page: 207-224    doi: 10.13052/jiems2446-1822.2017.010    

Read other article:
1 2 3 4 5 6 7 8 9 10 11 12 13

A Multi-Depot Logistics Distribution Routing Model for Unexpected Events

Xiaoxia Huang1,*, Liying Song1 and Hongqing Song2

  • 1Donlinks School of Economics and Management, University of Science and Technology Beijing, Beijing, China 100083
  • 2School of Civil and Enviromental Engineering, University of Science and Technology Beijing, Beijing, China 100083

*Corresponding Author: hxiaoxia@manage.ustb.edu.cn

Received 15 August 2017; Accepted 3 September 2017;
Publication 27 October 2017

Abstract

This paper discusses a multi-depot vehicle routing problem for dispatching vehicles in multi-depots to send relief material to the affected areas in unexpected events. Due to the occurrence of the unexpected events, people’s demands in the affected areas and the vehicles’ travel times on roads lack historical data and are given by experts’ estimations. Uncertain variables are used to describe these parameters. By using uncertainty theory, a multi-depot logistics distribution routing model is developed. To solve the problem, the equivalent of the proposed model is also presented. As an illustration, an example is also presented and discussed.

Keywords

  • Multi-depot vehicle routing problem
  • emergency logistics
  • uncertain programming
  • uncertainty theory
  • genetic algorithm

1 Introduction

Unexpected destructive events always cause great losses to human beings. Logistics plays an important role in mitigating pains and losses in these unexpected events and has attracted many scholars’ attention. The first study on logistics models for unexpected events was in the late 1970s aiming at handling the maritime disasters in the late 1960s and 1970s. Most early models were developed for dealing with oil spills or maritime disasters, e.g., Charnes et al. (1976), Psaraftis and Ziogas (1985), etc. Later, research has extended to explore more logistics distribution problems concerning a variety of disaster events such as earthquakes (Viswanath and Peeta, 2003; Linet et al., 2004), hurricanes (Lodree and Taskin, 2009; Horner and Down, 2010), floods (Garrido, et al., 2015), and man-made catastrophes (Wang, et al., 2012).

In the past, studies concerning logistics distribution for unexpected events mainly focused on addressing the specialness of the problem from normal logistics distribution and the way to handle it. Some examples include Yuan and Wang (2009) and Zhang, et al. (2013) who studied distribution routing problems for logistics with travel speed varying with time due to occurrence of the disasters, Zhang et al. (2012) who proposed a mixed integer programming model to handle primary and secondary disasters, and Liberatore et al. (2014) who proposed a method for repairing a broken transportation network for distribution of relief, etc. However, the authors argue that the greatest speciality of the problem should lie in the feature that no past data about the parameters are available because the events are unexpected and unusual. Then in the situation, all available are experts’ estimations about the parameters. Those estimations cannot be exact numbers. Since men’s estimations are not random in nature, men’s estimations can be quite different from probabilities either (Tversky and Kahneman,1974). In order to model men’s estimations, Liu (2007) proposed an uncertainty theory and further refined it (Liu, 2010). Along with the introduction and development of uncertainty theory, the application of the theory has also been researched. Some important works include Liu (2009b) who proposed the uncertain programming, and Huang (2010) who proposed an uncertain portfolio selection theory by introducing uncertainty theory into portfolio selection. So far, uncertainty theory has been applied to solve optimization problems concerning belief degrees in a variety of fields, e.g., in shortest path (Gao, 2011), inventory (Qin and Kar, 2013), production planning (Ning, et al., 2013), finance (Huang and Zhao, 2014a), capital budgeting (Zhang, et al., 2011; Zhang, et al., 2015), project selection and scheduling (Huang and Zhao, 2014b), and facility location problems (Gao, 2012; Huang and Di, 2015), etc. In this paper, we will use uncertainty theory to explore a multi-depot logistics distribution problem in unexpected events in which travel times on road and the demands of the affected areas are uncertain and given by experts’ estimations.

The paper proceeds as follows. For easy understanding of the paper, we will briefly review the fundamentals of uncertainty theory in Section 2. In Section 3 we will propose a multi-depot logistics distribution routing model for unexpected events. In order to solve the problem, we will also present the model equivalent in the section. Finally, we will conclude the paper.

2 Fundamentals of Uncertainty Theory

Uncertainty theory is a branch of mathematics based on the following four axioms.

Definition 1 Let L be a σ-algebra over a nonempty set Γ. Each element Λ ∈ L is called an event. A set function M{Λ} is called an uncertain measure if it satisfies the following four axioms (Liu, 2007; 2009a):

  1. M{Γ} = 1.
  2. M{Λ} + Mc} = 1.
  3. For every countable sequence of events{Λi}, we have

    M{ i=1Λi }i=1M{Λi}.

    The triplet (Γ,L,M) is called an uncertainty space.

  4. Let (Γk,Lk,Mk) be uncertainty spaces for k = 1,2,… The product uncertain measure is

    M{ k=1Λk }=Λk=1Mk{Λk}

    where Λk are arbitrarily chosen events from Lk for k = 1,2,…, respectively.

Definition 2 (Liu, 2007) An uncertain variable is a measurable function ξ from an uncertainty space (Γ,L,M) to the set of real numbers.

Definition 3 (Liu, 2007) The uncertainty distribution Φ : ℜ→ [0,1] of an uncertain variable ξ is defined by

Φ(t)=M{ξt}.

In application, an uncertain variable is characterized by an uncertainty distribution function. Regarding the way to obtain the uncertainty distribution function via experts’ estimations, please refer to Liu (2010), Huang (2012) and Huang and Zhao (2016).

Definition 4 (Liu, 2010) An uncertainty distribution Φ(t) is said to be regular if it is a continuous and strictly increasing function with respect to t at which 0 < Φ(t) < 1, and

limtΦ(t)=0,limt+Φ(t)=1.

To measure the size of an uncertain variable, the expected value of the uncertain variable is defined as follows.

Definition 5 (Liu, 2007) The expected value of an uncertain variable ξ is defined by

E[ξ]=0M{ξr}dr0M{ξr}dr(1)

provided that at least one of the two integrals is finite.

The operational law of the uncertain variables is given by Liu (2010) as follows:

Theorem 1 (Liu, 2010) Let ξ12,…,ξn be independent uncertain variables with regular uncertainty distributions Φ12,…,Φn, respectively. If f(t1,t2,…,tn) is strictly increasing with respect to t1,t2,…,tn, then

ξ=f(ξ1,ξ2,,ξn)

is an uncertain variable that has the following inverse uncertainty distribution function

Ψ1(α)=f(Φ11(α),Φ21(α),,Φn1(α)),0<α<1.(2)

Theorem 2 (Liu, 2010) Let ξ and η be independent uncertain variables with finite expected values. Then for any real numbers a and b, we have

E[aξ+bη]=aE[ξ]+bE[η].(3)

3 A Multi-Depot Logistics Distribution Routing Modelfor Unexpected Events

In the problem, suppose we have p numbers of depots, each having m vehicles. The decision maker (DM) needs to dispatch vehicles to distribute relief material from the p depots to the n affected areas. The affected areas’ demands and the travel times on roads are uncertain and lack historical data because of the impact of the accidents. Therefore, these parameter values are estimated by experts and treated as uncertain variables in the paper. Assume that (1) total vehicles in p depots can fully serve all the n numbers of affected areas but none of one depot can individually serve them well; (2) each vehicle begins and ends both at its own depot; (3) the vehicles will leave for the affected areas immediately once they receive the order so that they can send the material to the affected areas as early as possible; (4) the relief material will be unloaded immediately when it arrives at the affected areas; (5) each affected area will be served by one and only one vehicle; (6) a vehicle will serve only one route on which there may be several affected areas.

For expression convenience, the model parameters are introduced as follows.

D1,D2,…,Dp : the depots;

i = 1,2,…,n : the affected areas;

j = 1,2,…,m,m + 1,…,pm : vehicles, among which the vehicles 1,2,…,m belong to the 1st depot, the vehicles m + 1,m + 2,…,2m belong to the 2nd depot, …, and the vehicles (p - 1)m + 1,(p - 1)m + 2,…,pm belong to the p-th depot;

Qj : the capacities of vehicles j,j = 1,2,…,m,…,pm;

SDk : the inventory levels of the relief material of the depots Dk,k = 1,2,…,p;

Tik : the travel times from the depots i to the affected areas k,i = D1,D2,…,Dp,k = 1,2,…,n, which are uncertain variables;

tik : the travel times from the areas i to k,i,k = 1,2,…,n, which are uncertain variables;

di : the demands at affected areas i,i = 1,2,…,n, which are uncertain variables;

Ui : the unloading times at affected areas i,i = 1,2,…,n;

We use two decision vectors x and y to describe a routing plan. The vector x = (x1,x2,…, xn) is an integer vector representing n affected areas with 1 ≤ xin and xixk for all ik,i,k = 1,2,…,n. That is, x is the sequence of a rearrangement of {1,2,…,n}. The vector y = (y1,y2,…,ym,ym+1,…,ypm-1) is another integer vector with y0 ≡ 0 ≤ y1y2 ≤…≤ ymym+1 ≤…≤ ypm-1 ≤ n ≡ ypm. A routing plan is thus determined as follows: For each j,1 ≤ jpm, if yj = yj-1, the vehicle j is not used; if yj > yj-1 and (k - 1)m < jkm for 1 ≤ kp the vehicle j is used and starts at the k-th depot, and the routing of the vehicle j is

Dkxyj1+1xyj1+2xyjDk.

It is seen that the above two decision vectors x and y together ensure that (1) each vehicle will be used at most one time; (2) each vehicle routing begins and ends at this vehicle’s own depot; (3) each area will be served by one and only one vehicle; and (4) no sub-routing exists.

Let fi(x,y) denote the arrival times at areas i under the routing plan of (x,y). Then if vehicle j at depot k is used, i.e., if yj > yj-1 and (k - 1)m < j ≤ km for 1 ≤ k ≤ p, the arrival time of this vehicle at the area xyj-1+1 is

fxyj1+1(x,y)=T˜Dkxyj1+1,(4)

and the arrival times at the areas xyj-1+l,2 ≤ l ≤ yj - yj-1 are

fxyj1+l(x,y)=fxyj1+l1(x,y)+Uxyj1+l1    +t˜xyj1+l1xyj1+l.(5)

Let ui be the unloading time of unit material at areas i,i = 1,2,…,n. Then the Equation (5) becomes

fxyj1+l(x,y)=fxyj1+l1(x,y)+d˜xyj1+l1·uxyj1+l1      +t˜xyj1+l1xyj1+l.(6)

Thus the total arrival time at the n areas is

T=i=1nfi(x,y).(7)

Since the Tik’s, tik’s and ui’s in (4) and (6) are uncertain variables, the total arrival time T is also uncertain and cannot be minimized directly. Then the DM can set the objective as minimizing the expected value of the total arrival time, i.e., the DM can set the objective as

minE[i=1nfi(x,y)]

where fi(x,y) are determined by Equations (4) and (6).

When making routing plan, the DM must consider the vehicle capacity constraints and the depot inventory level constraints. Since the demands di at areas i,i = 1,2,…,n, are uncertain, the DM can ask that the total demands in a route should not exceed the capacity of the vehicle serving the route at a preset high enough confidence level β. That is, we can express the vehicle capacity constraints mathematically as follows,

M{i=yj1+1yjd˜xiQj}β,j=1,2,,pm.(8)

In the meantime, it should be ensured that the depot inventory level of the relief material can satisfy the amount of the material sent out by the vehicles from the depot at a preset high enough confidence level β′. That is,

M{j=(k1)m+1kmi=yj1+1yjd˜xiSDk}β,k=1,2,,p.(9)

Thus, if the DM wants to minimize the expected value of the total arrival time at all affected areas subject to the vehicle capacity constraints and the depot inventory level constraints, he or she can dispatch the vehicles in p depots according the following model:

{ minE[i=1nfi(x,y)]subject to:  M{i=yj1+1yjd˜xiQj}β,j=1,2,,pm  M{j=(k1)m+1kmi=yj1+1yjd˜xiSDk}β,  k=1,2,,p  1xin,i=1,2,,n,xixk,  ik,i,k=1,2,,n  0y1y2ypm1n  xi,yj,i=1,2,,n,j=1,2,,pm1,integers (10)

where fi(x,y) are determined by Equations (4) and (6) for i = 1,2,…,n.

Theorem 3 Suppose the travel times Tik,i = D1,D2,…,Dp,k = 1,2,…,n, and tik,i,k = 1,2,…,n, and the uncertain demands di at areas i,i = 1,2,…,n, are independent and have regular uncertainty distributions. Let eDk⋅i,k = 1,2,…,p,i = 1,2,…,n denote the expected values of the travel times between the depots Dk and the affected areas i and μij,i≠j,i,j = 1,2,…,n the expected values of the travel times between the affected areas i and j. Let edi,i = 1,2,…,n the expected values of the demands at areas i, and Φi denote the regular uncertainty distributions of the uncertain demands di for i = 1,2,…,n. Then the model (10) is equivalent to the following model:

{ mini=1nE[fi(x,y)]subject to:  i=yj1+1yjΦxi1(β)Qj,j=1,2,,pmj=(k1)m+1kmi=yj1+1yjΦxi1(β)SDk,k=1,2,,p  1xin,i=1,2,,n,xixk,  ik,i,k=1,2,,n  0y1y2ypm1n  xi,yj,i=1,2,,n,j=1,2,,pm1,integers (11)

where E[fi(x,y)] are obtained from the following equations

E[fxyj1+1(x,y)]=eDk,xyj1+1,k=1,2,,p,(k1)m<jkm(12)

and for 2 ≤ l ≤ yj - yj-1,

E[fxyj1+l(x,y)]=E[fxyj1+l1(x,y)]+uxyj1+l1·exyj1+l1+μxyj1+l1xyj1+l.(13)

Proof: From Equations (4) and (6) we know that the formula i=1nfi(x,y) is the sum function of independent uncertain variables Tik for i = D1,D2,…,Dp,k = 1,2,…,n, tik for i,k = 1,2,…,n, and di for i = 1,2,…,n. Therefore, from Theorem 2 we get that E[i=1nfi(x,y)]=i=1nE[fi(x,y)]..

Since i=yj1+1yjdxi˜ is strictly increasing with respect to dxi, according to Theorem 1 we can get that the inverse uncertainty distribution of the total demand amount served by vehicle j, i.e., the inverse uncertainty distribution of i=yj1+1yjdxi˜ at β is

i=yj1+1yjΦxi1(β),j=1,2,,pm.

Then from the increasing property of the uncertainty measure we can get that the vehicle capacity constraint (8) can be converted into the following form:

i=yj1+1yjΦxi1(β)Qj,j=1,2,,pm.

Similarly, the depot inventory level constraint (9) can be converted into the following form:

j=(k1)m+1kmi=yj1+1yjΦxi1(β)SDk,k=1,2,,p.

Thus, the theorem is proved.

Huang and Song (2016) provided a cellular integrated genetic algorithm (CGA) to solve a single depot emergency logistics distribution routing problem. We revise the algorithm to solve the problem of model (11).

4 An Example

A rural emergency command center has 2 distribution depots with each depot having 6 vehicles. The capacities of the 12 vehicles are given in Table 1 where vehicles 1 to 6 belong to depot 1 and vehicles 7 to 12 belong to depot 2.Depots 1 and 2 both have 7500 kg inventory of relief material. The center is responsible for 30 areas material distribution in the case of unexpected events. When an unexpected event happens, the center must decide how to dispatch vehicles in the two depots to send needed materials to the affected areas. Though lacking historical data, experts can take likely chaos, traffic jams and other bad situations into account to estimate the road travel times of vehicles from each depot to the affected areas and the times from one area to another area. Suppose the experts believe these parameters are normal uncertain variables and present their estimations in Tables 2 and 4. In Table 2, D1 represents depot 1 and D2 depot 2. In addition, the experts estimate the people’s demands in the affected areas according to the judgement on the severity of the accident and present them in Table 3.

Table 1 Vehicle capacities (kilogram)

Vehicle 1 2 3 4 5 6 7 8 9 10 11 12
Capacity 1000 1100 1200 1300 1400 1500 1000 1100 1200 1300 1400 1500

Table 2 Normal uncertain travel times between depots and the affected areas (μ,σ) (minute)

LCTs 1 2 3 4 5 6 7 8 9 10
D1 (40,10) (50,5) (50,10) (55,10) (55,10) (50,10) (30,10) (55,10) (45,10) (46,10)
D2 (60,5) (38,10) (65,15) (70,15) (60,10) (45,10) (60,10) (50,10) (45,10) (50,10)
LCTs 11 12 13 14 15 16 17 18 19 20
D1 (40,10) (35,10) (50,10) (50,15) (55,10) (50,10) (65,10) (55,10) (45,10) (42,10)
D2 (70,5) (50,10) (65,15) (70,10) (60,10) (45,10) (60,10) (50,10) (45,10) (50,10)
LCTs 21 22 23 24 25 26 27 28 29 30
D1 (45,10) (45,10) (50,10) (55,15) (55,10) (50,10) (50,5) (55,10) (45,10) (40,10)
D2 (35,5) (50,10) (65,15) (70,10) (60,10) (45,10) (60,10) (50,10) (45,10) (45,5)

Table 3 The normal uncertain demands (μ′,σ′) (kilogram)

Affected Area Demand Affected Area Demand Affected Area Demand
1 (230,20) 11 (240,25) 21 (240,25)
2 (300,21) 12 (220,25) 22 (310,30)
3 (215,25) 13 (300,35) 23 (240,25)
4 (360,30) 14 (195,25) 24 (290,25)
5 (190,25) 15 (200,20) 25 (320,30)
6 (190,35) 16 (260,30) 26 (240,25)
7 (410,35) 17 (210,20) 27 (370,35)
8 (220,30) 18 (375,30) 28 (330,30)
9 (410,35) 19 (300,20) 29 (260,20)
10 (220,30) 20 (375,30) 30 (280,35)

Table 4 Normal uncertain travel times between two affected areas (μ,σ) (minute)

LCTs 1 2 3 4 5 6 7 8 9 10
2 (15,7)
3 (40,15) (25,10)
4 (45,10) (20,10) (27,12)
5 (40,10) (27,10) (25,10) (50,15)
6 (20,10) (50,10) (25,5) (20,10) (26,10)
7 (35,10) (25,10) (27,10) (25,10) (25,5) (20,7)
8 (20,15) (30,5) (25,10) (35,10) (25,5) (27,10) (23,10)
9 (55,15) (20,10) (30,10) (30,10) (26,10) (25,7) (27,5) (30,12)
10 (15,5) (27,10) (35,10) (30,10) (30,10) (30,10) (26,5) (27,10) (25,10)
11 (65,15) (30,15) (35,15) (25,10) (40,12) (20,10) (27,12) (25,10) (20,10) (25,10)
12 (15,5) (25,10) (25,5) (45,15) (30,10) (27,10) (25,10) (30,10) (30,15) (20,10)
13 (65,20) (25,10) (40,15) (35,10) (25,10) (35,15) (23,10) (35,14) (15,5) (15,10)
14 (20,15) (30,12) (50,20) (40,15) (27,10) (45,14) (30,14) (25,10) (20,10) (10,5)
15 (65,15) (35,10) (26,10) (50,20) (65,10) (40,10) (27,12) (30,12) (20,10) (25,10)
16 (55,10) (45,10) (30,10) (35,14) (35,10) (30,10) (27,12) (35,10) (25,10) (20,10)
17 (15,5) (25,10) (35,10) (55,15) (30,10) (25,10) (30,10) (27,10) (25,10) (15,10)
18 (55,10) (20,10) (30,12) (30,10) (25,10) (25,7) (27,5) (30,12) (20,10) (10,5)
19 (15,5) (27,10) (35,12) (30,15) (30,10) (30,10) (26,5) (27,10) (30,15) (25,10)
20 (65,10) (30,15) (35,15) (25,10) (40,12) (20,10) (27,12) (25,10) (15,5) (20,10)
21 (15,10) (20,10) (25,10) (45,15) (30,14) (27,10) (25,10) (30,10) (20,10) (15,10)
22 (65,15) (25,10) (40,15) (35,15) (25,10) (35,15) (23,10) (35,14) (20,10) (10,5)
23 (20,15) (30,10) (50,20) (40,10) (27,10) (45,14) (30,14) (25,10) (25,10) (25,10)
24 (65,15) (95,30) (85,30) (120,50) (65,25) (100,30) (80,35) (90,35) (75,30) (70,25)
25 (55,10) (65,10) (30,10) (35,15) (35,10) (30,10) (27,12) (35,10) (20,10) (15,10)
26 (15,5) (25,10) (35,14) (55,20) (30,10) (25,10) (30,10) (27,10) (30,15) (10,5)
27 (20,15) (25,5) (50,20) (40,15) (27,10) (45,14) (30,14) (25,10) (15,5) (25,10)
28 (65,15) (35,10) (26,10) (50,20) (65,10) (40,10) (27,12) (30,12) (20,10) (20,10)
29 (55,10) (55,10) (30,10) (35,15) (35,10) (30,10) (27,12) (35,10) (20,10) (15,10)
30 (15,5) (23,10) (35,14) (55,10) (30,10) (25,10) (30,10) (27,10) (25,10) (10,5)
LCTs 11 12 13 14 15 16 17 18 19 20
12 (55,25)
13 (30,10) (45,7)
14 (15,7) (30,10) (20,10)
15 (65,10) (20,10) (25,10) (35,15)
16 (25,10) (15,5) (30,5) (40,20) (30,10)
17 (55,7) (25,5) (45,7) (30,5) (15,5) (26,12)
18 (20,10) (30,15) (35,10) (55,10) (25,5) (30,14) (25,10)
19 (20,7) (27,10) (65,10) (55,7) (23,10) (35,14) (23,10) (27,10)
20 (65,20) (30,10) (35,15) (25,10) (40,10) (20,10) (27,12) (25,10) (25,10)
21 (15,7) (26,10) (26,14) (45,15) (30,10) (27,10) (25,10) (30,10) (15,10) (15,5)
22 (65,15) (20,5) (40,14) (35,10) (25,10) (45,20) (23,10) (35,14) (15,10) (20,5)
23 (20,15) (30,12) (50,20) (40,10) (20,10) (45,15) (30,14) (25,10) (25,10) (25,10)
24 (65,15) (35,10) (26,10) (50,20) (65,20) (40,10) (27,10) (30,12) (10,5) (30,10)
25 (55,10) (55,15) (30,10) (35,15) (35,10) (30,10) (27,10) (35,10) (25,10) (35,10)
26 (15,7) (23,10) (35,14) (55,10) (30,10) (25,10) (30,10) (27,10) (15,10) (15,5)
27 (20,15) (30,12) (50,20) (40,14) (25,10) (45,15) (30,15) (25,10) (15,10) (20,5)
28 (65,15) (95,30) (85,30) (120,50) (65,25) (100,30) (80,35) (90,35) (75,30) (70,25)
29 (55,10) (65,10) (30,10) (35,15) (35,10) (30,10) (27,10) (30,12) (10,5) (30,10)
30 (15,7) (23,10) (35,14) (55,10) (30,10) (25,10) (30,10) (27,10) (25,10) (35,10)
LCTs 21 22 23 24 25 26 27 28 29
22 (65,7)
23 (20,15) (30,12)
24 (65,15) (35,10) (25,10)
25 (55,10) (60,10) (30,10) (35,14)
26 (15,7) (23,10) (35,14) (55,10) (30,10)
27 (20,15) (30,12) (50,20) (40,15) (25,10) (45,15)
28 (65,15) (35,10) (26,10) (50,15) (60,10) (40,10) (27,10)
29 (55,10) (45,10) (30,10) (35,10) (35,10) (30,10) (25,12) (35,10)
30 (15,7) (23,10) (35,14) (55,10) (30,10) (25,10) (30,10) (27,10) (25,5)

The manager of the center sets the confidence levels at β = 0.90 and β′ = 0.95. Running the algorithm (pop_size = 30,Pc = 0.6,Pm = 0.5, and the parameter in the rank based evaluation function ν = 0.05) 50,000 generations we get the optimal routing plan and present it in Table 5. The objective value is 1090 minutes.

Table 6 Optimal routing plan for twelve vehicles in two depots to thirty areas

Vehicles Vehicle Routing
Vehicle 1 D1 → 4 → D1
Vehicle 2 D1 → 14 → 10 → 25 → D1
Vehicle 3 D1 → 7 → D1
Vehicle 4 D1 → 3 → 28 → D1
Vehicle 5 D1 → 12 → 16 → D1
Vehicle 6 D1 → 22 → D1
Vehicle 7 D2 → 29 → 19 → 24 → D2
Vehicle 8 D2 → 26 → 11 → 18 → D2
Vehicle 9 D2 → 2 → 13 → 9 → D2
Vehicle 10 D2 → 21 → 20 → D2
Vehicle 11 D2 → 30 → 1 → 17 → 15 → 23 → D2
Vehicle 12 D2 → 6 → 5 → 8 → 27 → D2

Table 7 Optimal objective values with different Pc and Pm values in CGA (minutes)

Pop_size Pc Pm Objective Value Relative Error (%)
30 0.3 0.2 1108 1.65
30 0.4 0.4 1112 2.02
30 0.5 0.2 1119 2.67
30 0.6 0.5 1090 0.00
30 0.6 0.6 1098 0.73
30 0.7 0.4 1126 3.30
30 0.7 0.5 1114 2.20
30 0.7 0.7 1121 2.84
30 0.8 0.3 1109 1.74
30 0.8 0.4 1125 3.21
30 0.8 0.8 1111 1.93
30 0.9 0.3 1126 3.21
30 0.9 0.5 1120 2.75

To test the effectiveness of the algorithm, we change the Pc and Pm values in the CGA and do the experiments. The results are provided in Table 6. To compare the results, we give an index called relative error, i.e. (optimal objective value – actual objective value)/optimal objective value × 100%, where the optimal objective value is the minimum one of all the objective values obtained. It can be seen from Table 6 that the relative errors do not exceed 4%, which shows that the designed algorithm is robust to the parameter settings and effective for solving the problem.

To show the significance of our multi-depot distribution routing model, we study the case where unexpected events have attacked only a smaller number of areas, sending relief material to which can be well done by either one depot. Suppose the former 12 areas in Table 4 are attacked by the unexpected events. We search the optimal vehicle routing plans in the following three cases. In case one, only vehicles in depot 1 serve the 12 affected areas, in case two, only vehicles in depot 2 serve the 12 affected areas, and in case three, vehicles in both depot 1 and depot 2 can serve the 12 affected areas. Running CGA 50,000 generations, we get that the objective values in case one, two and three are 490.5, 428.75 and 421.25 minutes, respectively, which implies that even in the case where either one depot has capacity to serve the affected areas in unexpected events, two-depot routing plan still has advantage: It can send relief material to the affected areas earlier than either one-depot routing plan.

5 Conclusion

This paper has studied a multi-depot vehicle routing problem for dispatching vehicles in multi-depots to distribute relief material to the affected areas in unexpected events. Due to the occurrence of the unexpected events, people’s demands in the affected areas and the vehicles’ travel times on roads lack historical data and are given by experts’ estimations rather than historical data. Uncertain variables have been used to describe these parameters and an emergency multi-depot logistics distribution routing model has been developed. To solve the problem, the equivalent of the proposed model has also been given. The results of the example show that the model is effective for solving the proposed multi-depot vehicle routing problem.

Acknowledgment

This work was supported by National Social Science Foundation of China No. 17BGL052, Fundamental Research Funds for the Central Universities No. FRF-BR-16-002B, and USTB-NTUT Joint Research Program No. TW201709.

References

[1] Charnes, A., Cooper, W. W., Karwan, K. R., and Wallace, W. A. (1976). A goal interval programming model for resource allocation in a marine environmental protection program. J. Environ. Econ. Manang. 3,347–362.

[2] Gao, Y. (2011). Shortest path problem with uncertain arc lengths. Comput. Math. Appl. 62, 2591–2600.

[3] Gao, Y. (2012). Uncertain models for single facility location problems on networks. Appl. Math. Modell. 36, 2592–2599.

[4] Garrido, R. A., Lamas, P., and Pino, F. J. (2015). A stochastic programming approach for floods emergency logistics. Trans. Res. E 75, 18–31.

[5] Horner, M. W., and Downs, J. A. (2010). Optimizing hurricane disaster relief goods distribution: model development and application with respect to planning strategies. Disasters 34, 821–844.

[6] Huang, X. (2010). Portfolio Analysis: From Probabilistic to Credibilistic and Uncertain Approaches. Berlin: Springer-Verlag.

[7] Huang, X. (2012). Mean-variance models for portfolio selection subject to experts’ estimations. Exp. Syst. Appl. 39, 5887–5893.

[8] Huang, X., and Di, H. (2015). Modeling uncapacitated facility location problem with uncertain customers’ positions. J. Intell. Fuzzy Syst. 28, 2569–2577.

[9] Huang, X., and Song, L. (2016). An emergency logistics distribution routing model for unexpected events. Ann. Operat. Res. 2016, 1–17.

[10] Huang, X., and Zhao, T. (2014a). Mean-chance model for portfolio selection based on uncertain measure. Insurance 59, 243–250.

[11] Huang, X., and Zhao, T. (2014b). Project selection and scheduling with uncertain net income and investment cost. Appl. Math. Comput. 63,1583–1594.

[12] Huang, X., and Zhao, T. (2016). Project selection and adjustment based on uncertain measure. Inf. Sci. 352–353, 1–14.

[13] Liberatore, F., Ortuño, M. T., Tirado, G., Vitoriano, B., and Scaparra, M.P. (2014). A hierarchical compromise model for the joint optimization of recovery operations and distribution of emergency goods in Humanitarian Logistics. goods in humanitarian logistics. Comput. Operat. Res. 42, 3–13.

[14] Linet, Ö., Ediz, E., and Beste, K. (2004). Emergency logistics planning in natural disasters. Ann. Operat. Res. 129, 217–245.

[15] Liu, B. (2007). Uncertainty Theory. 2nd ed. Berlin: Springer-Verlag.

[16] Liu, B. (2009a). Some research problems in uncertainty theory. J. Uncert. Syst. 3, 3–10.

[17] Liu, B. (2009b). Theory and practice of uncertain programming, 2nd ed. Berlin: Springer-Verlag.

[18] Liu, B. (2010). Uncertainty Theory: A Branch of Mathematics for Modeling Human Uncertainty. Berlin: Springer-Verlag.

[19] Lodree, J. E., and Taskin, S. (2009). Supply chain planning for hurricane response with wind speed information updates. Comput. Operat. Res.36, 2–15.

[20] Ning, Y. F., Liu, J. J., and Yan, L. M. (2013). Uncertain aggregate production planning. Soft Comput. 17, 617–624.

[21] Psaraftis, H. N., and Ziogas, B. A. (1985). Tactical decision algorithm for the optimal dispatching of oil spill cheanup equipment. Manag. Sci. 31, 1475–1491.

[22] Qin, Z., and Kar, S. (2013). Single-period inventory problem under uncertain environment. Appl. Math. Comput. 219, 9630–9638.

[23] Tversky, A., and Kahneman, D. (1974). Judgment under uncertainty: heuristic and biases. Science, 185, 1124–1131.

[24] Viswanath, K., and Peeta, S. (2003). The multicommodity maximal covering network design problem for planning critical routes for earthquake response. Trans. Res. Rec. 1857, 1–10.

[25] Wang, X., Chen, H., and Wang, K. (2012). Studies on emergency logistics operation model for unexpected events at Yangtze chemical industrial park. Proc. Eng. 43, 353–358.

[26] Yuan, Y., and Wang, D. (2009). Path selection model and algorithm for emergency logistics management. Comput. Ind. Eng. 56, 1081–1094.

[27] Zhang, Q., Huang, X., and Tang, L. (2011). Optimal multinational capital budgeting under uncertainty. Comput. Math. Appl. 62, 4557–4567.

[28] Zhang, Q., Huang, X., and Zhang, C. (2015). A mean-risk index model for uncertain capital budgeting. J. Operat. Res. Soc. 66, 761–770.

[29] Zhang, J. H., Li, J., and Liu, Z. P. (2012). Multiple-resource and multipledepot emergency response problem considering secondary disasters. Exp. Syst. Appl. 39, 11066–11071.

[30] Zhang, X., Zhang, Z., Zhang, Y., Wei, D., and Deng, Y. (2013). Route selection for emergency logisctics management: a bio-inspired algorithm. Saf. Sci. 54, 87–91.

Biographies

images

Xiaoxia Huang, Ph.D., is a professor in the Donlinks School of Economics and Management, University of Science and Technology Beijing. She received her Bachelor of Science from University of Science and Technology Beijing,Bachelor of Economics from University of International Business andEconomics, Master of Management from University of Science and Technology Beijing, and Ph.D. from Beijing Institute Technology. Her major research area is in portfolio selection, capital budgeting, risk analysis, and investment optimization. She was awarded New Century Excellent Talents by the Ministry of China, and was one of the Most Cited Chinese Researchers issued by Elsevier from 2014 to 2016.

images

Liying Song, is a Ph.D. candidate in the Donlinks School of Economics and Management, University of Science and Technology since 2014. She received her B.Sc. in computer science from Liaoning Normal University and then she pursued her M.Sc. degree in E-Commerce Engineering from computer science department of Aberdeen University in United Kingdom.

images

Hongqing Song, Ph.D., is an associate professor in the School of Civil and Resource Engineering, University of Science and Technology Beijing. He received his B.Sc. degree in Process equipment and control engineering from Dalian University of Technology and Ph.D. majored Fluid Mechanics from University of Science and Technology Beijing. His research interests include high performance computing and optimization calculation method in engineering applications.

Abstract

Keywords

1 Introduction

2 Fundamentals of Uncertainty Theory

3 A Multi-Depot Logistics Distribution Routing Modelfor Unexpected Events

4 An Example

5 Conclusion

Acknowledgment

References

Biographies