A Logistics Model for Emergency Supply of Critical Items, YH Lin, R Battaa, PA Rogersona, A Blatta, M Flanigana

Tags: disaster relief operation, split delivery, CPLEX, soft time windows, medication, vehicle routing problem, prescription medication, Washington, D.C., integer programming model, Washington, sub-problems, Transportation Research Record, nodes, items, delivery strategy, disaster relief, National Academies, sub-problem, Los Angeles County, Transportation Research Board, delivery, Buffalo, NY, United States, delivery vehicles, VRP, Marie Flanigana, Department of Industrial and Systems Engineering, Alan Blatta, time windows, service level, random instances, central depot, generator, prescription, maximum difference, Decision Variables, local distribution center, Decomposition Lin, the earthquake, number of households, unsatisfied demand, vehicles, Research Board, problem size, size problems, demand data, period
Content: 1
A Logistics Model for Emergency Supply of Critical Items
2
in the Aftermath of a Disaster
3
Yen-Hung Lin a,b, Rajan Battaa,b, , Peter A. Rogersona,c,
4
Alan Blatta, Marie Flanigana, Kunik Leed
5
aCenter for Transportation Injury Research, CUBRC,
6
Buffalo, NY 14225, United States
7
bDepartment of Industrial and Systems Engineering,University at Buffalo (SUNY),
8
Buffalo, NY 14260, United States
9
cDepartment of Geography,University at Buffalo (SUNY),
10
Buffalo, NY 14260, United States
11
dFederal Highway Administration, Turner-Fairbanks Highway Research Center,
12
McLean, VA 22101, United States
13
July 30, 2010
14
Word Count: 6,374
15
Number of Figures: 2
16
Number of Tables: 2
Corresponding author. Address: Department of Industrial and Systems Engineering, University at Buffalo (SUNY), Buffalo, NY 14260, United States. Tel.: +1 716 6450972; fax: +1 716 6453302. E-mail address:[email protected] (R. Batta)
Lin, Y-H, Batta, R., Rogerson, P.A., Blatt, A., Flanigan, M., and Lee, K.
1
17
Abstract
18
In this paper, a new logistics model is proposed for the emergency supply of critical items in the aftermath of
19
a disaster. The modeling framework considers multi-items, multi-vehicles, multi-periods, soft time windows, and a
20
split and prioritized delivery strategy scenario, and is formulated as a multi-objective integer programming model.
21
To effectively solve this model we limit the number of available tours for delivery vehicles; towards this end a
22
decomposition approach is introduced that aims to decompose the original problem geographically. A computational
23
study is conducted to evaluate the proposed approach, and a case study and related analysis are presented to illustrate
24
the potential applicability of our model.
25
keywords: Vehicle routing problem, disaster relief, prioritized delivery, split delivery, soft time windows
Lin, Y-H, Batta, R., Rogerson, P.A., Blatt, A., Flanigan, M., and Lee, K.
2
26 INTRODUCTION
27 In recent years, much human life has been lost due to natural disasters. At least 1,836 people lost their lives in 28 Hurricane Katrina in 2005 (1), and 86,000 died in the Kashmir Earthquake in Pakistan in 2005 (2). The most recent 29 earthquake in Haiti caused approximately 230,000 deaths and more than 300,000 injuries (3). To mitigate damage 30 and loss in disasters, studies in pre-disaster, during disaster, and post-disaster issues have been widely conducted 31 in the past few years (4, 5, 6). A critical challenge in post-disaster is to transport sufficient essential supplies to 32 affected areas in order to support basic living needs for those trapped in disaster-affected areas. Supplies that are 33 essential for human survival include water, food (e.g., ready-to-eat meals), and prescription medications. In general, 34 prescription medication (e.g., diabetic supplies) are needed most urgently, followed by water and food, respectively. 35 The requirement for delivering essential supplies that have different priorities to a disaster-affected area provides the 36 motivation for this work. 37 Logistics problems are often modeled as variants of the vehicle routing problem (VRP). The classical VRP consists 38 of determining optimal routes for vehicles that originate and terminate at a single depot, to deliver items to a set of 39 nodes geographically scattered while minimizing the total travel distance/time/total delivery cost. The VRP has been 40 extended to include the capacitated VRP (CVRP), and the vehicle routing problem with time windows (VRPTW) 41 (7, 8). We now summarize related literature that contains similar characteristics to our modeling framework. Three 42 particular characteristics, appearing in the vehicle routing problem literature that are related to our new logistics model 43 are: soft time windows, multi-period routing, and split delivery strategy. 44 A vehicle routing problem with soft time windows (VRPSTW) is a special case of the VRPTW and has been 45 discussed in the literature, though not often. Contrary to the general time windows constraints, usually indicating the 46 earliest and latest allowable service time of a node, soft time windows denote that both the upper and lower bound 47 of the time window can be violated with a suitable penalty. Papers in this type of problems include Taillard et al. 48 (9) and Jung and Haghani (10). Multi-period vehicle routing problems are not common in the literature due to their 49 difficulties. In this type of VRP, routes are constructed over a period of time. The most recent review of this kind of 50 vehicle routing problem is seen in Francis et al. (11). Finally, the split delivery vehicle routing problem (SDVRP) is 51 defined as follows: the demand of a node can be satisfied by more than one-time delivery instead of only one-time 52 delivery allowed in the general VRPs. A detailed survey of the development of SDVRP can be found in Archetti and 53 Speranza (12). 54 The main contributions of this paper are as follows:
55 · Soft time windows, multi-period routing, split delivery strategy, and prioritized delivery are considered simulta-
56
neously in the new model.
57 · An approach of tour determination for the model is introduced and analysis of its performance is provided.
58 · The consequences of not prioritizing delivery are highlighted with the help of a disaster relief humanitarian
59
logistics case study
60 The rest of this paper is organized as follows. Section 2 presents a tour-based mathematical formulation for the 61 prioritized items delivery problem. The solution methodology of solving the tour-based formulation is discussed 62 in Section 3. Computational examples are provided in Section 4 to demonstrate the performance of the proposed 63 approach. In Section 5, a case study of a disaster relief logistics effort is conducted to show the benefit of our new 64 logistics model. Finally, Section 6 contains conclusions and suggestions for future work.
Lin, Y-H, Batta, R., Rogerson, P.A., Blatt, A., Flanigan, M., and Lee, K.
3
65 TOUR-BASED FORMULATION
66 Description and Assumption 67 We assume that there are multiple geographically dispersed nodes that need to be served by a single depot. It is 68 assumed that the supplies are unlimited in the depot and that the demand from various nodes over a planning horizon 69 is known at the beginning of the planning. For modeling simplicity, demand is assumed unchanged during all planning 70 time periods. Different prioritized items are required to be delivered to nodes via the transportation network. Urgency 71 levels of items are differentiated based on their importance. For each type of item, a soft time window is predefined to 72 specify the nodes' expected waiting time to receive an item. If an item cannot be delivered within the time window, a 73 penalty cost is incurred, although the item still can be delivered later. The longer the delay in delivering an item, the 74 more severe the penalty cost. 75 Characteristics of the transportation mode and the delivery methods are considered. Multiple but limited numbers 76 of identical vehicles are used to transport prioritized items. Vehicles are assumed to have limited weight and volume 77 capacities. For each vehicle, tours are assigned in each period to deliver items to one or more nodes. Tours begin at 78 the depot, continue to one or multiple nodes, and then return to the depot. The total working hours in a single time 79 period for the operation are limited. Therefore, the total travel time of tours assigned to a single vehicle in a single 80 time period cannot exceed the constrained working hours. We do not consider the time to load and unload items on or 81 off the vehicle. Furthermore, any node can be served multiple times by a single vehicle or multiple vehicles to meet 82 its demand, and the demand can also be satisfied fully or partially in a single delivery.
83 Multi-Objective Logistics Model 84 Based on the above scenarios, the new model considers a multi-item, multi-vehicle, multi-period, soft time windows, 85 and split delivery strategy prioritized delivery problem and is constructed by a multi-objective tour-based integer 86 programming formulation. In this section, we first summarize notation, parameters and define decision variables, 87 followed by a presentation of a mathematical formulation for the model.
88 Notation, Parameters, and Decision Variables
89 Sets:
90
I = {1, 2, . . . , i, . . . ,Їi}: the set of item types, and Їi is the total number of item types;
91
J = {1, 2, . . . , j, . . . , Їj}: the set of nodes, and Їj is the total number of nodes;
92
K = 1, 2, . . . , k, . . . , kЇ : the set of tour, and kЇ is the total number of tours;
93
L = 1, 2, . . . , l, . . . , Їl : the set of vehicles, and Їl is the total number of vehicles;
94
T = {1, 2, . . . , t, . . . , tЇ}: the set of periods, and tЇis the total number of planning time periods
95 Routing parameters:
96
Jk: the set of nodes which the vehicle will visit on tour k;
97
tk: travel time of tour k;
98
[0, toi]: time window for delivering item i without penalty after demand occurs, where toi is the maximum
99
acceptable waiting time to receive item i;
100
Ck: travel cost of tour k;
Lin, Y-H, Batta, R., Rogerson, P.A., Blatt, A., Flanigan, M., and Lee, K.
4
101
H: total working time available in a single period;
102
W : the maximum load weight of a vehicle;
103
V : the maximum volume capacity of a vehicle;
104
M : a large number;
105
u: the index of the length of delays after the maximum acceptable waiting time since the demand was requested,
106
where tЇ- toi u tЇ, i;
107
v: the index of time periods when the backorder delivery of item i can be made after demand was requested at
108
period t, where t + 1 v t + tЇ- toi;
109 Demand parameters:
110
dijt: demand of the item i of the node j at time t;
111
piu: penalty cost of item i if the severe level of delay is u;
112
f pi: penalty cost of item i if there is remaining unsatisfied demand after the operation;
113
ai: unit weight of item i;
114
bi: unit volume of item i;
115 Delivery Decision Variables:
116
xijklt: amount of item i delivered to node j on tour k by vehicle l in period t immediately after demand occurs;
117
wijklmn: backorder amount of item i delivered to node j on tour k by vehicle l in period m for demand in period
118
n, where m, n T and n < m;
119
S: maximum difference of service level between any two nodes;
120
sj: service level of node j.
121 Routing Decision Variables:
122
yklt: equal to one when tour k is assigned to vehicle l in period t, and 0 otherwise.
123 Formulation
124 Objective 1:
tЇ-toi tЇ-toi-u+1
t+u
min.
dijt -
xijklt +
wijklvt · piu+
i j u=1 t=1
kl
v=t+1



