Figures
Abstract
Natural disasters occur frequently in recent years, causing huge casualties and property losses. Nowadays, people pay more and more attention to the emergency logistics problems. This paper studies the emergency logistics problem with multi-center, multi-commodity, and single-affected-point. Considering that the path near the disaster point may be damaged, the information of the state of the paths is not complete, and the travel time is uncertainty, we establish the nonlinear programming model that objective function is the maximization of time-satisfaction degree. To overcome these drawbacks: the incomplete information and uncertain time, this paper firstly evaluates the multiple roads of transportation network based on grey theory and selects the reliable and optimal path. Then simplify the original model under the scenario that the vehicle only follows the optimal path from the emergency logistics center to the affected point, and use Lingo software to solve it. The numerical experiments are presented to show the feasibility and effectiveness of the proposed method.
Citation: Qiu B-J, Zhang J-H, Qi Y-T, Liu Y (2015) Grey-Theory-Based Optimization Model of Emergency Logistics Considering Time Uncertainty. PLoS ONE 10(9): e0139132. https://doi.org/10.1371/journal.pone.0139132
Editor: Yongtang Shi, Nankai University, CHINA
Received: April 23, 2015; Accepted: September 8, 2015; Published: September 29, 2015
Copyright: © 2015 Qiu et al. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited
Data Availability: All relevant data are within the paper and its Supporting Information files.
Funding: This paper was partially supported by the National Natural Science Foundation of China (NSFC) (Grant Nos. 71201093, 71571111), Independent Innovation Foundation of Shandong University, IIFSDU (Grant No. IFYT14011), and the Foundation of University of Jinan (Grant No XKY1414).
Competing interests: The authors have declared that no competing interests exist.
Introduction
In recent years, a number of disasters happen occasionally, such as the tsunami in Southeast Asia at the end of 2004, Hurricane Katrina in U.S. in 2005, Wenchuan earthquake in 2008, the super earthquake in Philippine in March 2012. All these disasters caused huge casualties and property losses to people. Therefore, emergency logistics play an important role in disaster relief operations. Emergency Logistics is a special logistics activity that provides emergency supplies for unexpected natural disasters, public health emergencies and other unexpected incidents, and aims at maximizing the time benefit and minimizing the loss of the disaster. And many researchers have focused on this subject since the late 1980s.
Haghani and Oh [1] present a large-scale multi-commodity multi- modal network flow model with time windows in the context of disaster relief operations. Two different heuristics are proposed for the solution of the problem. Vitoriano et al. [2] proposed a multi-criteria optimization model for aid distribution, and establish a decision support system. Ozdamar et al. [3] present a network-based multi-period model for emergency logistics. Tzeng et al. [4] develop a multi-objective relief-distribution model for designing real-life relief delivery systems. Their model features three objectives, including minimization of the total cost, minimization of the total travel time, and maximization of the minimal satisfaction during the planning period. Yan and Shih [5] propose multi-objective, multi-commodity network model in order to minimize the time of road maintenance and material distribution. Nolz et al. [6] develop a multi-objective model for emergency logistics. This model encompasses three objective functions, including minimizing the risk, maximizing the coverage provided by the logistics system and minimizing the total travel time. Najafi et al. [7] propose a multi-objective, multi-mode, multi-commodity, and multi-period stochastic model to manage the logistics of both commodities and injured people in the earthquake response, and develop a robust approach to make sure that the distribution plan performs well under the various situations. Barbarosoglu and Arda [8] present a two-stage stochastic programming model for relief distribution that includes uncertain arc capacities and demands to represent the lack of knowledge following a disaster. Ali Bozorgi-Amiri et al. [9] propose the multi-objective stochastic programming model of relief logistics with uncertainty. Sheu [10] presents a hybrid fuzzy clustering-optimization approach to coordinate the relief logistics flows in a three-layer relief supply network during the crucial rescue period. Raktim Pal and Indranil Bose [11] propose mixed integer programming model for deployment of roadway incident response vehicles with reliability constraint, and divide disaster points into big and small ones which consider different sizes of vehicles. Zhang et al. [12] propose an integer mathematical model to allocate the available resources to demand points subject to constraints on multiple resources and possible secondary disasters. Yuan and Wang [13] construct a model to express the effect that the disaster extension influenced the travel speed. Chang et al. [14] propose a greedy-search-based, multi-objective, genetic algorithm capable of regulating the distribution of available resources and automatically generating a variety of feasible emergency logistics schedules for decision-makers.
From the above literature, the existing models are mainly divided into two categories: deterministic and undeterministic model; and the objective functions are mainly minimization of the total cost, minimization of the total travel time, or minimizing the risk; and uncertainty factors include demand, and the number of vehicles etc. While the literature considering the incomplete information and uncertain time is rare. Sheu [15] presents a dynamic relief-demand management model for emergency logistics operations under imperfect information conditions in large-scale natural disasters. Their model consists of three main steps: data fusion to forecast relief demand in multiple areas, fuzzy clustering to classify affected area into groups, and multi-criteria decision making to rank the order of priority of groups. Zhang et al. [16] study route selection of emergency logistics which the travel time is not only related with the length of the arc, but it is also related with the travel speed of arc since the travel speed is a decreased function respect to distance. In fact, when disaster happens, the information of the state of the roads is not complete, because it is unexpected and the rescue time is urgent. Based on this consideration, this paper will assess the multiple roads of transportation network based on grey theory and select the reliable and optimal path, during which the vehicle only follows the optimal path from the emergency logistics center to the affected point. In addition, the travel time is uncertainty, and we have known that the travel time will go up generally with the increase of vehicles on the path. Therefore, this paper will consider the situation that the travel time is uncertainty, study the emergency logistics problem of multi-center, multi-commodity, and single-affected-point based on grey theory, and establish the nonlinear programming model that objective function is the maximization of time-satisfaction degree.
The section 2 describes some basic assumptions and symbols. The section 3 first establishes the relationship between travel time ti and traffic volume vi,, defines time-satisfaction degree function, and establishes a nonlinear programming model. The section 4 describes how to determine the optimal path based on grey theory and then simplifies the above model. Finally, an illustrative example and conclusion are presented in Sections 5 and 6 respectively.
Problem Description
There exist m emergency logistics centers that can totally provide n types of emergency supplies to the affected point. There is 1 affected point, when the affected point suffers disaster; emergency logistics center will provide appropriate relief services for the affected point. The loading capacity of vehicles is equal.
This paper will establish the nonlinear programming model that objective function is the maximization of time-satisfaction degree, and select optimal path based on grey theory and schedule emergency supplies from multi-emergency logistics center to single affected point.
2.1 Assumption
- demand for various emergency supplies of affected point is constant, and the supplies must be delivered within a certain time.
- all emergency logistics center are capable of satisfying the demand for various emergency supplies of the affected point, and the vehicle is allowed to a non-loaded transport.
- every emergency logistics center has only one type of vehicle, and the capacity of vehicle is less than the demand of the affected point for various emergency supplies, the vehicles of each center are certain, and the total vehicle capacity of all the emergency center is greater than the total necessary emergency supplies of affected point.
- paths from different emergency logistics centers to the affected point are in no coincidence, and different paths from the same center to affected point can coincide.
- Volume-delay functions [17,18,19] are used to express the travel time on a road link as a function of the traffic volume v. The most widely used Volume-delay functions are the Bureau of Public Roads (BPR) [18,19], which are defined as
where c is the capacity of the road and v is the traffic volume of the road. In this paper, for the purpose of processing convenience, we let α = 2.
- all vehicles will set off to the affected point together after being loaded.
2.2 Symbols Illustration
i, j, k, l respectively represents emergency logistics center, emergency supplies, vehicles, sequence numbers of paths;
F, f, q respectively denote the fixed cost of using a vehicle, the cost per unit distance and the loading capacity of the vehicle;
A denotes budget; T represents the latest allowed arrival time to the affected point estimated by experts;
ki、li respectively denotes the number of the vehicles owned by center i and the number of paths to the affected point;
ρj、Pj respectively denotes the weight of unit material and the demand for material j of the affected point;
Dij represents the amount of material j that center i can provide;
til、 respectively represents the actual time from center i to the affected point via the lth route and the time used normally;
dil、Qil respectively represents the distance of the lth path from center i to the affected point and the road loading capacity;
yik = 0 or 1, when the kth vehicle is called of center i yik = 1, otherwise yik = 0,
or 1, when the kth vehicle of center i follows the lth path
, otherwise
,
xijk indicates the amount of material j loaded by the kth vehicle of center i;
Note: The range of the symbols above i, j, k, l is respectively i = 1, 2, …, m, j = 1,2, …, n, k = 1, 2,…, ki, l = 1,2, …, li without other special instructions.
The Model Establishment
3.1 The Relationship between the Travel Time ti and the Traffic Volume vi of the Path
With the increase of the vehicles on path, the vehicle speed will be reduced, and increase with travel time correspondingly. Based on the assumption 5, the relationship between the actual time and the traffic volume of the lth route from center i to the affected point is as follows:
(1)
Here, it is allowed that the actual traffic volume exceeds the capacity of the path, thus it comes at the cost of increasing the travel time on the path. We adjust the number of vehicles on each path by maximizing time-satisfaction degree, making that it not exceeds the capacity of path too much, so in the model later we do not consider the capacity limitation of each optimal path, i.e.
3.2 The Time-Satisfaction Degree Function
Because of the uncertainties on the number of vehicle and the distribution plan of emergency supplies, the arrival time of vehicles is also uncertain. The longer the travel time used to transport the emergency supplies, the lower satisfaction degree of the affected point, on the contrary, the higher satisfaction degree. Define the time-satisfaction degree function as shown in Fig 1.
3.3 The Model of the Problem
Formula (4) is the objective function, which denotes that the sum of time-satisfaction degree from all emergency centers to the affected point; Eqs (5) and (6) represents the travel time from center i to affected point via the l-th route does not exceed the preset time; Eq (7) shows that the total cost does not exceed the budget; Eq (8) represents the capacity limitations of the vehicle; Eq (9) denotes the capacity constraints of material j that center i can provide; Eq (10) represents the total demand for material j in order to satisfy the affected point; Eq (11) represents that the k-th vehicle in center i can at most choose one path to transport the materials to the affected point. Eq (12) represents 0–1 variables; Eq (13) represents non-negative integer constraints.
The Optimal Path Determination
4.1 Prepare Knowledge
(1) Index system for the optimal path evaluation.
When selecting the optimal path in emergency logistics, we need establish the selection and evaluation index system. In this paper, we consider the six indicators: the safety of transportation (ST), convenience of transportation organization (CTO), congestion level of path (CLP), the difficulty of traveling (DT), path information (PI), and path conditions (PC).
(2) Grey class, grey number and whitenization weight function [20].
In the study of system, due to different disturbance and limitation of cognition level, people get some uncertain information. The grey system theory is a method dealing with systems with few data, poor information, and uncertainty question. The number that we only know the range of its value but don't know the exact value is called the grey number. Whitenization weight function is used to describe the preference degree of a grey number for different value of its value range.
The normal whitenization weight function f1 (x) is described as:
(14)
where a1<a2, f1(x) is a continuous function, L(x) is a non-decreasing function, and R(x) is a non-increasing function. In general, L(x) = (x-x1)/(x2-x1), R(x) = (x6-x)/(x6-x5).
For path selection problem, this paper divides the grey class into four classes: excellent, good, medium and poor. According to the importance of each grey class, we preset the grey class weight c = (1, 0.8, 0.6, 0.4). The whitenization weight function of the first grey class (excellent) is φ1, the whitenization weight function of the second grey class (good) φ2, the whitenization weight function of the third grey class (medium) φ3, the whitenization weight function of the fourth grey class (poor) φ4, are respectively shown in Fig 2:
(3) Determine the weight of evaluation index.
The weight vector w of evaluation index is determined as follows: first, obtain the judgments of various experts in the form of questionnaire. Each expert writes 1 on the index that he considers the most important, and writes 2 on the second important… writes M on the least important.
After attaining the data, process the obtained data as follows
(16)
Wherein, wi represents the weight of the i-th index; M represents the number of index; N represents the number of experts; Ri represents the sum of the assessment on the i-th index by various experts.
4.2 Selection of The Optimal Path Based on Grey Theory
(1) Symbols illustration.
i represents index number, i = 1,2, …, 6; j represents the evaluation grey class number, j = 1,2,3,4;
gsi denotes the i-th evaluation index of the s-th(s = 1,2,…, l) path;
β = (βsi)l×6 represents the evaluation information matrix, wherein βsi is attained from the normalization processing of gsi.
X(s) = (xij(s))6×4, where xij(s) represents the grey evaluation coefficient on evaluation index i belongs to the j-th grey class of the s-th path;
P(s) = (pij(s)) 6×4, wherein, pij(s) represents the grey evaluation weight on evaluation index i belongs to the j-th grey class of the s-th path;
y(s) represents the vector of synthetic evaluation results on the s-th path;
Y represents synthetic situation matrix of the path;
z represents the synthetic evaluation vector of the path.
(2) The steps to determine the optimal path based on grey theory.
The steps are as follows.
Step 1: determine the index value for each path and normalize to obtain path evaluation information matrix β
Based on the actual situation, determine each index value for each path, since the unit and standards of each index value are different, the data has to be normalized. If the value of evaluation index is the bigger the better, then process according to the formula ; otherwise process it according to the formula
. After processing, we can obtain the information matrix of path β = (βsi)n×m.
Step 2: Calculate the grey evaluation weight matrix for each path
Seek the grey evaluation coefficient matrix X(s) = (xij(s))6×4 belongs to each evaluation grey class of each index value on each path, wherein xij(s) = φj(βsi), then seek the grey evaluation weight matrix P(s) = (pij(s))6×4 to each evaluation grey class j of each index on the s-th path.
Step 3: Calculate the synthetic evaluation value matrix Y of each path
Whereiny(s) = wP(s), which represents the synthetic evaluation of each grey class on the s-th path.
Step 4: Determine the optimal path
Seek the synthetic evaluation value for each path z = Yc = (z1, z2, …, zl)T, where zs, s = 1,2,…, l is the synthetic evaluation value of the s-th optional path, and the path with the maximum synthetic evaluation value is the optimal path.
4.3 Simplify the Original Model
After obtaining the optimal path from each center to the affected point, we limit that it only follows the optimal path from emergency logistics center i to affected point. Under this assumption, if the vehicle of center i is called, it can only take the optimal path, then the 0–1 variable in the model can be removed. The symbols
will become the corresponding information on the optimal path from center i to the affected point, which are respectively represented by ti、ti0、yik、Qi、di. At this point, this simplified model is obtained as follows:
(18)
(19)
(20)
(21)
Eqs (8), (9), (10) and (13)
(22)
There is piecewise function in the objective function of the above model, and the model is a nonlinear programming model. This paper will use the software lingo to solve the optimization model.
Numerical Experiments
In this paper, we use an example of the earthquake to analyze in a certain area. Assume that each emergency logistics center can obtain some information after the disaster. Given that the affected points need 6 types of emergency supplies which are tents, quilts, drinking water, bread, bandages and drug(denoted respectively by j = 1,2,3,4,5,6), the unit weight (kg) of 6 materials is 80, 5, 24, 20, 15,30 respectively. There are 5 emergency logistics centers (denoted respectively by i = 1,2,3,4,5) near the affected points which can provide emergency supplies. Each center has 4 vehicles, and the vehicle loading capacity is q = 50(ton), the fixed cost of using a car is F = 5000(Yuan), the average cost for driving 100 kilometers is f = 120(Yuan), the budget of transportation expenses is A = 1,000,000 (Yuan). Experts estimate that the latest rescue time is T = 24(hour), and we set ai = 24, bi = 12. The other relevant data is in Table 1 and Table 2.
5.1 Select the Optimal Path Based on Grey Theory
According to steps in section 4.2, we can obtain the optimal path from each emergency logistics center to the affected points easily. The final result is shown in Table 3.
From the Table 3, we know that center 1 chooses the 4th path, center 2 chooses the 6th path, center 3 chooses the 8th path, center 4 chooses the 10th path, and center 5 chooses the 16th path.
5.2 Solve the Optimal Solution of The Model
Using lingo software to solve it, we get that the maximum time-satisfaction degree is 4.790625, and the optimal distribution scheme is shown in Table 4, and the arrival time from emergency logistics center to the affected points is shown in Table 5.
5.3 Further Discussion
According to the assumption 5 in section 2.1, we supposed that travel time of the path is quadratic function of the traffic volume. It can be shown in Table 6 that the running time of global optimal solution will become very long when the number of vehicles increases at every logistics center, which can't be accepted in the actual problem. So when the running time is too long, we generally take the local optimal value as satisfactory solution of the practical problems. However, under the assumption that travel time of the path is linear function of the traffic volume, the growth speed of the running time of global optimal solution is not fast when the number of vehicles increases at every logistics center. And besides, the running time becomes shorter when the number of vehicles increases to a certain value, because the objectives function value can reach the maximum value 5 soon.
Therefore, when the number of vehicles is small, a quadratic relationship setting can get the optimal solution in a short time. Otherwise, a linear relationship is better.
Conclusions
Emergency logistics problem is a hot topic in the field of management science, and there are a lot of issues which are worth studying. This paper focuses on the emergency logistics problem with multi-center, multi-commodity, and single-affected-point. According to the actual conditions that the path near the disaster point may be damaged, the information of the state of the paths is not complete, and the travel time is uncertainty, we propose the nonlinear programming model whose objective is maximizing the time-satisfaction degree. We obtain the optimal paths from each emergency logistics center to the disaster point based on grey theory, and then simplify the original model considering that the vehicle only follows the optimal path from the emergency logistics center to the affected point, and finally use Lingo software to solve it. The results of numerical experiment show the feasibility and effectiveness of the proposed method.
In the future, we will study effective approximation algorithms or heuristic algorithms to solve the simplified nonlinear programming model. And we’ll study the application of this method based on the actual case, such as “WenChuan” earthquake. These can help the relevant government departments develop the emergency plans scientifically and effectively, and perform the rescue quickly and efficiently.
Supporting Information
S1 Table. Data information of each path from emergency logistics center to the affected points.
The meaning of the abbreviations are as follows, ST: safety of transportation, CTO: the convenience of transportation organization, CLP: the congestion level of path, DT: the difficulty of traveling, PI: path information, PC: path conditions.
https://doi.org/10.1371/journal.pone.0139132.s001
(XLSX)
Acknowledgments
We would like to thank the editor and the anonymous reviewers for their constructive comments and suggestions on earlier versions of this paper.
Author Contributions
Conceived and designed the experiments: JHZ. Performed the experiments: BJQ YTQ YL. Analyzed the data: BJQ JHZ YL. Contributed reagents/materials/analysis tools: BJQ JHZ. Wrote the paper: BJQ JHZ YTQ YL. Established the model and designed the ideal to solve the model: BJQ JHZ.
References
- 1. Haghani A, Oh SC. Formulation and solution of a multi-commodity, multi- modal network flow model for disaster relief operations. Transportation Research Part A: Policy and Practice, 1996, 30(3): 231–250.
- 2. Vitoriano B., Ortuño M.T., Tirado G., Montero J. A multi-criteria optimization model for humanitarian aid distribution. Journal of Global Optimization, 2011, 51: 189–208.
- 3. Ozdamar L., Ekinci E., Kucukyazici B. Emergency logistics planning in natural disasters. Annals of Operations Research, 2004, 129: 217–245.
- 4. Tzeng G.H., Cheng H.J., Huang T.D. Multi-objective optimal planning for designing relief delivery systems. Transportation Research Part E: Logistics and Transportation Review, 2007, 43: 673–686.
- 5. Yan S, Shih Y. Optimal scheduling of emergency roadway repair and subsequent relief distribution. Computers & Operations Research, 2009, 36: 2049–2065.
- 6. Nolz C.P., Semet F., Doerner F.K. Risk approaches for delivering disaster relief supplies. OR Spectrum, 2011, 33: 543–569.
- 7. Najafi M., Eshghi K., Dullaert W. A multi-objective robust optimization model for logistics planning in the earthquake response phase. Transportation Research Part E: Logistics and Transportation Review, 2013, 49: 217–249.
- 8. Barbarosoglu G., Arda Y. A two-stage stochastic programming framework for transportation planning in disaster response. Journal of Operational Research Society, 2004, 55: 43–53.
- 9. Bozorgi-Amiri Ali, Jabalameli M. S., Mirzapour Al-e-Hashem S. M. J.. A multi-objective robust stochastic programming model for disaster relief logistics under uncertainty. OR Spectrum, 2013, 35(4): 905–933.
- 10. Sheu J.B. An emergency logistics distribution approach for quick response to urgent relief demand in disasters. Transportation Research Part E: Logistics and Transportation Review, 2007, 43: 687–709.
- 11. Pal Raktim, Bose Indranil. An optimization based approach for deployment of roadway incident response vehicles with reliability constraints. European Journal of Operational Research, 2009, 198: 452–463.
- 12. Zhang J.H., Li J., Liu Z.P. Multiple-resource and multiple-depot emergency response problem considering secondary disasters. Expert Systems with Applications, 2012, 39: 11066–11071.
- 13. Yuan Y., Wang D. Path selection model and algorithm for emergency logistics management. Computers & Industrial Engineering, 2009, 56: 1081–1094.
- 14. Chang F.S, Wu J.S., Lee C.N., Shen H.C. Greedy-search-based multi-objective genetic algorithm for emergency logistics scheduling. Expert Systems with Applications, 2014, 41(6): 2947–2956.
- 15. Sheu J.B. Dynamic relief-demand management for emergency logistics operations under large-scale disasters. Transportation Research Part E; Logistics and Transportation Review, 2010, 46: 1–17.
- 16. Zhang X., Zhang Z., Zhang Y., Wei D., Deng Y. Route selection for emergency logistics management: A bio-inspired algorithm. Safety Science, 2013, 54: 87–91.
- 17. Branston D.. Link capacity functions: A review. Tran. Res. 1976, 10: 223–236.
- 18.
Bureau of public roads, Traffic assignment manul, U.S. Dept. of commerce, Urban planning division, Washington D.C., 1964.
- 19. Spiess Heinz. Technical Note—Conical Volume-Delay Functions. Transportation Science, 1990, 24(2):153–158.
- 20.
Liu S., Lin Y. Grey Information: Theory and Practical Applications. Springer, 2005.