(1)

dijt -
xijklt +
wijklmt · f pi
i
jt
jkl t
m>t,mT
Objective 2:
min.
Ck yklt
(2)
kl
Lin, Y-H, Batta, R., Rogerson, P.A., Blatt, A., Flanigan, M., and Lee, K.
5
Objective 3:
min. S
(3)
Subject to:
S sp - sq, p, q J, p = q
(4)
S sq - sp, p, q J, p = q
(5)
i k l t xijklt + m>t,mT wijklmt
sj =
i t dijt
, j J
(6)
tkyklt H l, t T
(7)
k
xijklt M yklt i, j Jk, k, l, t
(8)
wijkltn M yklt i, j Jk, k, l, t, n < t
(9)
xijklt +
wijklmt
dijt
kl t
k l m>t,mT t
t


i, j
(10)
ai xijklt +
wijkltn W
k, l, t
(11)
ij
n

bi xijklt +
wijkltn V
k, l, t
(12)
ij
nxijklt 0 i, j Jk, k, l, t
(13)
wijklmn 0 i, j Jk, k, l, m T, n T
(14)
xijklt = 0 i, j / Jk, k, l, t
(15)
wijklmn = 0 i, j / Jk, k, l, m T, n T
(16)
yklt {0, 1} k, l, t
(17)
125 In this model, the objective function (1) is a penalty function that aims to minimize total unsatisfied demand,
126 especially for high priority items. Each item can only be backordered during toi periods after the period t in which it
127 is requested. If the initial demand from period t cannot be backordered during the subsequent toi periods, a penalty
128 is applied. There are two parts in this objective function. The first part (until piu) indicates the total accrued penalty
129 cost during the planning periods. It is noted that
tЇ-toi u=1
indicates
the
summation
of
the
penalty
due
to
various
lengths
130 of delays, and
tЇ-toi -u+1 t=1
indicates
the
summation
of
the
penalty
for
demand
requested
at
time
period
t
with
length
131 of delay u. Moreover,
t+u v=t+1
wijklvt
determines
the
total
backorder
amount
of
item
i
to
demand
requested
at
time
132 period t for avoiding the penalty due to u time periods of delays. The second part (after piu) is the penalty cost accrued
133 at the end of the planning periods for demand that cannot be delivered before the end of the operation, and it attempts
134 to deliver higher priorities at the end of the operation.
135 The objective function (2) aims to minimize the total travel time for all tours and all vehicles. The purpose of this 136 objective is to assign as many vehicles as possible consistent with the working hour limitation, in order to deliver the 137 largest amount of items (this assumes that the demand in a disaster scenario will be large). Objective function (3) is 138 used to minimize the difference in the satisfaction rate between nodes. The satisfaction rate is the ratio between the 139 requested demand and the actual delivered amounts. The purpose of this objective is intent on balancing the service 140 among nodes. "Fairness" is the term usually used to describe this purpose.
Lin, Y-H, Batta, R., Rogerson, P.A., Blatt, A., Flanigan, M., and Lee, K.
6
141 In addition to these objectives, equations (4-5) are used to determine the maximum service level between any two 142 nodes, and it is obtained by equation (6). Equation (7) indicates that the total travel time of all tours assigned to any 143 single vehicle in this period cannot be longer than the available working hours in a single period. Equations (8) and (9) 144 show that deliveries can only be made if corresponding tours are selected. Equation (10) shows that the total delivery 145 of items cannot exceed the demand during the planning periods. Equations (11) and (12) address the total available 146 loading weight and the total volume limit capacity constraints of a vehicle. Equations (13 - 16) are used to ensure that 147 vehicles can only stop and deliver to nodes on tours assigned to them. Finally, equation (17) indicates that yklt is a 148 binary variable.
149 SOLUTION METHODOLOGY 150 Overall Solution Process 151 To solve the above model, we apply the well-known weighted sum method (13) to aggregate the multi-objective 152 formulations to a single objective formulation. The assumption of applying this approach is that preferences of the 153 decision maker are known a priori. As a matter of fact, during the disaster relief operation, it is obvious that the 154 most important goal is to lower situations of unsatisfied demand (objective 1), followed by balance of service levels 155 among different nodes (objective 3), and expenditure of the operation (objective 2). We used the same consideration 156 to determine appropriate weights of each objective in the weighted sum method. 157 Ideally, the transformed problem can be solved directly using the commercial solver CPLEX in our study. However, 158 an important parameter in the aforementioned model that needs to be determined is the number of tours to be included 159 in the model (denoted by kЇ in the model). Theoretically, all possible tour combinations should be included in the model 160 so that all possible solutions can be explored. For a small-size delivery problem (e.g. only 3 or 5 nodes), it is possible 161 to enumerate all tours and include all of them in the model. However, as the problem size increases, enumerating 162 all tours is not a viable option, because it makes the size of the resultant problem too large for CPLEX to solve (e.g. 163 there are 4,932,055 possible tour combinations for a 10 node problem). Therefore, we propose a decomposition and 164 assignment approach as an alternative to overcome this difficulty.
165 Decomposition and Assignment Approach
166 The proposed approach allows the whole problem to be decomposed into several sub-problems ­ this allows assign167 ment of vehicles to each sub-problem. More specifically, for each sub-problem, we only consider a small number 168 of nodes that are close to each other geographically such that the number of possible tours in each sub-problem is 169 countable and more manageable. A portion of vehicles are assigned to each sub-problem to provide service between 170 the depot and included nodes in the sub-problem. Thus, all sub-problems can be simultaneously solved in parallel, 171 since the size of each sub-problem is solvable by CPLEX in reasonable time.
172 We have named this approach the Decomposition and Assignment Heuristic (DAH). Assume that a set of vehicles 173 L = 1, . . . , l, . . . , Їl , where Їl > 1 is used to deliver items to a set of nodes J = {1, . . . , j, . . . , Їj}. We use to 174 indicate the iteration number of the algorithm, Ї the total desired number of iterations in the algorithm, the number 175 of times that the solution is not improved after an iteration, and Ї the maximum consecutive times allowed in a row 176 that the solution is not improved. If we set = 0 initially, then the DAH procedures can be described as follows:
177
DAH algorithm:
178 1. Randomly select a node that is not included in any group, and put it in a new group J^g.
179 2. Find the nearest node (not currently included in any group) to the last assigned node in the group, and repeat the
180
process until the predefined number of nodes in a group is met or there is no ungrouped node left.
181 3. IF there is a node that does not belong to any group, Go to step 1.
Lin, Y-H, Batta, R., Rogerson, P.A., Blatt, A., Flanigan, M., and Lee, K.
7
182 4. ELSE Equally assign a number of vehicles L^g to each group g G, where G = {1, . . . , g, . . . , gЇ} is the
183
collection of groups, g L^g = Їl, and p = q, J^p J^q = . The original problem has now been decomposed
184
into gЇ subproblems with assigned nodes and vehicles, respectively, and each subproblem is labeled as SPg.
185 5. For each subproblem SPg, all feasible tours are enumerated and constructed using the shortest time principle.
186 6. For each subproblem SPg, construct the mathematical model based on L^g, J^g, and the corresponding demand
187
of nodes in the subproblem; solve SPg by CPLEX, and get the objective values zg and the total objective value
188
zall = g zg. If = 0, set the best total objective value zall = zall.
189 7. IF Ї, find a pair of groups (p, q) that has the minimum and maximum objective value, respectively.
190
8. IF L^p > 2, then do Steps 9 and 10.
191
9.
Remove a random number of vehicles from L^p, where 1 L^p-1, and assign it to L^q.
192 10. 193 11. 194 12.
Go to Step 6, update zp, zq, and zall. IF zall < zall, update zall = zall. Go to Step 8. ELSE Set = + 1.
195 13.
IF Ї. Go to Step 8.
196 14.
ELSE Set = + 1. Go to Step 1.
197 15. ELSEIF There are more than one group in addition to J^p and J^q; find the next maximum objective value
198
group. Go to Step 8.
199 16. ELSE Set = + 1. Go to Step 1.
200 17. ELSE Stop and Exit.
201 Steps 1-3 of the DAH algorithm decompose the original problem into several sub-problems by forming groups 202 with a predefined maximum number of nodes allowed in a group. In step 4, we equally assign vehicles to serve each 203 sub-problem following the order of groups in G. It is noted that we may have to assign a fewer number of vehicles 204 than the average integer number of vehicles to the last formed group. The next two steps are used to construct all tours, 205 and to create corresponding mathematical formulations for each sub-problem. The objective values of sub-problems 206 and the overall objective value under the current decomposition result are obtained in step 6. Steps 7 - 15 aim to 207 improve the solution by adjusting vehicles assignments among groups. If the solution is not improved for Ї successive 208 iterations, groups are reformed and the procedure is repeated until the maximum number of iterations Ї (i.e., times of 209 regrouping) is met. 210 Using this algorithm, we solve several smaller-scale problems, instead of a single large-scale problem. Tours in 211 each sub-problem are countable and manageable, and each sub-problem is also solvable by CPLEX in reasonable 212 computational time.
213 COMPUTATIONAL EXPERIMENTS 214 Two parts are discussed in this section. In the first part, a random instance generator is designed to produce numer215 ical instances for the following computational experiments. In the second part, a comparison of performance of our 216 proposed approach for tour determination and other approaches is provided.
Lin, Y-H, Batta, R., Rogerson, P.A., Blatt, A., Flanigan, M., and Lee, K.
8
217 Random Instance Generator
A random instance generator has been coded in C. We assume that the service area of a logistics operation is in a 50 square miles area. The location of the depot and all nodes are randomly located by the instance generator in this area. Instead of using Euclidean distances between any two nodes, we transform Euclidean distances to estimated road distances to obtain much more realistic estimations of travel times. This can be achieved by using the following equation (14):
2
1/s
d (q, r; k, p, s) = k
|qi - ri|p
(18)
i=1
218 where q and r are coordinate points on the plane in the service area, and k, p, s are parameters. Suggested ranges 219 of these parameters are k {0.80, 2.29}, p, s {0.90, 2.29}, respectively. In our instance generator, parameter 220 values are randomly generated from their corresponding ranges. It is noted that only distances between the depot and 221 each node are estimated according to equation (18), and distances among nodes are generated randomly based on the 222 triangular inequality (i.e., road distances are estimated on link OA and OB, if O is the depot and A, B are two demand 223 nodes, but the distance AB is generated randomly between OA + OB and OA - OB to ensure that the triangule 224 inequality holds).
225 Three sets of problems are generated by the instance generator: small size, medium size, and large size. Each size 226 of problem involves 5 random instances, respectively, where each instance has a distinct network structure, problem 227 size and number of vehicles. Specifically, the set of small size problems consists of 3 nodes and 6-9 tours. Problems 228 with 4 nodes and 20-30 tours are denoted as medium size. The large size problems have 5 nodes and 30-40 tours 229 included in each instance. Regardless of problem size, 10-20 vehicles are used in each instance, selected randomly. 230 Other outputs from the instance generator include the demand of three types of critical items in each node, and 231 structures of tours for each instance.
232 Performance Comparison 233 The performance of the proposed approach for tour determination is evaluated on three sets of problems. The heuristic 234 approach proposed in this paper has been coded in C, which interfaces with the callable library in ILOG CPLEX 235 version 11.2, which is used to solve sub-problems after the tours have been determined in each sub-problem. Each 236 instance with different tour determination approaches has been run on a computer with 2.00 GB RAM,and an Intel 237 Pentium D 3.40 GHz processor. 238 We consider two other tour determination approaches to compare our proposed approach. The first approach is 239 to enumerate all possible tours of problems and to include all of them in the model. Under this approach, we aim to 240 find the exact optimal solutions of these problems. The second approach, proposed by Lin (15), is based on a Genetic 241 Algorithm (named GA-based approach), a popular meta-heuristic method that has been applied in various applications 242 (16, 17). This approach uses a genetic algorithm to generate a small number of tours in each iteration, and the model 243 with these manageable number of tours is solved by CPLEX. The idea is to improve the solution at each iteration by 244 only retaining a reasonable number of good tours in the model until the end of the search process. 245 To compare the performance among different tour determination approaches, we assume that the weights for 246 objectives 1, 2, and 3 are 0.6, 0.1, and 0.3, respectively; these selections conform to general preferences of dealing 247 with disaster relief, where the first goal of the operation is to satisfy as many demand requests as possible, followed 248 by the fairness issue among different demand nodes; the shipment cost of items is typically of the least concern. We 249 use two criteria to stop the iterative process: either the running time exceeds 3,600 seconds or the MIP gap is smaller 250 than 0.01%. In order to obtain a more accurate evaluation, each instance was solved 10 times with different randomly 251 generated demand requests, and the average results of 10 replications for each instance is presented in the TABLE 1. 252 TABLE 1 summarizes the logistics performance of using three different tour determination approaches in the 253 solution process. The first column identifies the IDs of each instance. For each approach, percentages of demand
Lin, Y-H, Batta, R., Rogerson, P.A., Blatt, A., Flanigan, M., and Lee, K.
9
254 delivered and running times (seconds) of the corresponding approach are presented. For some instances, there is no 255 feasible solution available within 3,600 seconds, so we designate them as n/a. Furthermore, under the GA-based 256 approach column, the number of tours that remain in the model for small-size, medium-size, and large-size instances 257 are 6, 7, and 8, respectively. 258 The average performance of the three tour determination approaches is summarized as follows. The GA-Based 259 approach reduces the average running time by about 22.3%, compared to instances with all tours included. The average 260 percentage of complete delivery is 99.8%, which is almost the same as instances in which all tours are included. 261 However, the variance of running times in the GA-based approach is still high (range is from 17.81 to 3,600 seconds), 262 because CPLEX spends a long time in proving optimality in some cases. On the other hand, the DAH approach finds a 263 desirable solution in a very short running time with a 4.3% reduction of solution quality (i.e., only can achieve 95.5% 264 of complete delivery percentage) compared to the GA-based approach. Based on these results it is evident that the 265 DAH approach is both fast and sufficient method and we therefore use this for large-scale problems.
TABLE 1 Performance Comparison of Different Tour Determination Approaches
Instance ID S1 S2 S3 S4 S5
Enumeration
% of
Time
delivered (seconds)
99.98 178.11
99.97
44.54
98.73 312.16
96.31 260.15
94.74
17.81
GA-based Approach
% of
Time
delivered (seconds)
99.96
0.99
99.93
0.97
98.73 271.69
96.31 241.16
94.74
17.94
DAH
% of
Time
delivered (seconds)
99.86
17
99.82
52
96.97
18
95.00
14
87.10
5
M1
96.96
3,600
96.98 192.96
95.16
79
M2
n/a
n/a
98.74 1,794.91
98.05
42
M3
96.54 3,287.17
96.54
58.57
94.87
42
M4
n/a
n/a
92.95
3,600
92.60
39
M5
95.34 2277.21
95.14 3,340.12
93.33
15
L1
n/a
n/a
96.45 301.91
88.89
15
L2
n/a
n/a
97.70 3,473.27
94.57
22
L3
90.94
3,600
91.00 1278.63
77.48
45
L4
n/a
n/a
84.89 291.52
91.00
66
L5
79.09
3,600
73.06 120.37
63.34
14
266 CASE STUDY 267 To illustrate the capability of our model in the context of delivering prioritized items, we applied the logistics model 268 to the disaster relief operation in Northridge, CA, where a 6.7 magnitude earthquake occurred on Jan. 17, 1994. 269 The study region selected is Los Angeles County, CA, with a geographical size of 4,086.9 square miles, and a total 270 population of 9,519,338 (18). 271 Data 272 Federal Emergency Management Agency (FEMA) has developed a software named HAZUS-MH which can be used 273 to simulate nature disasters (19). We used HAZUS-MH to simulate the Northridge earthquake scenario. Three types of 274 simulation output are of particular interest for us: the number of displaced households, the number of severity level 1 275 injuries, and the number of households without water service. These output are used to generate and estimate demand 276 for food, prescription medication, and water, respectively. It is noted that severity level 1 injuries are those which 277 require medical attention, but hospitalization is not needed. We now justify this method. 278 First of all, the number of households without water service is used to generate demand of water. Since the 279 Geographic distribution of households without water service is not provided in the simulation output, we assumed that 280 the number of households without water service in each census tract was proportional to the number of households
Lin, Y-H, Batta, R., Rogerson, P.A., Blatt, A., Flanigan, M., and Lee, K.
10
281 affected by the earthquake in the track. Second, the number of displaced households is used to estimate the demand 282 of food. This is because these families suffered damage to their houses, require a temporary shelter, and are thus 283 incapable of preparing food by themselves. The estimated number of households displaced is 25,469 according to 284 the simulation. Finally, the number of casualties of severity level 1 is used to estimate the demand for prescription 285 medication. Based on the simulation, the total number of injuries at this level is 1,654 in this earthquake. It is noted 286 that we only extracted casualty data for level 1 in the residential families because the earthquake occurred at 4 AM, 287 and we assumed that the majority of people were at home during the earthquake. 288 In a disaster relief operation, it is common to transport supplies first from a central depot to several local distribution 289 centers by trucks; then, supplies are distributed to individuals from local distribution centers. Therefore, we actually 290 formed 9 clusters in Los Angeles County, as shown in FIGURE 1, simply by geographic relationships, and identified 291 a node in each cluster as the local distribution center to receive deliveries from the central depot. The demand data in 292 each node is obtained by aggregating each type of demand from all census tracts located inside the cluster. However, in 293 the simulation output, only "one-time" demand is available for us to derive from data, except the number of households 294 without water service data that consists of different numbers in discrete time points (e.g. day 1 to day 90). Therefore, 295 we assumed that the time series data in this dataset represents the recovery speed from the earthquake, and all supplies 296 would follow the same pattern to recover as well. Demand data of all kinds of items over 7 days can be estimated, 297 respectively, based on the initial "one-time" data from the simulation and the trend of the recovery speed, that is 298 represented by an exponential fitting function, obtained by fitting data of the number of households without water 299 service. As a result, a demand matrix containing 3 items, 9 nodes and 7 time periods was obtained. Based on the 300 catalogue published in a relief organization (20), we defined that the truck used in the study has 11,590 kg and 56 m3 301 of maximum loading and volume limits, respectively. The shipping weights and volumes of each unit of medication, 302 water and food are 86.5 kg and 0.22 m3, 400 kg and 4.3 m3, and 700 kg and 2.3 m3, respectively. We determined the 303 time windows for medication, water, and food for delivery without penalty cost as 0-1 days, 0-2 days, and 0-3 days, 304 respectively. Finally, the maximum working hours in each day was constrained as 15 hours.
FIGURE 1 Clustering Result in Los Angeles County 305 Results 306 Since this case study has nine demand nodes and one depot, the total number of tours is too large to be included in 307 the model, as discussed earlier. We therefore applied the DAH algorithm to decompose the original network into three
Lin, Y-H, Batta, R., Rogerson, P.A., Blatt, A., Flanigan, M., and Lee, K.
11
308 subnetworks that are depicted by different type of lines in FIGURE 2, which shows the transportation network among 309 the central depot and nine nodes in Los Angeles County, CA. The route between any two nodes was first determined by 310 the online map provider, and consisted of detoured partial segments if the best route involves some damaged roadways 311 due to the earthquake. The detours were established according to a government report (21). Then the travel time 312 between any two nodes or between a node and the depot was estimated by taking the average of the travel time in the 313 traffic and in congested traffic, because it is reasonable to assume that congestion usually occurs around the area after 314 the earthquake. In addition, we again assume the weights for objectives 1, 2, and 3 are 0.6, 0.1, and 0.3, respectively.
C
O
A
D
B
E F
O: San Fernando (Depot) A: Calabasas B: Beverly Hills C: Santa Clarita D: Burbank E: Palmdale F: Pasadena G: Duarte H: Culver City I : Paramount G
H
I FIGURE 2 Transportation Network and Sub-networks 315 It is common to involve resources from a variety of organizations in a disaster relief operation. The total number 316 of vehicles was assumed to be 400 from 20 different organizations (e.g. American Red Cross, military units, etc.). 317 Each organization is responsible for servicing the delivery tasks assigned from the disaster operations manager, and 318 each organization is also responsible for managing its own fleet to accomplish the relief effort. As a result, during 319 seven days of operations based on the data described above and the proposed new model, a total of 621 assignments 320 of delivery tasks had been made to different organizations, and this was equivalent to 12,420 deliveries by trucks. 321 Indeed, among the three types of items, an average of 90.1% of prescription medication was delivered in all nine 322 nodes, while only about 70% and 16.4% of water and food, respectively, were delivered on average. In fact, these 323 numbers reveal the compromise among objectives, compared with 100.0% delivery of medication, 78.9% delivery of 324 water, and 42.6% delivery of food in the best scenario, which is best performance we can achieve if all resources are 325 used to deliver one type of items. We note that only 30.8%, 32.5%, and 7.5% of demand of prescription medication, 326 water, and food, respectively, were satisfied during the time period when the demand arose -- these low numbers are 327 due to the soft time window feature in the model which allowed delayed satisfaction of demand. In addition, it is 328 interesting to see that the full truck load of a single type item is a preferred method of delivery in our application, 329 when the overall vehicle capacity is not capable of satisfying all demand; therefore, if extra capacity is available on 330 vehicles to the same demand locations, more of the same type of items are carried on vehicles. 331 Discussion 332 A major feature of our proposed model is its ability to prioritize delivery. To test this feature of our model, we 333 attempted a comparison with a similar model in the literature. Balcik et al. (22) proposed a model to deliver relief 334 supplies in disasters. Although our model and theirs have the same purpose, they are different for two reasons. The first 335 difference is that Balcik et al.(22) consider two types of supplies. The first type are critical items for which demand
Lin, Y-H, Batta, R., Rogerson, P.A., Blatt, A., Flanigan, M., and Lee, K.
12
336 occurs once at the beginning of the planning horizon (e.g. shelters, blankets) and has to be fully satisfied during the 337 planning horizon (i.e., a hard constraint in the model). The second type of items are those that are consumed regularly 338 and whose demand occurs periodically over the planning horizon (e.g. food, prescription medication, and water), and 339 cannot be backordered if it is not satisfied on time. In our model, we are only interested in the second type of items and 340 backorders are permitted. The second difference is that Balcik et al. (22) do not consider soft time windows, which 341 means that demand must be served immediately when it occurs. 342 To facilitate the comparison of our model with that of Balcik et al. (22) we assumed that the demand of shelters 343 after the earthquake is zero since our interest is not in this type of item. Therefore, the total available capacity of 344 vehicles would not be affected because of shipment of this type of item. To conform to the Balcik et al. model, 345 we collapsed our model to one in which backorder is not permitted and soft time windows are not considered. In 346 addition, we adjusted the weights of the three objectives from the original (0.6,0.1,0.3) to (0.5,0.5,0) since they only 347 considered the penalty cost due to unsatisfied demand and travel cost in their model. We first applied their model 348 to obtain the solution, and then used their travel cost as the budget limit in our model in order to get comparable 349 results. The comparison is shown in TABLE 2, in two parts. Part A in TABLE 2 indicates the percentage of demand 350 being delivered in each time period and Part B indicates the number of injuries or households suffering a shortage of 351 items. It shows that though their model reveals a prioritized delivery pattern similar to ours, their model was unable to 352 concentrate on delivering the item with the highest priority (e.g. prescription medication). In contrast, our collapsed 353 model showed a significant ability to deliver the highest priority item. The improved performance of our model is due 354 to the penalty cost function structure as shown in Equation 1. Furthermore, it is apparent that our collapsed model 355 provides superior results to that of Balcik et al. under the same budget. TABLE 2 Comparison of Logistics Performance between Models
t=1 t=2 t=3 t=4 t=5 t=6 t=7
A. Percentage of Satisfied Demand
Average
Medication: Balcik's model Proposed model (collapsed) Water: Balcik's model Proposed model (collapsed) Food: Balcik's model Proposed model (collapsed)
85.4% 100.0% 54.2% 76.0% 12.2% 12.1%
84.3% 100.0% 58.1% 77.8% 12.7% 12.2%
86.7% 100.0% 59.1% 78.4% 13.8% 13.0%
91.9% 100.0% 61.7% 78.9% 10.9% 14.0%
87.4% 100.0% 56.2% 79.5% 12.2% 15.0%
91.9% 100.0% 61.6% 38.5% 12.8% 8.6%
76.8% 95.3% 58.1% 12.8% 10.1% 8.7%
86.4% 99.4% 58.3% 64.6% 15.6% 12.0%
B. Number of Injuries or Households without Sufficient Supply
Total
Medication: Balcik's model Proposed model (collapsed) Water: Balcik's model Proposed model (collapsed) Food: Balcik's model Proposed model (collapsed)
0
216
223
181
106
159
98
982
0
0
0
0
0
0
0
0
0
0 14,282 12,081 11,356 10,230 11,252 59,201
0
0 7,482 6,405 5,998 5,625 5,261 30,771
0
0
0 23,263 21,411 20,328 20,227 85,230
0
0
0 23,285 21,546 20,529 19,524 84,885
356 Conclusions and Future Work 357 This paper proposes a new logistics model for the emergency supply of critical items in the aftermath of a disaster. 358 Our model considers multi-items, multi-vehicles, multi-periods, soft time windows, and a split delivery strategy, and 359 is formulated as a multi-objective integer programming model. The distinguishing feature of our work is the consider360 ation of delivery priorities of different items. In addition, a heuristic approach is developed, named the Decomposition
Lin, Y-H, Batta, R., Rogerson, P.A., Blatt, A., Flanigan, M., and Lee, K.
13
361 and Assignment heuristic (DAH), to overcome the computational challenge of enumerating all possible tours. The per362 formance of the approach is analyzed and its efficiency is investigated. We found that, in general, the DAH approach 363 provides solutions in reasonable computational time while it has about a 4.3% reduction in solution quality compared 364 to the other two tour determination approaches. 365 To verify the importance of the new model for delivery tasks containing prioritized delivery requests, we conducted 366 a case study of an earthquake scenario in Los Angeles County. For this case study, our model is capable of satisfying 367 90.1% of prescription medication demand, 70% of water demand, and 16.4% of food demand, under the limited 368 delivery capacity of vehicles and limited working time in each time period. The results from the case study showed 369 that the model performed well in this disaster relief operation. Further analysis showed that our model performed 370 better than a model in the literature by Balcik et al. (22) which has a similar purpose to ours. 371 We suggest three directions for future work. The first is to investigate the robustness of our model with respect to 372 uncertainty in demand values, congestion levels, network accessibility, and correlations of node locations with respect 373 to the highway systems. The second is to develop more efficient multi-objective optimization methodologies for this 374 type of problem and to perform a trade-off analysis to understand the compromises among different goals. The third is 375 to consider a distributed scenario in which several temporary depots are required to be located and serve as "bridges" 376 between the major depot and nodes.
377 ACKNOWLEDGMENT 378 This material is based upon work supported by the Federal Highway Administration under Cooperative Agreement 379 No. DTFH61-07-H-00023, awarded to the Center for Transportation Injury Research, CUBRC, Inc., Buffalo, NY. Any 380 opinions, findings, and conclusions are those of the author(s) and do not necessarily reflect the view of the Federal 381 Highway Administration.
382 References
383 [1] U.S. DEPARTMENT OF HEALTH & Human Services. Disasters and Emergencies: Hurricane Katrina. Available at
384
http://www.hhs.gov/disasters/emergency/naturaldisasters/hurricanes/katrina/index.html, 2005.
385 [2] U.S. Geological Survey. Earthquake hazards program: Significant earthquake and news headlines. Available at
386
http://earthquake.usgs.gov/eqcenter/eqinthenews/2005/usdyae/#summary, 2005.
387 [3] Holguґin-Veras, J., N. Peґrez, S. Ukkusuri, T. Wachtendorf and B. Brown. Emergency logistics issues affecting the response to
388
katrina: A synthesis and preliminary suggestions for improvement. In Transportation Research Record: Journal of the Trans-
389
portation Research Board, No. 2022, pages 76­82. Transportation Research Board of the National Academies, Washington,
390
D.C., 2007.
391 [4] Ukkusuri, S. and W. Yushimito. Location routing approach for the humanitarian prepositioning problem. In Transportation
392
Research Record: Journal of the Transportation Research Board, No. 2089, pages 18­25. Transportation Research Board of
393
the National Academies, Washington, D.C., 2008.
394 [5] Horner, M. W. and J. A. Downs. Testing a flexible geographic information system-based network flow model for routing
395
hurricane disaster relief goods. In Transportation Research Record: Journal of the Transportation Research Board, No. 2022,
396
pages 47­54. Transportation Research Board of the National Academies, Washington, D.C., 2007.
397 [6] Ozbay, K. and E. E. Ozguven. Stochastic humanitarian inventory control model for disaster planning. In Transportation
398
Research Record: Journal of the Transportation Research Board, No. 2022, pages 63­75. Transportation Research Board of
399
the National Academies, Washington, D.C., 2007.
400 [7] Chang, M.-S., Y.-C. Lin and C.-F. Hsueh. Vehicle routing and scheduling problem with time windows and stochastic demand.
401
In Transportation Research Record: Journal of the Transportation Research Board, No. 1882, pages 79­87. Transportation
402
Research Board of the National Academies, Washington, D.C., 2004.
403 [8] Ting, C.-J. and C.-H. Chen. Combination of multiple ant colony system and simulated annealing for the multidepot vehicle-
404
routing problem with time windows. In Transportation Research Record: Journal of the Transportation Research Board, No.
405
2089, pages 85­92. Transportation Research Board of the National Academies, Washington, D.C., 2008.
Lin, Y-H, Batta, R., Rogerson, P.A., Blatt, A., Flanigan, M., and Lee, K.
14
406 [9] Taillard, E., P. Badeau, M. Gendreau, F. Guertin and J.-Y. Potvin. A tabu search heuristic for the vehicle routing problem with
407
soft time windows. Transportation Science, 31(2):170­186, 1997.
408 [10] Jung, S. and A. Haghani. Genetic algorithm for the time-dependent vehicle routing problem. In Transportation Research
409
Record: Journal of the Transportation Research Board, No. 1771, pages 164­171. Transportation Research Board of the
410
National Academies, Washington, D.C., 2001.
411 [11] Francis, P. M., K. R. Smilowitz and M. Tzur. The period vehicle routing problem and extensions. In The Vehicle Routing
412
Problem: Latest Advances and New Challenges, pages 73­102. Springer, New York, 2008.
413 [12] Archetti, C. and M. G. Speranza. The split delivery vehicle routing problem: a survey. In The Vehicle Routing Problem:
414
Latest Advances and New Challenges, pages 103­122. Springer, New York, 2008.
415 [13] Zadeh, L. Optimality and non-scalar-valued performance criteria. IEEE Transactions on Automatic Control, AC-8(1):59,
416
1963.
417 [14] Love, R. F. and J. G. Morris. Mathematical Models of road travel distances. Management Science, 25(2):130­139, 1979.
418 [15] Lin, Y.-H. Delivery of Critical Items in a Disaster Relief Operation: Centralized and Distributed Supply Strategies. PhD
419
thesis, University at Buffalo, SUNY, 2010.
420 [16] Cevallos, F. and F. Zhao. Minimizing transfer times in public transit network with genetic algorithm. In Transportation
421
Research Record: Journal of the Transportation Research Board, No. 1971, pages 74­79. Transportation Research Board of
422
the National Academies, Washington, D.C., 2006.
423 [17] Lee, D.-H. and Z. Cao and J. H. Chen and J. X. Cao. Simultaneous load scheduling of quay crane and yard crane in port
424
container terminals. In Transportation Research Record: Journal of the Transportation Research Board, No. 2097, pages
425
62­69. Transportation Research Board of the National Academies, Washington, D.C., 2009.
426 [18] U.S. Census Bureau. United States Census 2000 Data. Available at: http://www.census.gov/main/www/cen2000.html, 2000.
427 [19] Federal Emergency Management Agency. Multi-hazard Loss Estimation Methodology Earthquake Model User Manual.
428
Department of homeland security, FEMA, Mitigation Division, Washington, D.C., 2006.
429 [20] International Federation of Red Cross and Red Crescent Societies. Emergency items catalogue. Available at
430
http://procurement.ifrc.org/catalogue/, 2009.
431 [21] DeBlasio, A.J., A. Zamora, F. Mottley, R. Brodesky, M. E. Zirker and M. Crowder. Effects of Catastrophic Events on
432
Transportation System Management and Operations, Northridge Earthquake - January 17, 1994. U.S. Department of Trans-
433
portation, Washington, DC., 2002.
434 [22] Balcik, B., B. M. Beamon and K. Smilowitz. Last mile distribution in humanitarian relief. Journal of Intelligent Transportation
435
Systems: Technology, Planning, and Operations, 12(2):51­63, 2008.

YH Lin, R Battaa, PA Rogersona, A Blatta, M Flanigana

File: a-logistics-model-for-emergency-supply-of-critical-items.pdf
Author: YH Lin, R Battaa, PA Rogersona, A Blatta, M Flanigana
Published: Thu Jul 29 12:33:25 2010
Pages: 15
File size: 0.69 Mb


, pages, 0 Mb

11 CAANews, 14 pages, 2.03 Mb
Copyright © 2018 doc.uments.com