An Integrated Logistics System for E ective Resource Distribution in Post-disaster Humanitarian Relief Operations by Nader A. B. Al Theeb A dissertation submitted to the Graduate Faculty of Auburn University in partial ful llment of the requirements for the Degree of Doctor of Philosophy Auburn, Alabama May 4, 2014 Keywords: Post-disaster humanitarian relief logistics, Vehicle routing problem, Satellite facilities, Integer programming Copyright 2014 by Nader A. B. Al Theeb Approved by Chase Murray, Chair, Assistant Professor of Industrial and System Engineering Alice Smith, W. Allen and Martha Reed Professor of Industrial and System Engineering Burak Eksioglu, Associate Professor of Industrial and System Engineering Je rey Smith, Joe W. Forehand Jr. Professor of Industrial and System Engineering Abstract After a disaster, distributing supplies and transferring people are critical operations and should be done quickly and fairly, with consideration to di culties associated with limited resources. In this research, more realistic and integrated models are proposed to perform several important logistic operations, including commodity distribution, wounded evacuation, and work{force transfer. To accomplish this, rst, an existing model of Yi and Kumar (2007), which considers two logistic operations (e.g., commodity distribution and wounded evacua- tion), is discussed and corrected. Second, a new model is developed to incorporate a new logistic operation of work{force transfer. Evaluation of this model shows that it has some of the same limitations as the Yi and Kumar (2007) model such as lacking detailed vehicles routes. Third, an integrated logistics system is developed to incorporate all three logistic operations while considering realistic issues such as the determination of detailed vehicle routes. Tiny-scale problems are solved optimally via CPLEX-Concert Technology, while problems of realistic size require the application of new heuristic approaches based on solving the model iteratively and optimally according to speci c routes which are constructed greedily to achieve the maximum resources utilization. Di erent heuristic versions are considered to solve the model, the performances of which are compared to the CPLEX results for numerous randomly generated data sets, and they show excellent results in an extremely short processing time. Local search is used in conjunction with replacement and insertion to improve the suggested solution approaches. In replacement, one customer visit could be replaced by two customer visits in the existing routes, if possible, to increase the number of visits which improves the distribution system. Using insertion, a node may be added to existing routes, if possible, to improve the e ciency ii of vehicles. These searches are applied in di erent ways and the results show that applying them for each candidate solution with higher numbers of iterations (longer termination time) gives the best results among all ways. Finally, a more comprehensive, multi-objective model is developed to consider the use of large vehicles as temporary satellite facilities, serving as mobile supply nodes to improve the e ciency of smaller vehicles. The objectives are considered separately which will minimize the total wounded deviation, the total worker deviations, or the total commodities deviations. Di erent approaches are developed to nd a wide range of solutions for more representative Pareto sets. It is found that there are some clusters in both wounded deviations{worker deviations and wounded deviations{commodities deviations Pareto sets, but they decrease in the commodities deviations{worker deviations Pareto set. Despite the problem of clusters, the suggested solution approaches are capable of nding many solutions in di erent regions of Pareto sets to cover most cases that might be requested from users. iii Acknowledgments I would express my great thanks to my advisor Dr. Chase Murray for his invaluable support and help. Throughout the years at Industrial and Systems Engineering Department, Dr. Murray has been my source of knowledge and the true guide through the very versatile engineering problems we faced. His passion and esteem of work have been, and always will be, inspiring me. Under Dr. Murray supervision, I learned the true qualities of the engineer. His wise advices will always be a guide through my professional career I also would like to extend my great thanks to my committee members, Dr. Alice Smith, Dr.Je rey Smith, and Dr. Burak Eksioglu for their insightful suggestions and recommenda- tions which make my research more realistic and bene cial. Finally, my deepest thanks to my parents, brothers, sisters, relatives, and friends for their encouragement during my life. iv Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Research Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Research Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3 An Overview of Proposed Model Development . . . . . . . . . . . . . . . . . 6 1.3.1 The Baseline Model (YK) . . . . . . . . . . . . . . . . . . . . . . . . 6 1.3.2 A Corrected YK Model (YK?) . . . . . . . . . . . . . . . . . . . . . . 7 1.3.3 Adding the Workforce Transfer Operation (YK?+WT): . . . . . . . . 7 1.3.4 Incorporating Vehicle Routing (HLVRP) . . . . . . . . . . . . . . . . 7 1.3.5 Satellite Facilities and Multiple Objectives (HLVRPSF) . . . . . . . . 7 1.4 Organization of the Dissertation . . . . . . . . . . . . . . . . . . . . . . . . . 8 2 Review of Related Literature . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.1 Pre-Disaster Research . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2 Post-Disaster Research . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2.1 Humanitarian Logistics Operations . . . . . . . . . . . . . . . . . . . 15 2.2.2 Objectives in Emergency Logistics . . . . . . . . . . . . . . . . . . . . 16 2.2.3 Review of Solution Approaches in Humanitarian Relief Studies . . . . 16 2.3 Vehicle Routing Problem (VRP) . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.3.1 Capacitated VRP (CVRP) . . . . . . . . . . . . . . . . . . . . . . . . 18 2.3.2 VRP with Time Windows (VRPTW) . . . . . . . . . . . . . . . . . . 19 v 2.3.3 Multi-Depot VRP (MDVRP) . . . . . . . . . . . . . . . . . . . . . . 19 2.3.4 VRP with Split Delivery (VRPSD) . . . . . . . . . . . . . . . . . . . 20 2.3.5 Periodic VRP (PVRP) . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.3.6 VRP with Satellite Facilities (VRPSF) . . . . . . . . . . . . . . . . . 20 2.4 Satellite Facilities Research . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.4.1 General SF Research . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.4.2 SF in Humanitarian Relief Research . . . . . . . . . . . . . . . . . . . 23 3 A Baseline Humanitarian Relief Model with Corrections and Improvement . . . 25 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.2 The Yi and Kumar Model (YK)-Problem Description . . . . . . . . . . . . . 26 3.2.1 Notations and Formulation . . . . . . . . . . . . . . . . . . . . . . . . 27 3.2.2 A Corrected Formulation . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.2.3 An Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.3 Incorporating Workforce Transfer (YK?+WT) . . . . . . . . . . . . . . . . . 33 3.3.1 Notation and Formulation . . . . . . . . . . . . . . . . . . . . . . . . 34 3.3.2 An Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 4 Humanitarian Logistics Vehicle Routing Problem (HLVRP) . . . . . . . . . . . . 39 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 4.2 Problem Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.3 An Overview of the HLVRP Model . . . . . . . . . . . . . . . . . . . . . . . 42 4.4 Notations and Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 4.4.1 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 4.4.2 The HLVRP Formulation . . . . . . . . . . . . . . . . . . . . . . . . 48 4.5 Model Veri cation by Example . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.5.1 Example Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 4.6 Solution Approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 vi 4.6.1 Heuristic Description . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 4.7 Numerical Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 4.7.1 Experimental Design . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 4.7.2 Tiny Scale Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 4.7.3 Small Scale Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 4.7.4 Medium Scale Problems . . . . . . . . . . . . . . . . . . . . . . . . . 91 4.7.5 Large Scale Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 4.8 Numerical Analysis with Respect to Scales . . . . . . . . . . . . . . . . . . . 97 4.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 5 Incorporating Satellite Facilities and Multiple Objectives . . . . . . . . . . . . . 104 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 5.2 Problem Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 5.2.1 Satellite Facilities in Post{Disaster Relief . . . . . . . . . . . . . . . . 107 5.3 An Overview of the HLVRPSF Model . . . . . . . . . . . . . . . . . . . . . . 109 5.4 Notations and Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 5.4.1 The HLVRPSF Formulation . . . . . . . . . . . . . . . . . . . . . . . 117 5.5 Numerical Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 5.5.1 Examples to Demonstrate SF Bene ts . . . . . . . . . . . . . . . . . 128 5.6 Description of the HLVRPSF Solution Approach . . . . . . . . . . . . . . . . 131 5.7 Solution Approach for the HLVRPSF . . . . . . . . . . . . . . . . . . . . . . 133 5.7.1 Route Construction for Various Objectives . . . . . . . . . . . . . . . 142 5.7.2 Generating Candidate Solutions for a Particular Objective . . . . . . 156 5.7.2.1 A Linearly{Weighted Combination of Objectives (LWCO) . 156 5.7.2.2 Single Objective with Individual Minimum Resource Usage Constraints (SOIMRUC) . . . . . . . . . . . . . . . . . . . . 158 5.7.2.3 Single Objective with Aggregate Minimum Resource Usage Constraints (SOAMRUC1) . . . . . . . . . . . . . . . . . . 162 vii 5.7.2.4 Single Objective with Aggregate Minimum Resource Usage Constraints to Fill Free Space (SOAMRUC2) . . . . . . . . 166 5.7.2.5 Single Objective Solved in Multiple Stages (SOSMS) . . . . 169 5.7.2.6 Single Objective with Weighted Penalties (SOWP) . . . . . 173 5.8 Numerical Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177 5.8.1 Experimental Design . . . . . . . . . . . . . . . . . . . . . . . . . . . 177 5.8.2 Tiny Scale Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178 5.8.3 Small Scale Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 180 5.8.4 Medium Scale Problem . . . . . . . . . . . . . . . . . . . . . . . . . . 181 5.8.5 Large Scale Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 182 5.9 Hybrid Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184 5.10 Case Study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190 5.10.1 Case Study Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190 5.10.2 Comparison between Multi{objective and Single Objective Models . . 193 5.10.3 Case Study Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194 5.11 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197 6 Conclusion and Opportunities for Future Research . . . . . . . . . . . . . . . . . 200 6.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200 6.2 Future Research . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208 Appendices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215 A Large Scale Set- HLVRPSF Model . . . . . . . . . . . . . . . . . . . . . . . . . 216 B Medium Scale Set- HLVRPSF Model . . . . . . . . . . . . . . . . . . . . . . . . 223 C Small Scale Set- HLVRPSF Model . . . . . . . . . . . . . . . . . . . . . . . . . 231 D Tiny Scale Set- HLVRPSF Model . . . . . . . . . . . . . . . . . . . . . . . . . . 236 viii List of Figures 1.1 Overview of the proposed research objectives . . . . . . . . . . . . . . . . . . . 4 3.1 Example solution using the YK? model. . . . . . . . . . . . . . . . . . . . . . . 33 3.2 Example solution from the YK?+WT model. . . . . . . . . . . . . . . . . . . . . 36 4.1 Detailed logistic plan for all vehicles . . . . . . . . . . . . . . . . . . . . . . . . 56 4.2 Local search operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 4.3 Gap and computation time for tiny scale sets . . . . . . . . . . . . . . . . . . . 87 4.4 Gap and computation time for small scale sets . . . . . . . . . . . . . . . . . . . 90 4.5 Gap and computation time for medium scale sets . . . . . . . . . . . . . . . . . 93 4.6 Gap and computation time for large scale sets . . . . . . . . . . . . . . . . . . . 96 4.7 Heuristic-0 and Heuristic-B vs. scale . . . . . . . . . . . . . . . . . . . . . . 98 4.8 Gap averages produced by Heuristics-A vs. size scales . . . . . . . . . . . . . 99 4.9 Gap average comparison for all proposed heuristics at di erent size scales . . . . 100 4.10 Percentages of how many times best solution is produced . . . . . . . . . . . . . 101 5.1 A humanitarian relief network including candidate locations for a large vehicle (LV) to serve as a satellite facility. . . . . . . . . . . . . . . . . . . . . . . . . . 108 ix 5.2 A comparison of vehicle routes when SFs are considered. . . . . . . . . . . . . . 109 5.3 Solution of the HLVRPSF model example for both options: with and without using the available SF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 5.4 HLVRPSF model, with SFs vs. without SFs . . . . . . . . . . . . . . . . . . . . 129 5.5 Slow vehicle route in HLVRPSF model- rst approach . . . . . . . . . . . . . . 161 5.6 A vehicle route in the HLVRPSF model obtained by the SOAMRUC2 approach 168 5.7 Detailed Pareto front for a tiny scale set . . . . . . . . . . . . . . . . . . . . . . 179 5.8 Detailed Pareto front for a small scale set . . . . . . . . . . . . . . . . . . . . . 180 5.9 Detailed Pareto front for a medium scale set . . . . . . . . . . . . . . . . . . . . 182 5.10 Detailed Pareto front for a large scale set . . . . . . . . . . . . . . . . . . . . . . 183 5.11 Detailed Pareto front for a tiny scale set with hybrid approach . . . . . . . . . . 186 5.12 Detailed Pareto front for a small scale set with hybrid approach . . . . . . . . . 187 5.13 Detailed Pareto front for a medium scale set with hybrid approach . . . . . . . 188 5.14 Detailed Pareto front for a large scale set with hybrid approach . . . . . . . . . 189 5.15 Detailed Pareto Front for a Case Study Set . . . . . . . . . . . . . . . . . . . . 195 5.16 Objective function value for HLVRPSF and HLVRP solutions . . . . . . . . . . 197 6.1 Communication device e ect . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206 6.2 Communication device: with and without cases . . . . . . . . . . . . . . . . . . 206 x List of Tables 2.1 Common objectives in emergency logistics research. . . . . . . . . . . . . . . . . 16 2.2 Solution approaches employed in previous studies. . . . . . . . . . . . . . . . . . 17 2.3 A comparison of VRP variants. . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.1 Commodity supply and demand over time. . . . . . . . . . . . . . . . . . . . . . 32 3.2 Quantity of evacuation requests over time. . . . . . . . . . . . . . . . . . . . . . 32 3.3 Summary of unsatis ed commodity demand and unserved wounded over time. . 32 3.4 Worker demands and availability at each node over time. . . . . . . . . . . . . . 36 3.5 Summary of unsatis ed commodity demand, unserved wounded, and non{delivered workers over time. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 4.1 A comparison between the HLVRP model and the existing literature. . . . . . . 44 4.2 Demand data, dccit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 4.3 Supply data, sccit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 4.4 Available and needed workers, sWwit and dWwit . . . . . . . . . . . . . . . . . . . . 53 4.5 Wounded awaiting evacuation, dEeit . . . . . . . . . . . . . . . . . . . . . . . . . 54 4.6 Parameter values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 4.7 Unsatis ed demand (commodity deviation values), vCcit . . . . . . . . . . . . . . 54 4.8 Non{evacuated wounded (wounded deviation values), vEeit . . . . . . . . . . . . 55 4.9 Undelivered workers (worker{force deviation values), vWwit . . . . . . . . . . . . 55 4.10 Vehicle routes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 4.11 Solution approach variants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 4.12 HLVRP - design of experiment . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 xi 4.13 HLVRP - xed parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 4.14 Tiny scale data set results (sets 1-25) . . . . . . . . . . . . . . . . . . . . . . . . 84 4.15 Tiny scale data set results (sets 26-50) . . . . . . . . . . . . . . . . . . . . . . . 85 4.16 Tiny scale data set results (sets 51-75) . . . . . . . . . . . . . . . . . . . . . . . 85 4.17 Small scale data set results (sets 1-25) . . . . . . . . . . . . . . . . . . . . . . . 88 4.18 Small scale data set results (sets 26-50) . . . . . . . . . . . . . . . . . . . . . . . 89 4.19 Medium scale data set results (sets 1-25) . . . . . . . . . . . . . . . . . . . . . . 92 4.20 Medium scale data set results (sets 26-50) . . . . . . . . . . . . . . . . . . . . . 92 4.21 Large scale data set results (sets 1-25) . . . . . . . . . . . . . . . . . . . . . . . 94 4.22 Large scale data set results (sets 26-50) . . . . . . . . . . . . . . . . . . . . . . . 95 5.1 Summary of the HLVRPSF example solution for both options: with and without using the available SF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 5.2 SOAMRUC2 vs. SOIMRUC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168 5.3 Di erent possibilities of SOSMS . . . . . . . . . . . . . . . . . . . . . . . . . . . 170 5.4 HLVRPSF { compare all approaches . . . . . . . . . . . . . . . . . . . . . . . . 176 5.5 HLVRPSF - design of experiment . . . . . . . . . . . . . . . . . . . . . . . . . . 178 5.6 Hybrid approach time limits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186 5.7 Case study parameters and Data . . . . . . . . . . . . . . . . . . . . . . . . . . 192 5.8 Objective function values for the HLVRPSF and HLVRP solutions . . . . . . . 196 A.1 Large scale { set parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216 A.2 Demand { rst type (dC1it) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216 A.3 Demand { second type (dC2it) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217 A.4 Demand { third type (dC3it) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217 A.5 Supply { rst type (sC1it) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217 A.6 Supply { second type (sC2it) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218 xii A.7 Supply { third type (sC3it) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218 A.8 Available workers { rst category (sW1it) . . . . . . . . . . . . . . . . . . . . . . 218 A.9 Available workers { second category (sW2it) . . . . . . . . . . . . . . . . . . . . . 218 A.10 Requested workers { rst category (dW1it) . . . . . . . . . . . . . . . . . . . . . . 219 A.11 Requested workers { second category (dW2it) . . . . . . . . . . . . . . . . . . . . 219 A.12 Waiting evacuees { rst level (dE1it) . . . . . . . . . . . . . . . . . . . . . . . . . 220 A.13 Waiting evacuees { second level (dE2it) . . . . . . . . . . . . . . . . . . . . . . . 220 A.14 Vehicle depots (iVv ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220 A.15 Vehicle speed factors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220 A.16 Vehicle capacities (mVv ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221 A.17 Satellite facility depots (iFf ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221 A.18 Satellite facility speed factors . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221 A.19 Satellite facility capacities (mFf ) . . . . . . . . . . . . . . . . . . . . . . . . . . 221 A.20 Mass of commodities, workers, and wounded (mCc , mEe , and mWw ) . . . . . . . . 221 A.21 Priorities (pCci, pEei, and pWwi) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221 A.22 Distance matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222 B.1 Medium scale { set parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . 223 B.2 Demand { rst type (dC1it) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223 B.3 Demand { second type (dC2it) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223 B.4 Demand { third type (dC3it) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224 B.5 Demand { fourth type (dC4it) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224 B.6 Demand { fth type (dC5it) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224 B.7 Supply { rst type (sC1it) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225 B.8 Supply { second type (sC2it) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225 B.9 Supply { third type (sC3it) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225 xiii B.10 Supply { fourth type (sC4it) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225 B.11 Supply { fth type (sC5it) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225 B.12 Available workers { rst category (sW1it) . . . . . . . . . . . . . . . . . . . . . . . 225 B.13 Available workers { second category (sW2it) . . . . . . . . . . . . . . . . . . . . . 226 B.14 Available workers { third category (sW3it) . . . . . . . . . . . . . . . . . . . . . . 226 B.15 Available workers { fourth category (sW4it) . . . . . . . . . . . . . . . . . . . . . . 226 B.16 Requested workers { rst category (dW1it) . . . . . . . . . . . . . . . . . . . . . . 226 B.18 Requested workers { third category (dW3it) . . . . . . . . . . . . . . . . . . . . . . 227 B.17 Requested workers { second category (dW2it) . . . . . . . . . . . . . . . . . . . . . 227 B.19 Requested workers { fourth category (dW4it) . . . . . . . . . . . . . . . . . . . . . 228 B.20 Waiting evacuees { rst level (dE1it) . . . . . . . . . . . . . . . . . . . . . . . . . 228 B.21 Waiting evacuees { second level (dE2it) . . . . . . . . . . . . . . . . . . . . . . . . 228 B.22 Waiting evacuees { third level (dE3it) . . . . . . . . . . . . . . . . . . . . . . . . . 229 B.23 Vehicle depots (iVv ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229 B.24 Vehicle speed factors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229 B.25 Vehicle capacities (mVv ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229 B.26 Satellite facility depots (iFf ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229 B.27 Satellite facility speed factors . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229 B.28 Satellite facility capacities (mFf ) . . . . . . . . . . . . . . . . . . . . . . . . . . 230 B.29 Mass of commodities, workers, and wounded (mCc , mWw , and mEe ) . . . . . . . . 230 B.30 Priorities (pCci, pWwi, and pEei) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230 B.31 Distance matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230 C.1 Small scale { set parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231 C.2 Demand { rst type (dC1it) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231 C.3 Demand { second type (dC2it) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231 xiv C.4 Demand { third type (dC3it) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232 C.5 Supply { rst type (sC1it) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232 C.6 Supply { second type (sC2it) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232 C.7 Supply { third type (sC3it) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232 C.8 Available workers { rst category (sW1it) . . . . . . . . . . . . . . . . . . . . . . . 232 C.9 Available workers { second category (sW2it) . . . . . . . . . . . . . . . . . . . . . 232 C.10 Requested workers { rst category (dW1it) . . . . . . . . . . . . . . . . . . . . . . 233 C.11 Requested workers { second category (dW2it) . . . . . . . . . . . . . . . . . . . . . 233 C.12 Waiting evacuees { rst level (dE1it) . . . . . . . . . . . . . . . . . . . . . . . . . 233 C.13 Waiting evacuees { second level (dE2it) . . . . . . . . . . . . . . . . . . . . . . . 233 C.14 Vehicle depots (iVv ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233 C.15 Vehicle speed factors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234 C.16 Vehicle capacities (mVv ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234 C.17 Satellite facility depots (iFf ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234 C.18 Satellite facility speed factors . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234 C.19 Satellite facility capacities (mFf ) . . . . . . . . . . . . . . . . . . . . . . . . . . 235 C.20 Mass of commodities, workers, and wounded (mCc , mWw , and mEe ) . . . . . . . . 235 C.21 Priorities (pCci, pWwi, and pEei) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235 C.22 Distance matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235 D.1 Tiny scale { set parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236 D.2 Demand { rst type (dC1it) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236 D.3 Demand { second type (dC2it) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236 D.4 Supply { rst type (sC1it) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236 D.5 Supply { second type (sC2it) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236 D.6 Available workers { rst category (sW1it) . . . . . . . . . . . . . . . . . . . . . . . 237 xv D.7 Available workers { second category (sW2it) . . . . . . . . . . . . . . . . . . . . . 237 D.8 Requested workers { rst category (dW1it) . . . . . . . . . . . . . . . . . . . . . . 237 D.9 Requested workers { second category (dW2it) . . . . . . . . . . . . . . . . . . . . 237 D.10 Waiting evacuees { rst level (dE1it) . . . . . . . . . . . . . . . . . . . . . . . . . 237 D.11 Vehicle depots (iVv ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237 D.12 Vehicle speed factors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238 D.13 Vehicle capacities (mVv ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238 D.14 Satellite facility depots (iFf ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238 D.15 Satellite facility speed factors . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238 D.16 Satellite facility capacities (mFf ) . . . . . . . . . . . . . . . . . . . . . . . . . . 239 D.17 Mass of commodities, workers, and wounded (mCc , mWw , and mEe ) . . . . . . . . 239 D.18 Priorities (pCci, pWwi, and pEei) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239 D.19 Distance matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239 xvi Chapter 1 Introduction Each year, natural and man-made disasters result in catastrophic loss of life, critical injuries, and debilitating economic impacts worldwide. In 2010, for example, a total of 385 natural disasters killed more than 297,000 people, a ected over 217 million others and caused $123.9 billion in economic damages worldwide (Sapir et al. 2010). In the United States, the Federal Emergency Management Agency (FEMA) reported 99 major and 29 emergency declarations in 2011, FEMA (2013). In response to the large number of disasters experienced in the last 20 years, an increas- ing amount of research in engineering, medicine, and social sciences has been conducted to aid in recovery in the aftermath of these events. Logistics is one of the most important research elds that could help save lives, especially when the resources are distributed fairly and in a timely manner. A recent survey by the Fritz Institute investigated the importance of logistics for humanitarian relief after a tsunami. Their ndings indicate that 88% of the relief organizations had to reallocate their most experienced logisticians to sta the tsunami relief e orts. Furthermore, without adequate supply chain systems in place, the majority of organizations relied on solutions using Excel spreadsheets or manual processes for tracking goods in the eld. Not surprisingly, 62% of the organizations? plans fell short of needs and only 58% of organizations used logisticians in their assessment teams, Firtz Institute (2013). With many de ciencies existing in humanitarian relief logistics, the focus of this research is to address some of these shortcomings by developing realistic models and constructing solution approaches capable of solving these models with reasonable computational e ort. Altay and Green (2006) divided the disaster operations into four main categories; miti- gation, preparedness, response, and recovery. The rst two categories are performed before 1 disasters, so they are called pre-disaster operations and include pre-disaster planning (c.f. Chang et al. (2007), Rawls and Turnquist (2010), and Campbell and Jones (2011)) and con- struction of warehouses (c.f. Widener and Horner (2011)). The second two categories are done after disasters, so they are called post-disaster operations. The goals of post-disaster humanitarian relief logistics are to provide rapid delivery of essential commodities to sur- vivors (e.g. food, water, medicine), to evacuate wounded survivors in the most e cient manner possible, given limited resources and potentially impassable roadways (c.f. Yi and Kumar (2007) and Yi and Ozdamar (2007)), debris removal (c.f. Fetter and Rakes (2011)) and construction of temporary warehouses (c.f. Widener and Horner (2011)). This research presents optimization models to focus on post-disaster logistic operations such as commodity delivery, wounded evacuation, and assignment of relief workers to regions a ected by the event. This problem is complicated by a number of factors. First, workforce transfer is di cult due to operational complexity and the variety of skills required (i.e. doctors, nurses, and drivers). Second, besides demand distribution, vehicles have to evacuate the wounded. Third, demand almost certainly exceeds the available supply. Fourth, vehicles are working in an environment of damaged roads and infrastructure. Fifth, because vehicles are donated from di erent sources, they have a variety of speci cations in size, capacity, and speed. Finally, large vehicles, which can not be used in cases of partially destroyed roadways, require long load, unload, and travel times, and thus require utilization in di erent ways. Several existing studies in the literature have proposed approaches to post-disaster hu- manitarian relief logistics e orts; however, to the best of our knowledge, no study has consid- ered more than two logistic operations (e.g., commodity distribution, wounded evacuation, and workforce transfer) in the same model, and no study has considered workforce assign- ment and transfer in conjunction with other logistic operations. There are also no studies that utilize large and small vehicles in di erent ways. Accordingly, new models, and corre- sponding solution approaches, are proposed to address these shortcomings. 2 In the proposed models, many vehicle routing problem (VRP) variants are considered, including split deliveries, multiple depots, multiple commodities, heterogeneous vehicles, and multiple periods. Furthermore, the suggested models in this research consider dynamic supply and demand changes, hence they will be solved for multiple time periods and resolved at the beginning of each new time horizon. More details about these models are discussed in later chapters. The remaining sections of this chapter address the research objectives in Section 1.1, list the research contributions in Section 1.2, and describe all models that are discussed or developed in this dissertation in Section 1.3 . 1.1 Research Objectives This research considers mixed integer models to optimize the service performance of a post-disaster logistic system and solve the problems that humanitarian agencies encounter during relief work. To do so, we propose di erent models, each of which o ers improvements over previous studies, as follows: All studies in the literature consider at most two logistic operations in post{disaster situations while utilizing many unrealistic assumptions. The rst research objective is to develop more realistic and e cient models to incorporate more than two logistic operations that can be used e ciently in post-disaster situations. These operations include commodity delivery, wounded evacuation, and assignment of relief workers. In post{disaster situations, utilizing large vehicles in distribution is not easy because of blocked roads and substantial loading and unloading times. In the literature of humanitarian relief operations, there are no studies that utilize large vehicles in non- traditional ways. The second research objective is to develop a model to use large vehicles as mobile satellite facilities (SFs) that serve as movable supply nodes to im- prove the performance of distribution systems. These SFs are used to replenish small 3 vehicles without returning back to supply depots, which saves time and increases the delivered amount. With the improved model from previous research objectives, the third research objec- tive is to use multiple objectives instead of a single objective. The objectives used are relevant to the case of post-disaster, including minimizing total commodities de- viations, total workers deviations, and total wounded deviations. Deviations are the di erence between requested amounts and delivered amounts. These objectives are used because they are the most suitable objectives in case of a disaster. The goal of using multi-objective optimization is to provide a wide range of solutions to the users. Create di erent heuristic approaches to solve these models in a reasonable time. These approaches are supposed to provide full a detailed distribution plan for each individual vehicle based on a given route. Suggest di erent techniques to improve the heuristic approaches to o er di erent so- lution platforms with di erent performances and computation times. Figure 1.1 shows the ow of research objectives. Figure 1.1: Overview of the proposed research objectives 4 1.2 Research Contributions This research e ort aims to provide many contributions. First, it will provide a corrected formulation of the humanitarian logistics model of Yi and Kumar (2007). This represents an admittedly minor contribution, but enables its use as a basis for future models. The second contribution of this research is the construction of a humanitarian logistics model incorporating the most important operations that must be performed after a disas- ter, with consideration of realistic assumptions. The literature in this eld shows that the available models incorporate two operations at most (i.e. wounded evacuation and demand distribution). By contrast, the suggested model in this research will incorporate three op- erations within a single framework by adding the work-force assignment operation to those previously mentioned. Third, the model in the second contribution has the same limitations as that of Yi and Kumar (2007) such that it does not produce a detailed route for each vehicle, needs a heuristic to build up a detailed solution for each vehicle, and considers vehicles with same speed. A new model is developed to explicitly consider individual vehicle routes, a feature that is noticeably absent from the work of Yi and Kumar (2007). This model represents the rst major contribution in this research. Fourth, the incorporation of larger vehicles as temporary satellite facilities (SF) repre- sents a novel approach to improve humanitarian relief e orts. SFs represent movable supply nodes that can supply distribution vehicles, saving time, and enhancing the distribution system. Fifth, e cient heuristic approaches will provide high-quality solutions to the model de- veloped in the third contribution with a short computation time. It depends in constructing route for all vehicles using greedy approaches, and then solve complete model at speci c routes ( xed binary variables) using CPLEX. This approach allows CPLEX to nd an opti- mal solution for the modi ed model in extremely short time such that, in large scale problem, it gives a feasible solution in less than 5 minutes whereas CPLEX fails to give any feasible 5 solution in 16 hours. The procedure is repeated iteratively to nd di erent vehicle routes and solutions taking the advantage of some good routes inherited from previous iterations. Furthermore, di erent local search variants are applied iteratively to this approach to nd more improved solutions. Finally, the heuristic approaches that were developed in previous contribution will be modi ed to be suitable to solve the model developed in the fourth contribution. Hence the model is using SF and multi-objective, the proposed heuristic is capable to take SFs in consideration and provide representative Pareto sets that include wide range of solutions in short computation time. 1.3 An Overview of Proposed Model Development In this section, a short description of the ve models included in this research is presented which makes the understanding of the following chapters easier. Detailed information about each model is contained in later chapters. 1.3.1 The Baseline Model (YK) There are many insightful studies related to humanitarian relief in post-disaster opera- tions, including Ozdamar et al. (2004), Yi and Kumar (2007), and Yi and Ozdamar (2007), all of which include two operations and use an objective function well-suited to the prob- lem at hand. Of these, the model of Yi and Kumar (2007), which we will denote as YK, was selected to be the starting point for this research. It incorporates multiple commodity types, split deliveries, di ering vehicle capacities, multiple depots, multiple time periods, and wounded evacuation. A complete description of the YK model is presented in Chapter 3. 6 1.3.2 A Corrected YK Model (YK?) There are some minor errors in the YK model such as missing indices and missing variables in some constraints that cause infeasible solutions. A corrected version of this model, denoted as model YK?, is presented in Section 3.2.2. 1.3.3 Adding the Workforce Transfer Operation (YK?+WT): A new model is built to incorporate one more logistic operation. In the YK? model, there are some potential operations that could be added to make it more robust. The most impor- tant operation that could improve it is to use available vehicles to transfer the workforce from the supply nodes or hospitals to the demand nodes to help in distribution, medication, and evacuation of wounded people. Although Dolinskaya et al. (2011) have suggested workforce management as an important area for future research, and Jiang et al. (2012) have suggested a focus on the interdependency of operations and work- ow across di erent stakeholders, no models exist that incorporate workforce management in humanitarian relief e orts. This model formulation with a numerical example is presented in Chapter 3.3 1.3.4 Incorporating Vehicle Routing (HLVRP) One drawback of the YK?+WT model is that it neglects vehicle routing. A new model, the humanitarian logistics vehicle routing problem (HLVRP), is proposed to incorporate vehicle routing decisions. In particular, solutions to the HLVRP provide detailed vehicle tracking information that is not a orded by the aforementioned models. Details about this model { including di erences from previous models, a mathematical formulation, a numerical analysis, and an example { are explained in Chapter 4. 1.3.5 Satellite Facilities and Multiple Objectives (HLVRPSF) Improving the distribution system is the ultimate goal of this research. A new model is developed to incorporate the operations in the HLVRP model with improved logistics 7 operations. We will call this model humanitarian logistics vehicle routing problem with satellite facilities (HLVRPSF). The bene t of this model is to use large vehicles as satellite facilities (SFs) to deliver commodities faster, where using large vehicles as satellite facilities incurs no construction cost or time comparing with construction xed warehouses. The model with SF considers three objectives in a truly multi{objective manner. The rst objective is to minimize unsatis ed demand, the second objective is to minimize unserved workforce, and the third objective is to minimize unserved wounded evacuees. In the HLVRP model, priorities are de ned by users and used in a single objective function to di erentiate between wounded, workers, and commodities categories. Whereas, in the HLVRPSF model, considering these objectives separately overcomes the problem of using priorities which could cause undesirable results when unsuitable values are used. Formulation, solution approaches, and numerical analysis of this model are presented in Chapter 5. 1.4 Organization of the Dissertation This dissertation is organized as follows. In Chapter 2, an extensive literature review of related studies is provided. Chapter 3 includes the model from Yi and Kumar (2007), the corrected model of Yi and Kumar (2007), and develops the rst model to incorporate work-force transfer with demand distribution and wounded evacuation. In Chapter 4, a new model is developed to incorporate all three operations while con- sidering detailed routes for each individual vehicle. To utilize the large vehicles as mobile satellite facilities, the last model is developed in Chapter 5 which includes the formula- tion, solution approaches, and discussion about di erent multi-objective treatments. Finally, Chapter 6 concludes this research and suggests future work. 8 Chapter 2 Review of Related Literature This section reviews the literature related to this research and is organized as follows. Section 2.1 summarizes related pre-disaster research, while Section 2.2 summarizes and de- scribes relevant post-disaster research. Section 2.3 explains the most relevant VRP variants and how they are related to this research. Finally, Section 2.4 reviews existing satellite facility (SF) research and describes how this research area will be applied to the proposed work. 2.1 Pre-Disaster Research Pre-disaster research is concerned with all activities performed before a disaster, such as determining facility locations in areas with a high risk of disaster, and determining the quantities of rst aid materials, food, and other supplies to store in those facilities. Although this research does not consider pre-disaster planning, the following articles could be helpful for post-disaster cases. For example, most of the permanent suppliers? locations found in pre-disaster models are used in post-disaster activities. Several optimization models have been developed for pre-disaster planning. For instance, Chang et al. (2007) suggested two models to help relief agencies construct rescue organiza- tions, specify the locations of rescue resource storehouses, allocate rescue resources under capacity restrictions, and distribute rescue resources. They have formulated two stochastic models for the case of a ood disaster. The rst model aims to distribute rescue equipment from the distribution centers of minimum distance to the prede ned rescue areas under dif- ferent rainfall levels. The second model determines the quantity of equipment that should be stored at each location before the rainy season. The objective is to minimize the cost 9 of operations, maintenance, and purchases. These models use non-mathematical approaches to divide the disaster area into groups and a sampling-based approximation to address the stochastic nature of the problem. Similarly, Rawls and Turnquist (2010) proposed an integer programming model to de- termine the locations and quantities of di erent commodities that should be prepositioned in areas having a high disaster risk. The objective is to minimize the xed cost of construct- ing new facilities plus the cost of quantities that will be stored at these locations. Costs of transportation, holding in case of excess, and a penalty in the case of shortage, were also added, based on the di erent possible scenarios with di erent probabilities. The authors assume that the road conditions before and after a disaster are the same (i.e. constant cost), and consider the quantities stored at a supply location to be the only resources for supply. Other research demonstrates parameter speci cation. For example, Campbell and Jones (2011) have de ned the parameters that could a ect the selection of supply points in pre- disaster conditions. These parameters de ne the probability of the disaster destroying the supply points, the distances between points, restocking costs, salvage values, and other variables. Additional literature related to pre-disaster planning can be found in the recent review article of Caunhye et al. (2012). 2.2 Post-Disaster Research Post-disaster research is concerned with all activities performed after a disaster, such as commodity distribution, wounded evacuation, and workforce management. In this section, some studies related to this research are presented. Because the complexity of the post-disaster situation and the limited resources, logistic systems should adopt many important logistical operations. Few studies incorporate more than one operation in the optimization model. For example, Yi and Kumar (2007) suggest a model that includes the objective of minimizing both unsatis ed demand and unserved wounded. It aims to distribute commodities to distribution centers in the a ected areas 10 and evacuate the wounded people to medical centers. Similarly, Yi and Ozdamar (2007), Yan and Shih (2009), Ozdamar and Demir (2012), Balcik et al. (2008) and Ozdamar and Yi (2008) have suggested models with two logistical operations. In Yi and Ozdamar (2007), an integrated capacitated location-routing problem (LRP) is suggested, which is a mixed integer multi-commodity network ow model aimed at the coordination of the transportation of commodities from major supply centers to a ected areas and the transportation of wounded people from a ected areas to temporary and permanent emergency units. Speci cally, the objective is to minimize the total unserved commodities multiplied by their priorities and divided by a standard amount to sustain one wounded, plus the number of unserved wounded people with di erent level of wounded multiplied by its priority for all time periods. The drawback of this model is neglecting vehicle routes and treating the vehicles as commodities passing along arcs. Similarly, Ozdamar and Yi (2008) have suggested a model with minor di erences from the model of Yi and Ozdamar (2007) such as adding limitations to the number of wounded that can be served at each hospital. They used a greedy neighborhood search to solve the model. Because roadway repair a ects the supply distribution, Yan and Shih (2009) have suggested a model to perform these operations with respect to the repair schedule. In a similar way, Wex et al. (2013) suggested a model for the problem of rescue unit scheduling and assignment, where the rescue units are scheduled to process di erent prioritized types of incidents such as res and building collapse. Some studies include a model for evacuation only. For example, Baharanchi et al. (2011) have developed bi-objective integer programming models to evacuate wounded persons after an earthquake. The rst objective is to minimize the number of unsuccessful vehicle visits, and the second is to minimize the total travel distance. Drawbacks include the assumption of only one level of earthquake (six Richter), incorporating only identical vehicles, and decision variables that indicate only the arcs that should be traveled by each vehicle without sequence. Jotshi et al. (2009) have used data fusion analysis to estimate the number of victims who 11 need transfer. Chiu and Zheng (2007) have suggested a model to evacuate multi-priority groups with minimum travel time. On the other hand, some studies only include a model for demand distribution. For example, Ozdamar et al. (2004) have presented a model to minimize the amount of unsatis ed demand for all types of commodities at all nodes and time slots. In the model, vehicles do not necessarily return to the depot, assuming the drivers have contact with coordination centers. The rst of the two models determines the ow plan or quantity that should be transfered through each road. The second model is an integer program to determine the number of vehicles that should pass through each road. Similarly, Balcik et al. (2008) have suggested a model to nd the routes of vehicles with minimum travel cost and unsatis ed demand cost where the route costs are assumed to be known, and Lin et al. (2011) have presented a model to minimize the penalty cost associated with a delay of delivering the demand of di erent types to the nodes at all periods plus the penalty cost of unsatis ed demand. Finally, Afshar and Haghani (2012) have developed a model to distribute the demand while minimizing the total prioritized unsatis ed demand. Some studies have used numerical analysis to develop the procedure for performing some post-disaster operations, but they do not include an optimization model. Sheu (2007) has shown a hybrid fuzzy clustering optimization approach to divide the relief supply network into three levels: supply, distribution, and demand areas. His model starts with processing data numerically to forecast the relief demand based on the number of facilities available in the governmental records. A fuzzy clustering approach classi es a ected area into groups based on the clustering results. Finally, multi-criteria decision making is applied to rank the priority order of groups. This article does not include an optimization model, and instead is a numerical analysis. Similarly, Sheu (2010) used numerical methods to forecast the relief demand, group the a ected areas, and determine the urgency of relief demand; these models do not consider optimization. In the same manner, numerical and statistical analysis are used to determine the bounds and estimations of some parameters and decision 12 variables. For example, Fiedrich et al. (2000) employed statistical methods to nd the estimated number of supplier locations to be used among available facilities. Gong and Batta (2007) used numerical techniques to model the clusters in disaster areas and to allocate/re- allocate ambulances into the clusters. Arora et al. (2010) described a resource allocation approach to optimize regional aid during public health emergencies. Some studies consider models with multiple objectives, such as Liu and Zhao (2007) who have presented a weighted multi-objective model for distributing commodities in emergency logistics. In the model, the objective is to minimize the time needed to move the items from suppliers to distribution centers (DCs) and from DCs to the demand points. The cost of constructing DCs and the cost of unsatis ed demand are also included. In this model, the decision variables represent the demand quantities that should be distributed to each location, without considering the vehicle routes. Using other objectives related to the distribution time, Campbell et al. (2008) have presented a new objective function for relief e ort that depends on the maximum and average arrival times, instead of total distance. They used a model with one vehicle, and then approximated values for some bounds. Besides the time, Vitoriano et al. (2010) added more terms to the objective function. They developed a multi-objective model based on equity, reliability, time, cost, security and priority. A target value for each of these objectives is speci ed, and the deviation variables are de ned as the di erence between the objective and its target value. They assumed a heterogeneous eet of vehicles characterized by capacity, velocity, and variable and xed costs. Two types of nodes were suggested in this single-commodity model: nodes to pick up the commodity and nodes for delivery. A goal programming approach was used to minimize the deviation variables of the objectives. Yuan and Wang (2009) suggested two models to select the paths during the relief dis- tribution. In the rst model, travel speed along each arc was considered while in the second model, chaos, panic and congestion were considered to minimize the number of arcs required to cover all demand locations. 13 Some studies incorporate location determination in post-disaster relief. For example, Widener and Horner (2011) have suggested a hierarchical model to select the best location for facilities in the event of a hurricane to minimize the total distance of serving the nodes with di erent service or demand levels. They neglected vehicle routing, multi-commodity considerations, and di ering costs of facility construction based on location. Tzeng et al. (2007) constructed a multi-objective model to minimize the total cost and total travel dis- tance and maximize the minimal satisfaction. Total cost includes the xed costs associated with constructing supply nodes and transportation. Supply nodes are selected from prede- termined locations. The drawback with this model is that the best locations to construct the supply nodes are selected after a disaster. Distribution can only begin after construction, creating extremely long delays for post-disaster response where time is a critical factor. Barbarosoglu et al. (2002) developed a model for a helicopter logistics system. It is divided into six sub problems: eet consumption, pilot assignment, number of tours for each helicopter, helicopter routing, helicopter transportation (loading and unloading), and refueling scheduling problems. The mathematical model is divided into two models, such that the top level model contains the rst three sub problems, while the base level model contains the last three sub problems. The objective is to minimize the cost of pilots and helicopters in the rst model, and the total distance in the second model. Finally, some researches suggest models that are suitable for small scale problems only. First, Barbarosoglu and Arda (2004) developed a model with two stochastic stages to solve multi-commodity network ow problems. This model was used to solve a small scale problem with 6 demand nodes and 5 supply nodes. Second, Fei et al. (2011) solved a small scale path selection problem for post-disaster situations. The problem solves a 15-node problem using ant colony optimization, with the objective of minimizing the time traveled by all vehicles. Finally, Haghani and Oh (1996) solved two problems, one with 4 nodes and the other with 10 nodes. 14 A recent review article is by Galindo and Batta (2013) includes a full summary about the studies concerning pre-disaster and post-disaster, as well as a discussion on research gaps in the literature. For example, they note the lack of studies on coordination among humanitarian agencies that are working in the same geographical area. New technologies, such as geographical information system (GIS) ans simulation software, have not yet seen widespread adoption. Furthermore, better performance indicators to measure the e ective- ness of proposed models, using interdisciplinary techniques that would be more suitable for the case of disaster, are desirable. Finally, it is suggested that future research should rely upon more realistic assumptions. Another review study has been conducted by Luis et al. (2012), which includes a good summary for the research of disaster relief operations. The following subsections classify the research according to di erent criteria. These classi cations highlight several gaps in the existing literature. 2.2.1 Humanitarian Logistics Operations There are many di erent operations that take place during humanitarian relief e orts. First, demand requirements must be determined, typically via numerical methods to analyze existing demand data and forecast future demands (c.f., Sheu (2007) and Sheu (2010)). Next, emergency resources must be allocated to available facilities (c.f., Fiedrich et al. (2000), Sherali et al. (2004), Gong and Batta (2007), and Arora et al. (2010)). These resources must be distributed to points of demand (c.f., Tzeng et al. (2007), Yuan and Wang (2009), Barbarosoglu and Arda (2004), and Barbarosoglu et al. (2002)). In addition to resource delivery, wounded persons must be evacuated to rst aid areas or hospitals (c.f., Jotshi et al. (2009), Han et al. (2006), Chiu and Zheng (2007), Ozdamar and Yi (2008), Ozdamar and Demir (2012) and Tan et al. (2009)). Most existing research on humanitarian logistics has focused on only one logistic activity at a time. While some research, most notably the works of Ozdamar and Yi (2008), Yi and Kumar (2007), Yi and Ozdamar (2007), Yan and Shih (2009), and Balcik et al. (2008) have 15 incorporated two of these activities within a single model, we are aware of no existing models that have considered three or more of these critical operations within a uni ed framework. Furthermore, the activities of allocating and transferring relief workers are noticeably absent from the literature. 2.2.2 Objectives in Emergency Logistics A variety of objectives have been considered in humanitarian relief optimization models, as highlighted in Table 2.1. Most studies employ traditional objectives such as minimizing cost and time while few use emergency-related objectives such as minimizing unsatis ed demand and unserved wounded. Table 2.1: Common objectives in emergency logistics research. Objective References Minimize distribution time Tzeng et al. (2007), Jotshi et al. (2009), Chiu and Zheng (2007), Ozdamar and Demir (2012) and Yan and Shih (2009) Minimize maximum completion time Gong and Batta (2007), Campbell et al. (2008) Minimize evacuation time Tan et al. (2009) Minimize distribution cost Sheu (2007), Tzeng et al. (2007), Barbarosoglu and Arda (2004), and Balcik et al. (2008) Maximize vehicle tour duration Barbarosoglu et al. (2002) Minimize unsatis ed demand and minimize un- served wounded (in one objective function) Ozdamar and Yi (2008), Yi and Ozdamar (2007), and Yi and Kumar (2007) Maximize demand ll rate Sheu (2007) and Tzeng et al. (2007) Minimize number of fatalities Fiedrich et al. (2000) Multi-objective Lin et al. (2011) (penalty cost of delayed deliv- eries, tours cost, and satisfaction), Yan and Shih (2009) (Minmax repairing, Minmax distribution), Liu and Zhao (2007) (overall cost, e ectiveness, and satisfaction), Naja et al. (2013), and Tzeng et al. (2007) (total cost, travel time, satisfaction) 2.2.3 Review of Solution Approaches in Humanitarian Relief Studies Many previous studies on humanitarian relief relied on commercial integer programming software (e.g. CPLEX, GAMS, LINGO) to solve small-scale problems optimally. For large 16 scale problems, heuristic approaches, such as particle swarm optimization (PSO), modi ed branch-and-bound (MBAB), ant colony optimization (ACO), tabu search (TS), genetic al- gorithm (GA), and simulated annealing (SA) were used. A summary of solution approaches applied to previous emergency studies is contained in Table 2.2. Table 2.2: Solution approaches employed in previous studies. Solution Approaches References Commerical software (CPLEX, GAMS, LINGO) Lin et al. (2011), Yi and Ozdamar (2007), Vitori- ano et al. (2010), Yan and Shih (2009), Widener and Horner (2011), Liu and Zhao (2007), Tzeng et al. (2007), Sheu (2007), Barbarosoglu and Arda (2004), and Balcik et al. (2008) Genetic Algorithm Lin et al. (2011) Ant Colony Yuan and Wang (2009), Yi and Kumar (2007), and Fei et al. (2011) Simulated Annealing Baharanchi et al. (2011) Greedy Neighborhood Search Ozdamar and Yi (2008) Lagrangian relaxation based iterative algorithm Ozdamar et al. (2004) Insertion algorithm Campbell et al. (2008) hierarchical cluster and route procedure Ozdamar and Demir (2012) 2.3 Vehicle Routing Problem (VRP) The classical vehicle routing problem (VRP) is an essential part of this research because it forms the basis for many logistic systems. The VRP will be used to construct the inte- grated logistic system for post-disaster relief, which is the ultimate goal of this research. It should be noted, however, that the VRP must be substantially extended to be applicable to humanitarian relief problems. Such enhancements include incorporating multiple existing VRP variants, considering workforce transfer, and addressing wounded evacuation. In this section, some common VRP variants that are related to this research will be reviewed and explained. The VRP is a very well-known problem in logistics and operations research, and was rst introduced by Dantzig and Ramser (1959). The classical version of the VRP consists of 17 a set of customers with known demands for a single commodity, a eet of identical vehicles, and a single depot. The objective is to minimize the total cost of distribution, where each customer must be visited exactly once. Any violation of one or more of the previous assumptions will result in a new VRP vari- ant. In the next subsections, a short review of relevant variants is presented. A comparison of these variants with the proposed research is provided in Table 2.3. There are some other VRP classes of note that incorporate multiple variants simultaneously (c.f. Bettinelli et al. (2011) and Ho and Haugland (2004)). More details about VRP variants can be found in Toth and Vigo (2002) and Chapter 6 of Barnhart and Laporte (2007), while Cordeau et al. (2002) describe many e ective algorithms to solve VRP problems. Table 2.3: A comparison of VRP variants. Multi Split Time Hetero. Multi SatelliteType CommoditiesDelivery Windows Vehicle Depot Periodic Facilities VRPCVRP VRPTW XMDVRP X VRPSD XPVRP X VRPSF XThisResearch X X X X X X 2.3.1 Capacitated VRP (CVRP) This variant considers identical vehicles and is the simplest extension of the VRP. Al- though this variant will not be considered in this research, it is explained here because it is an important case that is used for building other variants. It is considered as a modi ed multiple traveling salesman problem (MTSP). The only di erence between the two cases is that in the CVRP the capacity of vehicles is nite, not in nite as in MTSP. The terms VRP and CVRP are often used interchangeably because vehicle capacities are typically implied within most VRP formulations. 18 Many studies have considered this variant. For example, Laporte (1992) reviewed the exact and approximate algorithms that have been used to solve the CVRP. The exact al- gorithms include direct tree search, dynamic programming, and integer programming. The heuristics or approximate algorithms include the nearest neighbor, insertion algorithms, and tour improvement procedures. In recent studies, both Baldacci et al. (2008) and Lysgaard et al. (2004), have presented an exact algorithm based on the branch-and-cut to solve the CVRP. More details about the CVRP can be found in Chapters 1{6 of Toth and Vigo (2002). 2.3.2 VRP with Time Windows (VRPTW) In the VRPTW, customers must be visited within pre-determined time windows. This variant was rst presented by Golden and Assad (1986). Chapter 7 of Toth and Vigo (2002) explains details of this variant. Many articles have suggested algorithms to solve the VRPTW (c.f., Wen and Meng (2008) and Ho and Haugland (2004)). While the proposed research e ort does not explicitly consider customer time windows, the time-critical nature of customer demand is certainly important. For example, in the short period of time immediately following a disaster, the golden time, all customers need the demand as soon as possible. For this reason, it is di cult to de ne a time window for when each customer should be supplied. Instead, in the context of humanitarian relief, some urgency parameters that depend on the customer status are developed to attribute higher priority to the most urgent demand needs. 2.3.3 Multi-Depot VRP (MDVRP) The MDVRP addresses cases that have more than one depot, such as distribution centers or stores. If the nodes can be clustered around depots, this problem becomes a multi-CVRP; otherwise, it should be treated as a MDVRP. This problem was rst introduced by Tillman (1969). Desaulniers et al. (1998) studied this variant with time windows and waiting costs. Ho et al. (2008) developed a hybrid genetic 19 algorithm to solve the MDVRP with customer grouping. Soeanu et al. (2011) suggested a decentralized heuristic approach to solve the MDVRP with split delivery. Bettinelli et al. (2011) suggested a branch-and-cut-and-price algorithm to solve VRP with a heterogeneous eet, time windows, and multi depots. In the proposed research e ort, more than one location in the logistic network will be considered as a supply point. 2.3.4 VRP with Split Delivery (VRPSD) The VRPSD occurs when customers may be supplied by more than one vehicle. The mathematical formulation is the same as that of the CVRP, except the single vehicle con- straint, which guarantees that only one vehicle supplies each node, is removed. This variant was rst introduced by Dror and Trudeau (1989). Ho and Haugland (2004) used tabu search to solve VRP with time window and split delivery, and Jin et al. (2007) suggested two stage tabu search to solve VRPSD. In the proposed research, split deliveries are allowed. 2.3.5 Periodic VRP (PVRP) The PVRP is a general case of the CVRP where the distribution could occur over many days or time periods. Beltrami and Bodin (1979) were the rst to describe this case for a waste collection case study. The proposed research may be considered to be a modi ed PVRP, as each demand node may have a di erent demand for each time period. 2.3.6 VRP with Satellite Facilities (VRPSF) In the VRPSF, satellite facilities (SFs) can be used to provide delivery vehicles with additional supplies if needed. In this case, the vehicles could be replenished completely or partially during the distribution without returning back to the depot. At the end of each shift, delivery vehicles may return to the depot. Beltrami and Bodin (1979) were the rst to 20 suggest this variant, while Bard et al. (1998a) suggested a branch-and-cut solution approach. This variant is applicable to the proposed research e ort, where large vehicles may serve as SFs. 2.4 Satellite Facilities Research The term satellite facility appears to lack a universal de nition in the context of logistic networks. Typically, SFs include large vehicles, simple buildings, tents, local stores, or shelters. In the proposed research, large mobile vehicles will be used as satellite facilities whose use a ords improved response to a ected areas. The remainder of this section describes the use of SFs in other research elds, within the area of humanitarian relief, and as they are applied speci cally to the proposed research. 2.4.1 General SF Research Satellite facilities have been successfully deployed across a variety of applications. For example, military camps operating in remote areas often utilize temporary SFs for both housing and supplies. Other short-duration activities such as blood donation drives and weather monitoring stations typically use mobile vehicles as SFs. In industry, the term SF is commonly used in inventory routing problems and multi-echelon inventory systems where the inventory is transfered from the main warehouses to local stores and then to the nal retailers. Bard et al. (1998b) have suggested the use of satellite facilities around a central sup- plier to solve the problem of demand uncertainty which could con ict with the objective of minimizing the annual operating cost of the inventory routing problem (IRP). An IRP arises when a set of customers depends on a supplier to provide them with a certain commodity. The solutions of such cases aims to distribute the commodity and specify the amount of supplies that should be maintained at stores to reduce the chance of stock-out. 21 Bard et al. (1998a) have suggested branch-and-cut to solve the vehicle routing problem with satellite facilities (VRPSF). In this problem vehicles could be replenished at any of the SFs instead of going back to the main depot. In this article, the model consists of n customers with demands from a known distribution, a central depot, and s satellite facilities. Vehicles can be reloaded at the central depot or at any satellite facility. As with many routing problems, the objective is to minimize the cost of distribution. The model was solved in three main steps: identi cation of the customers to visit at each time, assignment of customers to vehicles, and construction of routes for each vehicle. Research on multi-echelon inventory problems often incorporates the use of satellite facilities. Here, inventory is distributed in multiple stages from the main suppliers through multiple levels of transshipment nodes until reaching the end users. Vehicle routing decisions are not always considered within these problems. Clark and Scarf (1960) were the rst to present the multi-echelon inventory system to determine optimal purchasing quantities. Rottkemper et al. (2012) suggested a mixed integer model with two objectives to minimize the total unsatis ed demand and distribution cost. The model allows transshipments between regional depots, and was solved by a rolling horizon solution method. The main drawback associated with this model is that it can be used for only a single item. Jaillet et al. (2002) determined distribution cost approximations in an inventory routing problem with xed satellite facilities. Crainic et al. (2010) proposed a distribution system within a two-echelon- vehicle routing problem. This basic system employs large vehicles that travel from the central depot to a xed number of capacitated satellite facilities. Smaller vehicles transfer the demand from the SFs to customers with xed demands. Such a system keeps large vehicles outside of crowded cities. Perboli et al. (2008) presented a two-echelon model with capacitated vehicle routing to minimize the total cost of transferring goods from the rst level depot to the predetermined SFs. Zhao et al. (2008) presented a three-echelon logistics system consisting of a supplier, a central warehouse, and a group of retailers. The objective is to minimize the overall average 22 cost of the system. This model was solved by a large neighborhood search. Jung and Mathur (2007) suggested a heuristic to solve the two-echelon inventory routing problem with a single warehouse and multiple retailers. Gendron and Semet (2009) suggested path- and arc-based formulations for multi-echelon inventory routing problems. A comprehensive review about this topic can be found in the paper of Paterson et al. (2011). In previous studies, there are many assumptions that limit their use in humanitarian relief e orts. For example, in all existing studies, time is not a critical factor. However, in the proposed research, the primary motivation behind employing SFs is to improve the distribution system and reduce delivery times. Additionally, the previous studies assume that the SF locations are xed and already constructed, or can be selected from many available locations. In this research, SF locations will be changed after each shift based on the new data concerning demand and road conditions. Other assumptions regarding customers with equal demands and customers with unlimited storage capacities are also inappropriate for humanitarian relief. 2.4.2 SF in Humanitarian Relief Research To the best of our knowledge, only Azimi et al. (2012) have used the SF term and applied it in the context of humanitarian relief. The authors have suggested a model to deliver multiple commodities to demand locations through multiple xed SFs. The model results only decide which SFs and node should be visited by each vehicle in a single trip. Many shortcomings are encountered in this research. First, it is not periodic, as a single trip with only one arc for each vehicle is considered. Second, SF locations are predetermined and each node is assigned to a speci c SF with an unknown procedure. Third, it is assumed that the available supply is greater than the overall demand. Finally, the objective function is to minimize the total distance traveled by all vehicles. Some studies have used multi-phase distribution systems in post-disaster situation such as Clark et al. (2013) who developed a model to distribute demand from main suppliers 23 to regional warehouses and then to the recipients. The objective is to minimize unsatis ed demand, operating cost of the vehicles, amount of inventory, and the number of vehicles used. Similarly, Rottkemper et al. (2012) suggested a model with multi-phase distribution to minimize the cost of distribution demand and the running cost of trucks. Finally, Afshar and Haghani (2012) suggested a single logistic operation and multi-phases supply model for demand distribution. In this study, the term \mobile center" is used to de ne the locations where the supplies can be stored for a speci c time. The objective is to minimize the prioritized unsatis ed demand. It can be concluded from the literature that no studies consider SF e ciently in a multi-operation model while considering individual plans for each SF and vehicle. 24 Chapter 3 A Baseline Humanitarian Relief Model with Corrections and Improvement 3.1 Introduction In this chapter, the model of Yi and Kumar (2007) is studied extensively and corrected to make it usable. For the purposes of the proposed research e ort, the so-called YK model was chosen to serve as a baseline model because it is one of the most recent studies that includes two operations (distribution and evacuation), utilizes an objective function related to humanitarian relief. There are some errors in the YK model, so it is corrected and used to solve a simple example. The corrected model is denoted as YK? model. The second part of this chapter addresses a new model. The YK? model is extended to consider the use of available vehicles for the transfer of relief workers from supply nodes to demand nodes. In post{disaster situation, volunteers and workers are supposed to help people in evacuation and wounded treatment. But the problem with this is that workers come to the regions of where the humanitarian agencies are placed and they request transfer to demand areas. This leads us to extend the YK? model to adopt workforce transfer as a new logistic operation that can improve the whole model. This chapter is organized as follows: Section 3.2 describes the problem solved by YK model, Section 3.2.1 presents the mathematical formulation, Section 3.2.2 provides some corrections to the YK? model, Section 3.2.3 shows a numeric example of the YK? model. Section 3.3 includes the description, formulation, and a numeric example of the YK?+WT model. Section 3.4 summarizes the chapter. 25 3.2 The Yi and Kumar Model (YK)-Problem Description Yi and Kumar (2007) developed a multi-operation logistics model for post-disaster sit- uations. It aims to distribute commodities to a ected areas and evacuate wounded persons to medical centers. In such situations, disaster areas are divided into three main categories: supply nodes, demand nodes, and hospital nodes with the distance of the arcs (routes) be- tween nodes being prede ned. Vehicles are classi ed into many types based on capacity but they are assumed to have equal speed. They pick up supplies from the supply nodes and deliver them to the demand nodes. They can then pick up wounded from demand nodes and transfer them to the hospitals. Demand is classi ed into many types and prioritized based on its importance where the more important commodities have higher priority. In the same manner, wounded are classi ed into many categories and prioritized based on the level of injury. Due to the limitation of resources in a post{disaster situation, vehicles might not be able to deliver the overall demand for each demand node or to pick up all wounded from a node when it is visited. The di erence between the requested and the delivered demand for each node at each time period is called deviation or unsatis ed demand, and the di erence between the total wounded needing evacuation and the wounded still awaiting transfer is called deviation wounded. Accordingly, this model develops a relevant objective function to minimize the summations of these deviation variables. The model outputs for each time period are the amount of commodities of each type which are transfered on each arc, number of wounded from each category traveling on each arc, number of unsatis ed demand of each type at each demand node, number of unserved wounded (deviations) from each category, number of vehicles from each types transfer each arc at each time, and the total number of wounded treated at each hospital node. Many data sets for this model were exactly solved by the authors using CPLEX. These problems were also solved using a two-phase approach. Ant colony optimization (ACO) is 26 applied in the rst phase to determine distribution quantities, while the number of vehicles required to deliver goods between pairs of nodes is determined in the second phase. 3.2.1 Notations and Formulation The YK model employs the following sets and parameters: T: Set of discrete time periods comprising the planning horizon, T= f1, 2, . . . , jTjg. H: Set of severity categories for wounded people, H =f1(heavy);2 (moderate);3 (light);:::;jHjg. V: Set of vehicle types, where vehicles are classi ed based on capacity. A: Set of commodity types, A =f1;2;3;:::;jAjg. CD: Set of demand nodes. CS: Set of supply nodes. CH: Set of available hospitals. C: Set of all nodes in the network, C = CD[CS[CH. top: Number of discrete time intervals required to traverse arc (o;p). This parameter is not vehicle-speci c. dHhot: Number of wounded people of category h2H at node o2CD at time t2T. dAaot: Amount of commodity a2A demanded at node o2CD at time t2T. supaot: Amount of commodity a2A that can be supplied at node o2CS at time t2T. avovt: Number of vehicles of type v2V assigned to node o at time t2T. srvho: Service rate of node o2CH for wounded category h2H. This represents the maximum number of wounded category h2H can be treated at hospital node o. wca: Unit weight of one unit of commodity a2A. wwh: Average weight of one wounded person of category h2H. capv: Capacity of vehicles of type v2V. PCa: Priority of commodity type a2A. 27 PWh: Priority of wounded category h2H Kospt: Binary parameter such that Kospt = 1 if node p 2 C is reachable from node o2C at time t2T, zero otherwise. The decision variables are given by: Zaopvt: Quantity of commodity a2A traversing arc (o;p) at time t2T by vehicle type v2V. devCaot: Amount of unsatis ed demand of commodity a2A at node o2CD at time t2T. Xhopvt: Number of wounded people of category h 2 H traversing arc (o;p) at time t2T by vehicle type v2V. devWht: Number of unserved wounded people of category h2H at time t2T. Yopvt: Number of vehicles of type v2V traversing arc (o;p) at time t2T. SPhot: Number of wounded category h2H served at node o2CH at time t2T. The YK model of Yi and Kumar (2007) is given as follows. Minimize X a2A X o2CD X t2T PCa devCaot + X h2H X t2T PWh devWht (3.1) subject to X s2Ts t dAaos X p2C X v2V X s2Ts t [KpsotZapovs Zaopvs] = devCaot 8 a2A; o2CD; t2T (3.2) X p2C X v2V X s2Ts t [Zaopvs KpsotZapovs] X s2Ts t supaos 8 a2A;o2CS;t2T (3.3) Yopvt M X s2Ts t Kotps 8o2C;p2C;v2V;t2T (3.4) Yopvtcapv X a2A wcaZaopvt + X h2H wwh Xhopvt 8 o2C;p2C;t2T (3.5) 28 X s2Ts t X p2C [Yopvs YpovsKpovs] X s2Ts t avovs 8 o2C;v2V;t2T (3.6) X v2V X s2Ts t X p2C [Xhopvs KpsotXhpovs] X s2Ts t dwhos 8 h2H;o2CD;t2T (3.7) X v2V X s2Ts t X p2C [KpsotXhpovs Xhopvs] X s2Ts t SPhos 8 h2H;o2CnCD;t2T (3.8) X s2Ts t X o2C [dwhos SPhos] = devWht 8 h2H;t2T (3.9) 0 all variables <1; SPhot srvho 8h2H;o2CH;t2T (3.10) In this model, the objective is to minimize the total unsatis ed commodity demands (weighted by the priority of each type at all demand nodes, across all time periods) plus the number of unserved wounded people (weighted by their priority) across all time periods. Constraints (3.2) balance the ow and de ne the unsatis ed demand for each demand node. In other words, the total quantity delivered from node o minus the quantity received by node o in previous periods plus the unsatis ed demand at that node in the current period should equal the total demand for all previous periods. Similarly, constraints (3.3) balance the ow through supply nodes. Constraints (3.4) restrict the itinerary of each vehicle type to existing arcs, while (3.5) restrict the transportation quantities by the capacity of vehicles traversing the arc. Constraints (3.6) balance the vehicle ows at each node and restrict the number of vehicles introduced to the network by their cumulative availability over time. Constraints (3.7) and (3.8) govern the ow of wounded people, whereas constraints (3.9) de ne the unserved wounded people. Finally, constraints (3.10) de ne the variable bounds. Unfortunately, as described in the next section, the YK model contains errors that limit its usefulness. 29 3.2.2 A Corrected Formulation The YK? model represents a corrected formulation of the model proposed by Yi and Kumar (2007). The rst issue associated with the YK model is encountered in constraints (3.2) and (3.3). They were designed to restrict the quantity delivered from each node by its supply capacity and input. Using only these constraints could result in demand nodes operating as supply nodes with unrealistic quantities being admitted. For example, a demand node could supply 100 units and receive 80 units with both constraints (3.2) and (3.3) still satis ed. To correct this, the following constraint, (3.11), is added to the model: X v2V X p2C [Zaopvt Zapovt] supaot 8a2A;o2C;t2T (3.11) Similarly, constraints (3.6) allow infeasible vehicle ows at a given node. For example, suppose that only 6 vehicles are available in the system. As written, these constraints would allow the release of 10 vehicles and the receipt of 5. The net di erence of 5 is less than the number of vehicles in the system, but the 10 vehicles released exceeds the system vehicle availability. To solve this issue, constraints (3.12), below, are added to restrict the total number of vehicles that are moving in the system at any time by the actual number of available vehicles in the system. X o2C X p2C Yopvt X s2Ts t X o2C avovs 8v2V;t2T (3.12) Constraints (3.5) do not properly de ne the v index, an omission likely due to a typo- graphical error in the YK model. These constraints are easily modi ed as follows, where v2V is incorporated into the \for{all (8)" sets: Yopvtcapv X a2A wwa Zaopvt + X h2H wwh Xhopvt 8o2C;p2C;v2V;t2T (3.13) 30 Finally, constraints (3.8) and (3.9) utilize variable SPhot, which is de ned for hospital nodes only. These constraints are modi ed by considering node o2CH, rather than o2C or o2fCnCDg. These constraints are rewritten as: X v2V X s2Ts t X p2C [KpsotXhpovs Xhopvs] tX s=0 SPhos 8h2H;o2CH;t2T (3.14) X s2Ts t X o2CH [devWhos SPhos] = devWht 8h2H;t2T (3.15) The corrected model, YK?, may be represented as: Min (3:1) s.t. (3:2) (3:4);(3:6);(3:7);(3:11) (3:15): 3.2.3 An Example A small example demonstrates the validity of model YK?. This example includes three demand nodes, one supply node, one hospital node, six time periods, and two vehicle types. Two vehicles from each type are available, such that the rst (second) vehicle of Type 1 is added at the beginning of time period 1 (2), and the rst (second) vehicle of Type 2 is added at the beginning of time period 3 (4). Type 1 vehicles have a capacity of 800 lb and Type 2 vehicles have a capacity of 600 lb. This small example considers only one commodity type with a unit weight of 1.5 lb, and one category of wounded victims with an assumed weight of 200 lb each. Unit travel times between any two nodes are assumed for the sake of simplicity. Periodic supply and demand quantities for each node are shown in Table 3.1, while Table 3.2 contains the number of wounded persons waiting at each demand node over time. 31 Table 3.1: Commodity supply and demand over time. Node Type t = 1 t = 2 t = 3 t = 4 t = 5 t = 6 1 Supply 360 460 360 200 240 200 2 Demand 0 260 200 160 210 0 3 Demand 0 190 140 180 192 100 4 Demand 90 160 186 100 160 80 5 Hospital { { { { { { Table 3.2: Quantity of evacuation requests over time. Node Type t = 1 t = 2 t = 3 t = 4 t = 5 t = 6 2 Demand 2 3 1 2 1 0 3 Demand 7 3 1 2 0 0 4 Demand 6 2 1 2 2 0 For this small-scale problem, an optimal solution may be obtained directly via CPLEX. This solution, as represented graphically in Figure 3.1, provides the quantities of commodities and wounded persons transported between nodes. A summary of unsatis ed commodity demand and unserved wounded persons is contained in Table 3.3. Table 3.3: Summary of unsatis ed commodity demand and unserved wounded over time. Node Type t = 1 t = 2 t = 3 t = 4 t = 5 t = 6 2 Demand 0 0 0 0 0 0 3 Demand 0 0 140 140 192 0 4 Demand 0 160 26 100 130 0 Nodes 2, 3, and 4 (Total) Wounded 15 8 6 0 1 0 32 Figure 3.1: Example solution using the YK? model. 3.3 Incorporating Workforce Transfer (YK?+WT) The YK? model is extended to consider the use of available vehicles for the transfer of relief workers from supply nodes to demand nodes to help in wounded treatment and evacuation. These workers, while vital to relief e orts, can consume valuable vehicle space and impose additional constraints on the system. It is assumed that workers may be classi ed according to their skills (e.g., doctors or nurses) with many assumptions such as a known number of each category of relief worker at any node in the network at any speci c time, a periodic demand for particular worker skills at any node, and a priority for successfully delivering workers of a particular type. Beside the same assumptions, inputs, and outputs of the YK? model, the YK?+WT model has the number of workers available at supply nodes and the number of workers re- quested at demand nodes as inputs, and the number of workers from each category transfered at each arcs by each type of vehicles as output. 33 3.3.1 Notation and Formulation The following additional parameters are required by this new model which we denote as YK?+WT. W: Set of worker categories, W =f1 (nurses);2 (doctors);:::;jWjg. SRwot: Number of workers of category w2W that are available at node o2CS at time t2T. dwot: Number of workers of category w2W that are needed at node o2CD at time t2T. wrw: Average weight of a worker in category w2W. PRw: Priority of workers in category w2W. Two new decision variables are also required. The rst, Wwopvt, represents the number of workers of category w 2W traversing arc (o;p) at time t2T by vehicle type v 2V. Second, devRwot denotes the number of workers of category w 2 W are requested by all demand nodes at time t2T, but they are not delivered. The objective function of the YK?+WT model incorporates a third term not found in the YK and YK? models. This term penalizes the number of relief workers waiting for transfer over time: Minimize X a2A X o2CD X t2T PCa devCaot + X h2H X t2T PWh devWht + X w2W X o2C X t2T PRw devRwot: (3.16) New constraints related to workforce transfer are as follows: Yopvtcapv X a2A wcaZaopvt + X h2H wwhXhopvt + X w2W wrwWwopvt 8 o;p2C;v2V;t2T (3.17) 34 X s2Ts t SRwot + X v2V X s2Ts t X p2C [Wwpovs KosptWwopvs] = devwot 8 w;o2CS;t2T (3.18) X s2Ts t dwos X s2Ts t SRwot X v2V X s2Ts t X p2C [Wwpovs KosptWwopvs] = devwot 8 w;o2CD;t2T (3.19) X v2V X p2C [Wwopvt Wwpovt] SRwot 8w2W; o2CS; t2T (3.20) Constraints (3.17) incorporate worker weights within vehicle capacity restrictions. As in the YK? model, constraints (3.18) - (3.20) balance the ow of workers, de ne the deviation variables, and restrict the number of workers that can be moved between nodes. The YK?+WT model may be represented as corrected model while YK? may be repre- sented as: Minimize (3:16) s.t. (3:2) (3:4);(3:6);(3:7);(3:11) (3:15); (3:17) (3:20): 3.3.2 An Example A small example of the YK?+WT model is presented to demonstrate the di erences between the solution to the YK?+WT model and YK? model (where work{force transfer is ignored). The data for this problem are taken from the example of Section 3.2.3, with the addition of workforce parameters, as shown in Table 3.4. This table describes the number of available workers at supply nodes and the number of workers needed at demand nodes. It is assumed that the average weight of workers and wounded people are the same, such that wrw = 200. 35 Table 3.4: Worker demands and availability at each node over time. Node Type t = 1 t = 2 t = 3 t = 4 t = 5 t = 6 1 Available 6 6 4 5 4 0 2 Needed 3 4 1 2 1 0 3 Needed 2 2 2 0 0 1 4 Needed 5 1 0 2 1 0 A graphical representation of the solution to this example is depicted in Figure 3.2, and quantities of unsatis ed demand, unserved wounded, and available workers awaiting transfer are summarized in Table 3.5. Figure 3.2: Example solution from the YK?+WT model. Table 3.5: Summary of unsatis ed commodity demand, unserved wounded, and non{ delivered workers over time. Node Type t = 1 t = 2 t = 3 t = 4 t = 5 t = 6 2 Demand 0 0 0 27 130 0 3 Demand 0 190 0 180 192 0 4 Demand 0 160 186 34 0 0 All nodes Wounded 15 8 6 5 0 0 All nodes Workers 7 5 0 0 0 1 36 In the YK? solution, the total commodities delivered is 1,520 and the number of wounded evacuated is 13. Whereas, in the YK?+WT solution, less commodities are delivered and fewer wounded are evacuated (the total commodities delivered is 1,309 and the number of wounded evacuated is 9). This is because the new logistic operation (work{force transfer) is added to the YK?+WT model and 13 workers are transfered consuming space in vehicles. Accordingly, the bene t of the YK?+WT model is to utilize the available vehicles to perform more logistic operations as requested realistically by the humanitarian agencies in post disaster relief operations. It can be also noted that the utilization of the vehicles in YK?+WT is better than in YK?, as the total mass picked by vehicles in the YK? solution is 4,880 lb and in YK?+WT solution is 6,163 lb. This happens because vehicles in YK?+WT have more options for picking up at supply nodes. 3.4 Summary To start this research, a good baseline model was studied in this chapter. The model from Yi and Kumar (2007) is selected to be our starting point. For better understanding, the mathematical model from this study is coded in CPLEX to solve a small example, but some errors are found which limit its use. Because of this, some corrections are made to the formulation which represents the rst contribution in this research. Unfortunately, solutions obtained by the corrected model (YK?) do not provide actual vehicle routes. They provide the demand quantities and wounded numbers traveled by each type of vehicles as shown in Figure 3.1; such solutions can not be applied directly. Due to this drawback, an additional optimization procedure is required to obtain vehicle assignments to deliver the quantities of goods or people between nodes. This type of post-processing may result in ine cient vehicle routes or the use of excess vehicles which could be avoided if the model were to incorporate individual vehicle assignments. Such an enhancement is 37 described in Chapter 4; however, the YK? model is rst extended to consider the transfer of relief workers between nodes. The new model is developed to incorporate the work-force transfer in YK? model in the same manner of wounded and commodities transfer, i.e. this model provides the number of workers from each category transfered at each arc without providing insight into the actual vehicles route. This shortcoming is addressed in the next chapter. It is interesting to note the di erences between the solutions obtained by the YK? and YK?+WT models. First, the ow quantities of commodities and wounded persons di er, as shown in Figures 3.1 and 3.2. Not surprisingly, the numbers of unserved wounded and unsatis ed demand are greater in the YK?+WT model than in the YK? model. This reduction in service re ects the more realistic nature of the YK?+WT model where the work{force transfer is considered. The next chapter provides a new model to incorporate work{force transfer and consider individual vehicle routes. 38 Chapter 4 Humanitarian Logistics Vehicle Routing Problem (HLVRP) 4.1 Introduction In this chapter, the fourth model which represents the rst main contribution of this research is considered. This model, the humanitarian logistics vehicle routing problem (HLVRP), is an integrated model for humanitarian relief logistics that o ers several dis- tinct advantages over the baseline model of Yi and Kumar (2007), denoted as YK. First, the new model incorporates three logistic operations simultaneously: demand distribution, evacuation of wounded, and workforce transfer. To the best of our knowledge, no other humanitarian logistics model has considered more than two operations. For example, in the models of Yi and Kumar (2007) and Yi and Ozdamar (2007), demand distribution and wounded evacuation, but not workforce transfer, are included. Second, the HLVRP model provides valid and complete vehicle routes. This is facilitated by the inclusion of a new binary decision variable, xvijt, which determines if a particular vehicle, v, arrives at node j at time t after traversing arc (i;j). Thus, solutions of the HLVRP model indicate the exact sequence of nodes to be visited by each vehicle at particular times. By contrast, while the YK model determines the quantities of commodities and wounded traversing each arc, valid vehicle routes to transport these entities are not modeled. This increased granularity of solution information provided by the HLVRP model, as well as detailed vehicle speed characteristics, result in a more practical model. For example, solutions from the HLVRP may indicate exactly which vehicles should be operated to deliver goods, pickup wounded, and transport workers. Conversely, the models of Yi and Kumar (2007) and Yi and Ozdamar (2007) only indicate that a certain number of goods or wounded should be transferred between two nodes by some nondescript vehicle of a particular type. 39 The nal advantage of the proposed HLVRP model is the fact that it considers hetero- geneous vehicles, such that each vehicle may have a unique capacity, average travel speed, and capabilities of traveling along certain roadways. The inclusion of this data provides a more realistic representation of the problem, where many of the vehicles employed may be donated from several sources. Besides the above advantages, this model considers many VRP variants and humani- tarian relief features and activities. While many of the individual features of the proposed research e ort have been considered in separate existing studies, this model aims to provide a comprehensive uni ed model that incorporates multiple critical components of humanitarian relief. These variants and features are explained in the next section. 4.2 Problem Description The problem to be solved in this chapter deals with a logistic system in a post{disaster network requiring coordination of commodity distribution from main distribution centers to areas a ected by a disaster, evacuation of wounded people from a ected areas to the available emergency centers, and transfer of workers from distribution centers to a ected areas to help in medication, evacuation, and repairing the damaged infrastructures. Each separate a ected area represents a demand node, where each demand node is characterized by a time based demand for di erent commodities, such as bottled water, boxed food, medications, and clothes. Commodities have di erent priority values based on their importance. Besides the demand requested at each demand node, there are a number of wounded persons with di ering levels of injuries awaiting transfer to emergency centers or hospitals. To di erentiate among the di erent levels of injury (category), each is given a value of priority such that more severe levels are given a higher value. Because, in the demand nodes, disasters cause di erent levels of destruction and the number of a ected people changes over time, di erent types of workers are needed at each demand node. Accordingly, di erent numbers of workers at a given time are requested at each demand node from di erent professions, such as doctors 40 and nurses who are supposed to help in medication of wounded and electrical technicians who help in repairing power lines. Supplies and workers are picked up from the supply nodes to ful ll the requests that sent from the demand nodes. Time{based supply for each type of commodity and worker are available in the distribution centers which could be the available warehouses in the a ected areas, supply units constructed in pre{disaster planning, non{permanent warehouses built immediately after a disaster, and shelters and tents donated by humanitarian agencies. Despite the kind of supply places, each one is called a supply node. The last type of node in a post{disaster network is the hospitals and emergency centers. These nodes could be the already available hospitals in the area of the disaster or temporary units constructed by humanitarian agencies after the disaster. Heterogeneous vehicles are utilized to perform the demand distribution, worker transfer, and wounded evacuation. It is assumed that each vehicle has its own capacity and speed, starts from a depot (one of the supply nodes) and returns to the same depot at the end of the planning period to start from there for the next plan. The logistic operations are performed as follows. Each vehicle, based on its capacity and the availability of supplies and workers, retrieves an amount of commodities and workers from its depot. The vehicle then starts visiting demand nodes to distribute commodities and deliver workers. If su cient free space is available, a vehicle may pick up wounded people. After some visits, it has many options such as going to a hospital to deliver the wounded and then to another depot to reload, returning directly to another depot if it has no wounded, or returning to its origin depot. In some cases with special conditions, vehicles perform the logistic plans di erently. For example, if some depots have a high number of vehicles compared to others, vehicles from these depots may go directly to the depots with low number of vehicles to pick up supplies and/or workers and then start distribution. In another example, if the available vehicle capacities exceed the available supplies, or if the priority of wounded evacuation is 41 much higher than the demand distribution and work{force transfer, some vehicles may travel empty to demand nodes to evacuate wounded. Due to the limitation of supplies and transporters in a post{disaster situation, the goal in this problem is to deliver as many commodities as possible, transfer as many workers as possible, and evacuate as many wounded as possible. Thus, these minimizing the unsatis ed demand, non{transfered workers, and non-evacuated wounded. 4.3 An Overview of the HLVRP Model From the previous description, a mathematical model called HLVRP model, a mixed integer program, is used to model a dynamic routing system. The HLVRP includes many input sets. First, the time horizon set T, which is discretized into a set of integer periods with equal length, where the duration of each depends on the situation and could be any time, (e.g., 5 minutes, 30 minutes, 1 hours, 2 hours). This time horizon makes other parameters, such as demands needed, available supplies, number of workers at each depot, and number of wounded as time based parameters. Second, the set of wounded evacuee categories E includes di erent qualitative values such as heavy, moderate, and light injuries. For fairness, the priority of these categories is di erent, where more severe injuries have higher priority values. Third, the set of vehicles, V, includes all vehicles in the system with di erent speeds and capacities. Fourth, the set of commodities, C, contains all commodity types, such as bottled water, boxed food, medications, and clothes. Fifth, the set of workers, W, de nes di erent professions of the work-force and volunteers, such as doctors, nurses, and rst responders. Sixth, the set of nodes N contains all nodes in the networks. This set includes three sub{sets: supply nodes set S, demand nodes set D, and hospital nodes set H. The given parameters are: starting depot for each vehicle, time needed to pass between nodes by each vehicle, time based demand at each demand node from each type of commodity, time based number of wounded for each level of injury at each demand node, time based number of workers from each category (profession) requested by each demand node, time 42 based supply from di erent commodities and available workers from each category at each supply node, mass capacity for each vehicle, unit mass for each demand type, unit mass for each worker and wounded, priorities for each demand type, priorities for each work-force category, and priority for each wounded level. After solving the model, each vehicle will be given a route and the following outputs (decisions) given for the users. For each vehicle and time period, the number of commodities of each type to be picked up from each supply node, the number of commodities of each type to be delivered to each demand node, the number of wounded from each level to be picked up from each demand node, the number of wounded from each level to be delivered to each hospital node, the number of workers from each category to be picked up from each supply node, and the number of workers from each category to be delivered to each demand node will be determined. Accordingly, unsatis ed demand, non{evacuated wounded, and undelivered workers can be determined The HLVRP model considers many realistic features. First, the existence of multiple depots, where each vehicle starts from a speci c depot. Second, split deliveries are allowed, such that each demand node can be supplied by di erent vehicles. Third, the HLVRP consid- ers multiple commodity types, evacuee categories, and work{force professions. Fourth, the HLVRP provides a detailed route for each vehicle including the nodes that must be visited, the time to visit each node, demand quantities to be picked up and delivered, wounded to be evacuated, and workers to be transfered. Finally, the proposed HLVRP model considers heterogeneous vehicles, such that each vehicle may have a unique capacity, average travel speed, and capabilities of traveling along certain roadways. Table 4.1 contrasts the previous studies with this proposed model according to several key features. Some assumptions are made in the HLVRP model for practical reasons. First, demand nodes can not operate as transshipment nodes (i.e., excess supply can not be temporarily stored at a demand node). This restriction is considered for the practical reason that it is likely that any excess goods left at a demand node may be consumed (or even stolen) during 43 the chaos of a humanitarian crisis. However, this assumption may be relaxed by modifying some constraints. Second, workers do not need to return to their starting locations. Instead, it is assumed that they will remain stranded at their last destinations and begin from there on the following day. In the event that it is necessary for each worker to return \home", a constraint may be added to the model, as discussed later. Third, because each vehicle starts from its depot and can not revisit it, a vehicle can pick up commodities and workers from its depot only at the rst time period, but vehicles can pick up commodities and workers from other supply nodes. Fourth, each vehicle should return back to its depot where a new plan could be given for the next planning horizon. To avoid any infeasible activity, many conditions must be satis ed through the model?s constraints. First, a vehicle can not reach a node (i) before nishing the travel time on the arc between its current node and node (i). Second, any vehicle that enters a node should also leave that node which balances the vehicle ows. Third, the total picked up commodities and workers from any supply node should be less than or equal to the available quantities. Fourth, the total delivered commodities and workers to any demand node at any time period should be less than or equal to the requested numbers. Fifth, vehicles must visit a node to be able to pick up or deliver commodities, workers, or wounded. Table 4.1: A comparison between the HLVRP model and the existing literature. Multi Split Di erent Di .Cap MultiVehiclesMulti-Time Work-forceReference Commodity Delivery Speed Vehicle Depot Routing slots EvacuationTransfer Ozdamaretal.(2004) X X X XYiandKumar(2007) X X X X X X LiuandZhao(2007) X X XYiandOzdamar(2007) X X X X X X Campbelletal.(2008)YuanandWang(2009) Vitorianoetal.(2010) X X X XWidenerandHorner(2011) X X Linetal.(2011) XFeietal.(2011) X HLVRP X X X X X X X X X 44 4.4 Notations and Formulation 4.4.1 Notations In this section, the notations employed by the model are de ned. This model requires the de nitions of numerous parameters and decision variables, as described below. T: Set of discrete time periods in the planning horizon, T =f1;2;3;:::jTjg. E: Set of di erent injury severity categories of evacuees (wounded people). For exam- ple, E= f1: Heavy, 2: Moderate, 3: Light, :::g. W: Set of worker categories. For example, W =f1 (doctors); 2 (nurses); 3;:::;jWjg. V: Set of individual vehicles, V =f1;2;3;:::jVjg. C: Set of commodity types C =f1;2;3;:::jCjg. D: Set of demand nodes. S: Set of supply nodes. H: Set of available hospitals. N: Set of all nodes in the network, N =fD[S[Hg. iv: Initial depot of vehicle v2V, where each depot is a supply node, i.e. all iv2S. vij: Integer time periods needed by vehicle v2V to travel from node i2N to node j2N. dEeit: Number of wounded persons, of category e2E, requesting evacuation from node i2D at time t2T. dWwit: Number of workers of category w2W requested by node i2D at time t2T. dCcit: Amount of commodity type c2C demanded at node i2D by time t2T. 45 sCcit: Amount of commodity type c2C that can be supplied from node i2S at time t2T. mCc : Unit mass of commodity c2C. mEe : Average mass of an evacuee of category e2E. sWwit: Number of workers of category w2W that are available at node i2S at time t2T. mWw : Average mass of one worker of category w2W. pWw : Priority of workers in category w2W. mv: Mass capacity of vehicle v2V. pCc : Priority of commodity type c2C. pEe : Priority of wounded evacuees category e2E. Numerous decision variable types are required to provide the more detailed solutions a orded by the HLVRP model. There are four main variable categories: pick{ups, deliveries, deviations, and binary routing variables. The pick{up variables are used to de ne the picked up quantities of supplies as in zPcivt, number of workers picked up from the supply nodes as in wPwivt, and the number of wounded evacuated from the demand nodes as in ePeivt. Similarly, the delivery variables de ne the demand deliveries as in zDcivt, workers delivered to demand nodes as in wDwivt, and the number of wounded delivered to each hospital as in eDeivt. The deviation variables depend on the values of picked up and delivery variables. There are three groups of the deviation variables. First, the demand deviation variables vCcit are de ned, at each demand node and time, as the demand requested minus the total value of demand delivery variables to that node by that time. Second, worker{force deviation variables vWwit are de ned, at each demand node and time, as the number of workers requested by that node minus the total value of work{force delivery variables to that node by the same 46 time. Third, the evacuation deviation variables vEeit are de ned, at each demand node and time, as the number of wounded request evacuation by that node minus the total value of wounded picked up variables from that node by the same time. Finally, binary variables de ne the vehicle routes and relate to other variables using big{M constraints, such that the picked up and delivery variables for each vehicle can take values greater than zero only if a particular binary variable is equal to one. This is discussed more clearly after the model is formulated. All of these variables are listed below: zDcivt: Quantity of commodity type c2C delivered to node i2D at time t2T by vehicle v2V, where zDcivt2 0;1;:::;min dCcit; mvmC c zPcivt: Quantity of commodity type c2C picked up from node i2S at time t2T by vehicle v2V, where zPcivt2 8 >< >:0;1;:::;min 8 >< >: X s2Ts t sCcis; mvmC c 9 >= >; 9 >= >; vCcit: Amount of unsatis ed demand of commodity type c2C at node i2D at time t2T, where vCcit2 0;1;:::;dCcit vEeit: Number of evacuees of category e2E that requested transportation from node i2D at time t2T but were not transfered, where vEeit2 0;1;:::;dEeit vWwit: Number of workers of category w2W requested by node i2D at time t2T but were not satis ed, where vWwit2 0;1;:::;dWwit eDeivt: Number of evacuees of category e2E transfered (delivered) to node i2H at time t2T by vehicle v2V, where eDeivt2 0;1;:::; mvmE e ePeivt: Number of evacuees of category e2E transfered (picked up) from node i2D at time t2T by vehicle v2V, where ePeivt2 0;1;:::;min dEeit; mvmE e wDwivt: Number of workers of category w2W (e.g., nurses or doctors) transfered (deliv- ered) to nodei2D at timet2T by vehiclev2V, wherewDwivt2 0;1;:::;min dWwit; mvmW w 47 wPwivt: Number of workers of category w2W transfered (picked up) from node i2S at time t2T by vehicle v2V, where wPwivt2 0;1;:::;min sWwit; mvmW w xvijt: A binary variable, such that xvijt = 1 if vehicle v2V arrives at node j 2N, coming from node i2N;i6= j, at time t2T; xvijt = 0 otherwise. 4.4.2 The HLVRP Formulation In this section, a mathematical formulation of the HLVRP is presented, as follows Min X c2C X i2D X t2T pCc vCcit + X e2E X i2D X t2T pEe vEeit + X w2W X i2D X t2T pWw vWwit (4.1) X i2N X j2N j6=i xvijt 1 8v2V; t2T (4.2) X j2N j6=iv X t2T xvivjt = 1 8v2V (4.3) X j2N j6=iv X t2T xvjivt = 1 8v2V (4.4) X i2Ni6=j X t2T xvijt 1 8v2V; j2N (4.5) X i2N X t2T t xvijt X k2Nniv X t2T (t jkv)xvjkt 8v2V; j2N (4.6) X i2Nniv i6=j X t2T xvijt = X i2Nniv X t2T xvijt 8v2V;j2N (4.7) X i2N X j2N i6=j X t2T ijv xvijt jTj 8v2V (4.8) X s2Ts t vCcis = X s2Ts t dCcis X v2V X s2Ts t zDcivs 8c2C; i2D; t2T (4.9) X s2Ts t vEeis = X s2Ts t dEeis X v2V X s2Ts t eDeivs 8e2E;i2D; t2T (4.10) 48 X s2Ts t vWwis = X s2Ts t dWwis X v2V X s2Ts t wDwivs 8w2W; i2D; t2T (4.11) X s2Ts t X i2S zPcivs X s2Ts t X j2D zDcjvs 8v2V; c2C; t2T (4.12) X s2Ts t X i2D ePeivs X s2Ts t X j2E eDejvs 8v2V; e2E; t2T (4.13) X s2Ts t X i2S wPwivs X s2Ts t X j2D wDwjvs 8v2V; w2W; t2T (4.14) X v2V zPcivt X s2Ts t sCcis X s2Ts t 1 X v2V zPcivt 8c2C; i2S;t2T (4.15) X v2V ePeivt dEeit 8e2E; i2D; t2T (4.16) X v2V wPwivt X s2Ts t sWwis X s2Ts t 1 X v2V wPwivs 8w2W; i2S; t2T (4.17) mv X a X s2Ts t X i2S mCc zPcivs + X e2E X s2Ts t X i2D mEe ePeivs + X winW X s2Ts t X i2S mWw wPwivs X c2C X s2Ts t X i2D mCc zDcivt X e2E X s2Ts t X i2H mEe eDeivs X w2W X s2Ts t X i2D mWw wDwivs 8v2V; t2T (4.18) X i2D X t2T X v2V ePeivt = X i2H X t2T X v2V eDeivt 8e2E (4.19) X c2C zDcivt M4:20 X j2N xvjit 8i2D; v2V; t2T (4.20) X c2C zPcivt M4:21 X j2N xvjit 8c2C;i2Sniv;v2V; t2T (4.21) zPcivvt = 0 8c2C;v2V; t2Tnt = 1 (4.22) X e2E eDeivt M4:23 X j2N xvjit 8e2E; i2H; v2V; t2T (4.23) X e2E ePeivt M4:24 X j2N xvjit 8e2E; i2D; v2V; t2T (4.24) 49 X w2W wDwivt M4:25 X j2N xvjit 8w2W; i2D; v2V; t2T (4.25) X w2W wPwivt M4:26 X j2N xvjit 8w2W;i2Sniv; v2V; t2T (4.26) wPcivvt = 0 8w2W; v2V; t2Tnt = 1 (4.27) The objective function (4.1), seeks to minimize the quantities of unsatis ed demand, unserved wounded, and non-transfered workers. Each of these quantities are scaled by their respective priority values. There are 26 constraint sets: Constraints (4.2) ensure that each vehicle may serve only one node at a given time, whereas Constraints (4.3) ensure that each vehicle starts from its initial depot. To ensure that each vehicle will return to its initial depot after nishing its route and it can not leave the depot again, Constraints (4.4) are used. Constraints (4.5) prevent each vehicle from visiting any node more than once. To maintain feasibility of routes, Constraints (4.6) are used ensure that each vehicle can not reach any node before nishing the arc between the previous and the current nodes, Constraints (4.7) are used to balance ow for each demand node, so each vehicle should enter and leave each node the same number of times. Constraints (4.8) restrict each vehicle?s route by the total time available for that vehicle. Constraints (4.9), (4.10), and (4.11) de ne the deviation variables, such that Constraints (4.9) address unsatis ed demand, Constraints (4.10) address non{evacuated wounded, and Constraints (4.11) consider undelivered workers. To maintain control of quantities in each vehicle, Constraints (4.12) restrict the quantity of commodities that may be delivered to demand nodes by the quantity that are picked up from supply nodes. Similarly, constraints (4.13) and (4.14) restrict the number workers delivered to demand nodes and the number of wounded delivered to hospitals by the number picked up by each vehicle. Constraints (4.15), (4.16), and (4.17) restrict the supply and transfer at each time. Constraints (4.15) ensure that each supply node can provide quantities not exceeding the available supply for each type. Constraints (4.16) limit the number of assisted wounded to 50 be no more than the number waiting at a particular demand node. In the same manner, Constraints (4.17) ensure that the number of workers dispatched from any supply node does not exceed the actual number of available workers. Vehicle capacity limitations are included in constraints (4.18), while constraints (4.19) ensure that wounded persons should be transferred from demand nodes to hospital nodes. Constraints (4.20){(4.27) ensure that all distribution and transfer variables have a value for any node only if a vehicle visits that node; such that Constraints (4.20) ensure that the delivered quantity from a vehicle to a demand node can be greater than zero only if the vehicle visits that node. Constraints (4.21) ensure that the quantity picked up from a supply node by a vehicle can be greater than zero only if the vehicle visits that node. Constraints (4.22) require that each vehicle can pick up commodities from its depot at time zero but not later. Constraints (4.23) ensure that a vehicle can deliver wounded to a hospital only if it visits that hospital. For wounded pick{ups, Constraints (4.24) ensure that a vehicle can retrieve wounded from a demand node only if it visits that node. Constraints (4.25) allow a vehicle to deliver workers to a demand node only if it visits that node. Similarly, Constraints (4.26) allow a vehicle to pick up workers from a supply node if it visits that node. Finally, Constraints (4.27) ensure that each vehicle can pick up workers from its depot only at the rst time period. Because vehicles can leave their depots just once, both Constraints (4.27) and (4.22) are used for the same purpose, which is to allow vehicles to pick up commodities or workers only at the rst time. On of the assumptions discussed before is that workers do not need to return to their starting locations. In the event that it is necessary for each worker to return \home", Constraints 4.28 may be added. X v2V X t2T wPwivt = X v2V X t2T wDwjvt 8i2S: (4.28) 51 The big{M values in constraints (4.20), (4.21), and (4.23){(4.26) may be calculated as follows. The de nitions of these values have an abuse of notation such that the M values should be de ned for each combination of indices, (e.g., Mivt4:20), but for simplicity, it is de ned without indices (e.g., M4:20). M4:20 =min dCcit; mvmC c 8i2D; v2V; t2T M4:21 =min 8 >< >: X s2Ts t sCcis; mvmC c 9 >= >; 8c2C;i2Sniv;v2V; t2T M4:23 =mvmE e e2E; i2H; v2V; t2T M4:24 =min dEeit; mvmE e 8e2E; i2D; v2V; t2T M4:25 =min dWwit; mvmW w 8w2W; i2D; v2V; t2T M4:26 =min sWwit; mvmW w 8w2W;i2Sniv; v2V; t2T By de ning each value separately, the bounds of the linear program (LP) relaxation may be improved, thus (potentially) saving computational e ort. In the next section, an example veri es this model and demonstrates how the solution represents a detailed plan. 4.5 Model Veri cation by Example A small problem is presented to demonstrate the bene ts of the proposed HLVRP formulation and to show how the results are understandable and easy to apply. This example includes 12 time periods (15 minutes each), 3 demand nodes, 2 supply nodes, 1 hospital node, 2 commodity types, 1 wounded category, 1 worker category, and 3 vehicles. Table 4.2 contains the commodity demand data over the planning horizon, while Table 4.3 contains the 52 commodity supply data over the planning horizon. Available and requested numbers of relief workers are summarized in Table 4.4. Similarly, Table 4.5 shows the number of wounded requiring evacuation. Finally, Table 4.6 shows other parameter values which are the starting node for each vehicle (iv), vehicle capacities (mVv ), unit mass of each commodity type (mCc ), wounded and worker average mass (mEe; mWw ), commodity priorities (pCc ), wounded priority (pEe ), and worker priority (pWw ), respectively. Table 4.2: Demand data, dccit Demand Time Node Type 1 2 3 4 5 6 7 8 9 10 11 12 1 1st type 0 0 60 85 96 0 100 0 0 120 0 0 2nd type 0 0 100 100 30 0 110 0 180 0 0 0 3 1st type 0 0 30 100 0 0 195 0 165 66 0 0 2nd type 0 0 100 200 0 100 0 120 0 30 0 0 4 1st type 0 0 0 36 112 0 100 0 120 0 0 0 2nd type 0 0 140 0 112 0 100 200 0 130 0 0 Table 4.3: Supply data, sccit Demand Time Node Type 1 2 3 4 5 6 7 8 9 10 11 12 2 1st type 400 0 0 60 0 100 0 60 0 0 0 0 2nd type 230 0 0 0 300 0 0 0 0 0 0 0 6 1st type 400 0 0 60 0 100 0 60 0 0 0 0 2nd type 566 0 0 220 0 68 0 0 0 0 0 0 Table 4.4: Available and needed workers, sWwit and dWwit Time Node Type 1 2 3 4 5 6 7 8 9 10 11 12 1 Requested 0 1 4 3 5 2 1 4 3 2 2 0 2 Available 6 0 2 0 0 4 0 0 1 0 0 0 3 Requested 0 2 3 1 6 5 5 2 0 2 0 0 4 Requested 0 1 3 3 2 0 2 5 3 2 3 0 6 Available 8 0 0 2 0 0 0 3 0 0 0 0 53 Table 4.5: Wounded awaiting evacuation, dEeit Time Node 1 2 3 4 5 6 7 8 9 10 11 12 1 0 0 4 2 1 1 0 1 1 0 0 0 3 0 6 4 1 8 0 5 0 1 0 0 0 4 0 0 7 0 4 0 4 0 1 0 0 0 Table 4.6: Parameter values Parameter Values Vehicledepotsiv [2, 2, 6] Vehiclecapacities(lb)mVv [1400,1000,1100] Commodity mass(lb)mCc [1.5,2] Wounded andworker massmWw , mEe 200 Commodity prioritiespCc [5, 10] Evacueepriority pEe 160 Worker prioritiespWw 100 4.5.1 Example Results The deviation variable results of this example are shown in Tables 4.7{4.9. These vari- ables are: unsatis ed demand of commodity type 1 (vC1it), unsatis ed demand of commodity type 2 (vC2it), undelivered workers (vWwit), and unserved wounded (vEeit). Route variables xvijt, which are used to construct the route for each vehicle, are shown in Table 4.10. To make the solution of this example easier to understand, it is depicted graphically in Figure 4.1. Table 4.7: Unsatis ed demand (commodity deviation values), vCcit Unsatis ed Time Node Demand 1 2 3 4 5 6 7 8 9 10 11 12 1 1st type 0 0 0 85 96 0 100 0 0 120 0 0 2nd type 0 0 0 100 30 0 110 0 0 0 0 0 3 1st type 0 0 30 7 0 0 195 0 165 66 0 0 2nd type 0 0 50 170 0 100 0 120 0 30 0 0 4 1st type 0 0 0 36 112 0 0 0 120 0 0 0 2nd type 0 0 140 0 112 0 0 0 0 130 0 0 54 Table 4.8: Non{evacuated wounded (wounded deviation values), vEeit Time Node 1 2 3 4 5 6 7 8 9 10 11 12 1 0 0 0 2 1 1 0 1 1 0 0 0 3 0 6 3 0 5 0 5 0 1 0 0 0 4 0 0 7 0 0 0 0 0 1 0 0 0 Table 4.9: Undelivered workers (worker{force deviation values), vWwit Time Node 1 2 3 4 5 6 7 8 9 10 11 12 1 0 1 3 3 5 2 1 4 0 2 2 0 3 0 2 0 1 1 5 5 2 0 2 0 0 4 0 1 3 1 2 0 2 2 3 2 3 0 Table 4.10: Vehicle routes Vehicle Route, times are listed below 1 depot ! 3 ! 4 ! hospital ! depot t=1(8:00) t=5(9:15) t=7(9:45) t=9(10:15) t=12(11:00) 2 depot ! 1 ! 3 ! hospital ! resupply ! 4 ! depot t=1(8:00) t=3(8:45) t=4(9:00) t=5(9:15) t=6(9:30) t=8(10:00) t=12(11:00) 3 depot ! 3 ! 4 ! hospital ! resupply ! 1 ! depot t=1(8:00) t=3(8:45) t=4(9:00) t=5(9:15) t=6(9:30) t=9(10:15) t=12(11:00) 55 (a) Problem Data. (b) Vehicle 1 route with its logistic plan. (c) Vehicle 2 route with its logistic plan. (d) Vehicle 3 route with its logistic plan. Figure 4.1: Detailed logistic plan for all vehicles As indicated, the HLVRP provides a full detailed and realistic logistic plan which is easy to apply. For each vehicle, the plan includes the quantities which should be picked up, where they should be delivered, the number of wounded, and where workers should be transfered at each time. 4.6 Solution Approaches As an extension of the CVRP, it is clear that the HLVRP represents an NP-hard problem. It is particularly challenging because it requires the determination of vehicle routes and delivery quantities that might not meet demand. Additionally, decisions must be made 56 regarding whether to visit a particular hospital, the number of workers to transport, and the number of wounded to evacuate. Although small-scale problems may be solved optimally via CPLEX, larger-scale problems require the use of customized heuristic approaches to obtain high-quality solutions. The proposed heuristic depends on taking advantage of the model?s inherent consider- ation of individual vehicle routes. Thus, the solution approach will be rooted in a valid, realistic, and complete mathematical model. The rst phase will consist of a heuristic vehi- cle route construction procedure. Preliminary testing indicates that, given a set of vehicle routes, the resulting integer programming problem can be solved surprisingly quickly (i.e., in a few seconds) using CPLEX. The CPLEX solution would provide quantities of com- modities, wounded, and workers (again, for a xed set of vehicle assignments). An iterative procedure will be applied to generate di erent vehicle routes at each iteration via changing some parameters. Then di erent local search techniques are used to improve the routes, as discussed later in this section. 4.6.1 Heuristic Description In this subsection, the proposed heuristic is described. The new notations are de ned as follows: Routev is a route for a vehicle v which is constructed from the variables xvijt and is used to facilitate the coding. For example, if a vehicle route is [2, 3, 6, 8, 2], this means the vehicle starts from node 2 and visits 3, 6, and 8, before returning to node 2. The vehicle does not visit any nodes not shown in this array. A function exists to convert between Routev and xvijt. This function is the Binaries-Route and shown in Algorithm 1 in the next point. RouteTv is a row array of the same size as Routev which contains the time to reach each node. Function Binaries-Route in Algorithm 1 shows how Routev and RouteTv are generated from the binary variables. 57 Algorithm 1: Binaries-Route converter 1: Set k = current selected vehicle 2: Set counter = 2 3: Set Routek(1) = ik // starting point is the current vehicle?s depot 4: Set RouteTk(1) = 1 // starting time 5: for all t2T do 6: for all i2N do 7: for all j2Nni do 8: if xkijt = 1 then 9: Routek(counter) = j 10: RouteTk(counter) = t 11: counter = counter + 1 12: Set i;j >jNj Skip loops, impossible to nd other visit at the same time. 13: end if 14: end for 15: end for 16: end for current is a holder used to save the current location for a vehicle. It changes dynami- cally during the process. sortD is a two dimensional array of size jTj jDj which contains the demand nodes sorted in descending order at each time based on their importance value. The element sortD(t;i) represents the ith demand node at time t. For example, if the importance values for 5 demand nodes at time t are [1000, 800, 3000, 2100, 1450], then the tth row from sortD is [3, 4, 5, 1, 2] so the element sortD(t;1) = 3. In other words, node 3 58 is placed in the rst place because it has the highest preference to be visited by the current selected vehicle. sortS is a two dimensional array of size jTj jSj which contains the supply nodes sorted in descending order at each time based on their importance value. The element sortS(t;i) represents the ith supply node at time t. sortH is a two dimensional array of size jTj jHj which contains the hospital nodes sorted in descending order at each time based on their importance value. The element sortH(t;i) represents the ith supply node at time t. AvgD is a scalar quantity which represents the average commodity and worker masses requested by the demand nodes for the whole time horizon. It can be mathematically calculated as AvgD = P c2C P i2D P t2T(d C cit m C c ) + P w2W P i2D P t2T(d W wit m W w ) jTj jDj is a random integer which represents the number of demand nodes that should be visited by a vehicle v before it ends the trip and goes to a hospital or supply node. It is randomly selected from a set of integer values, a set which is created based on the vehicle capacity and node demands. Mathematically, can be represented as follows 2 m v d AvgD + 0:5 2; m v d AvgD + 0:5 + 2 : (4.29) Selecting a high number for , i.e. 8 nodes in the previous example, could result in useless visits such as visiting some nodes while the vehicle is empty. In contrast, visiting a low number of demand nodes could force the vehicle to resupply or go to a hospital while it has some undelivered commodities and workers. d is the percentage of the demand and workers requested expected to be delivered each time the vehicle visits a demand node. Portion of 70% is selected as a value of d because it has been noticed that in many instances, vehicles try to visit demand nodes where 70% of their 59 needs can be supplied. This helps minimize the deviation variables which is the model objective. For example, in a data instance, if AvgD is 600 lb and the capacity of a vehicle is 1600, assuming vehicle supplies 70% of node demands each time it visits a node (d = 0:7), this means vehicle v can supply 1600 / (0.7*600) = 3.8 nodes. In this case, is randomly selected from an interval that has a center value of 3.8 (rounded to the closest integer which is 4) nodes. Based on equation 4.29, the interval equals to [2 nodes, 6 nodes]. The value of is randomly selected from this interval at each time the vehicle v leaves a supply node and begins distribution. tnow is the current time of the selected vehicle which is used to test the feasibility of any visit done by the vehicle. This time is incremented at each visit but not between visits. For example, one of the feasibility conditions is to test if tnow + v;current;i = t, where i is a node that the vehicle tries to visit. At the beginning, tnow = t = 1, if the rst visit to node i can be made at time 4 because v;current;i = 3, tnow is kept at a value of 1 while the value of t incremented to 2, 3, and 4. At time 4, the visit is done and the value of tnow is updated to 4. sup is a counter used to keep track of the number of supply nodes which are visited by a vehicle. It is incremented by 1 each time the vehicle visits a supply node during the heuristic process. dem is a counter used to keep track of the number of demand nodes visited by a vehicle. It is incremented by 1 each time the vehicle visits a demand node during the heuristic process. hos is a counter used to keep track of the number of hospital nodes visited by a vehicle. It is incremented by 1 each time the vehicle visits a hospital. is a number selected randomly from the set [1, 2] selected randomly after a vehicle nishes visiting demand nodes, such that = 1 means that the current vehicle must 60 visit a supply node on the next step while = 2 means the vehicle must visit a hospital next. PTD is a two dimensional array, where the element PTD(t;i) represents the prioritized demand requested, workers needed, and wounded awaiting help at node i2D at time t2T. It can be calculated as PTD(t;i) = X c2C dCcit pCc + X e2E dEeit pEe + X w2W dWwit pWw : (4.30) The whole array appears as follows PTD(t;i) = 2 66 66 66 64 PTD(1;1); PTD(1;2); ::: PTD(1;jDj) PTD(21); PTD(22) ::: PTD(2;jDj) :::; :::; ::: ::: PTD(jTj;1); PTD(jTj;2); ::: PTD(jTj;jDj) 3 77 77 77 75 : PTS is a two dimensional array, where the element PTS(t;i) represents the prioritized available supply and workers at node i2S at time t2T. It can be calculated as PTS(t;i) = tX k=2 (X c2C sCcik pCc + X w2W sWwik pWw ) (4.31) In demand nodes, prioritized demand is calculated at each time by using the demand, wounded, and workers at that time. For supply nodes, because picking up workers and supplies left from previous periods is allowed, prioritized supply is calculated cu- mulatively excluding the rst time period. In the rst time period, vehicles pick up workers and supplies from their depots, so the information about prioritized supply val- ues at that time is not known. This justi es its exclusion from the prioritized supply calculation. The whole array is given by 61 PTS(t;i) = 2 66 66 66 64 PTS(1;1); PTS(1;2); ::: PTS(1;jSj) PTS(2;1); PTS(2;2) ::: PTS(2;jSj) :::; :::; ::: ::: PTS(jTj;1); PTS(jTj;2); ::: PTS(jTj;jSj) 3 77 77 77 75 : IMv is a two dimensional array which contains the importance values, IMv(t;i), of node i2N at each time t2T for vehicle v. This array is calculated for each vehicle at the beginning of the solution approach and is updated each time the vehicle changes its location. Importance is not constant and is a function of the selected vehicle, current location, PTS; and PTD. This array looks like: IMv = 2 66 66 66 64 IMv(1;1); IMv(1;2); ::: IMv(1;jNj) IMv(2;1); IMv(2;2); ::: IMv(2;jNj) :::; :::; ::: ::: IMv(jTj;1); IMv(jTj;2); ::: IMv(jTj;jNj) 3 77 77 77 75 : Z is the incumbent objective value, initialized to be 1. ZB is an array which contains all variables associated with the incumbent objective value such that ZB = 2 66 66 66 66 66 66 66 66 66 66 66 66 66 64 zDcivt 8c2C;i2D;v2V;t2T zPcivt 8c2C;i2S;v2V;t2T vCcit 8c2C;i2D;t2T vWwit 8w2W;i2D;t2T vCcit 8e2E;i2D;t2T eDeivt 8e2E;i2H;v2V;t2T ePeivt 8e2E;i2D;v2V;t2T wDwivt 8w2W;i2D;v2V;t2T wPwivt 8w2W;i2S;v2V;t2T xvijt 8i2N;j2Nni;v2V;t2T 3 77 77 77 77 77 77 77 77 77 77 77 77 77 75 : 62 Xbvijt is a four dimensional array which contains all binary variable values xbvijt 8i2 N; j2fNnig; and t2T associated with the best solution ZB , so, it contains the last row of matrix ZB . Z is the objective function value of the current candidate solution. ZC is an array which contains all variables associated with the current objective func- tion value. It looks similar to ZB but is associated with the current solution. XCvijt: is a sub{array from ZC which contains only the binary variables associated with the current objective function value, XCvijt = xcvijt 8i2N; j2fNnig; t2T. Pv is the performance of a vehicle v2V which equals the total mass of commodities, workers, and wounded picked up by v during the whole logistic plan, as in equation 4.32 Pv = X t2T (X i2S X c2C mCc zPcivt + X i2D X e2E mEeePeivt + X i2S X w2W mWw wPwivt ) (4.32) BPv is the best performance achieved by vehicle v2V. It is initialized to zero for all vehicles. Xbvvijt is a four dimensional array which contains all binary variable values xbvvijt 8i2 N; j 2fNnig; and t 2 T associated with the best performance achieved by each vehicle. The di erence between Xbvvijt and Xbvijt is that Xbvvijt used to save the best binary values for each vehicle individually, (i.e., the best binaries for vehicles might come from di erent solutions and iterations and they only depend on the performance of the vehicle). Conversely, Xbvijt is used to save the best binaries for a complete solutions from a single iteration, depending on the performance of all vehicles together. XIinitialvijt is a four dimensional array which contains all binary variable values xivijt8i2 N; j2fNnig; and t2T. This array is used as a starting solution for the local search 63 and can take di erent values based on the type of local search. Local search with initial solutions are further explained later in this section. ? is a number, ?2 [0;1;2;3], set by the user before the code is run to specify some inputs for the local search where 0 is used when local search is not required, 1 is used for (A) variants of local search, 2 is used for (I) variants of local search, and 3 is used for (B) variants of local search. All of these types are explained later in this section. This approach begins with calculating the prioritized demand for each demand node and the prioritized supply for each supply node. In the case of demand nodes, the prioritized demand is found based on the demand needed, workers requested, and wounded evacuees who need help, as in equation 4.30. For supply nodes, the prioritized supply is determined by cumulative available supply and workers, as in equation 4.31. Next, the set of vehicles is randomly partitioned into two sets, large (V 1) and small (V 2), where the number of vehicles in the larger set is about 70% of the total number. The reason of selecting the 70% for the larger set is discussed later. In the larger set, a vehicle is randomly selected, and the importance for all nodes is calculated depending on node type, the selected vehicle, and its current place which is initially its depot. In the case of hospital nodes, vehicles visit closer hospitals, so importance values of hospitals are independent of the node type and they are mainly dependent on the distance from the current node. The selected vehicle moves to the most bene cial demand node (i.e., the demand node with the highest importance value), given that the node has not yet been visited by the vehicle. After a speci c random number of demand nodes , the vehicle visits the most bene cial (important) supply node or hospital based on the value. If the vehicle decides to visit a hospital, it goes afterwards to a supply node to be replenished, then visits a new value of demand nodes. On the other hand, if it visits a supply node, it goes on to visit a new set of demand nodes. This procedure is repeated until the end of the time horizon. Each time a node is visited, its importance is decreased to avoid being revisited by other vehicles in the same time period unless its importance justi es multiple visits. This procedure is 64 continued until all vehicles in the larger group have been selected. At the end of the time horizon for each vehicle, binary variables are known and set to 0 or 1. In the smaller set of vehicles (V 2), best binary variables are set to be the current values except the rst iteration where no history is available. Vehicles in this set are treated as the vehicles in the larger set. To determine the best binary variable values for each vehicle at the end of each iteration, the total mass of commodities, wounded, and workers picked up by the vehicle is measured; higher mass indicates a better route because this means the vehicle works more e ciently by picking up more commodities, wounded, and/or workers. If the current measure is improved, it is saved as the best performance for this vehicle and binary variables are saved as best binaries. The selection of 70% of the vehicles to be in the larger group is justi ed as follows. All the vehicles are working in parallel such that one route could a ect other routes and the best routes for the vehicles are created within di erent complete solutions from di erent iterations where each solution includes routes for all vehicles. Within the same solution, vehicles have no con icts such as an important node being visited by two vehicles at the same time while other important nodes are available for visit by that time. This is because the suggested approach prevents con icts from happening, as the prioritized demand value for visited demand nodes is dropped down. However, the best routes could have some con icts because they are produced from di erent solutions. Therefore, selecting many best routes to create a new complete solution could have some con icts that a ect the objective negatively. Accordingly, in the smaller vehicle group (V 2), the best route for each vehicle, achieved in previous iterations is selected to be the current route to take advantage of good inherited history. Preliminary results show that increasing the number of vehicles in (V 2) can worsen results; this why is the smaller group is set to the best routes while routes are constructed in the larger group. When all binary variables are set using the construction function or selected from the best history, the model is solved optimally in CPLEX where the binaries are set to zeros and 65 ones. The model is solved with CPLEX-Concert technology to determine the other variable values such as quantities picked up, quantities delivered, worker assignments, and wounded evacuation. Iterations end when the termination criterion is met. Many termination criteria can be used, including the total memory used, processing time, number of iterations, and number of iterations without improvement. In this research, time limit is selected in the numerical analysis because it is easier for users to set based on an actual situation. The pseudo code of this heuristic is provided in Algorithm 2. Algorithm 2: Main Heuristic 1: De ne the termination criterion 2: Set ?2[0;1;2;3] 3: Initialize incumbent Z =1 4: itr = 1 //Iterations counter 5: BPv = 0 8v2V 6: while Termination criterion not met do 7: Calculate the prioritized demand for all demand nodes, as PTD(t;i) = X c2C dCcit pCc + X e2E dEeit pEe + X w2W dWwit pWw 8i2D; t2T 8: Calculate the cumulative prioritized supply for all supply nodes, asPTS(t;i) = tX k=2 X c2C sCcik pCc + tX k=2 X w2W sWwik pWw 8i2S; t2T. 9: Randomly divide vehicle set V into 2 groups, V 1 and V 2 10: Reorder v2V 1 and v2V 2 to be randomly sequenced. 11: for all v2V 1 do 12: xvijt = 0 8i;j2Nni; t2T // Initialization and clear any 1 values from previous iterations 13: current = iv // Set current location to the depot of the selected vehicle 66 14: Calculate time-based importance for all nodes, such that 15: IMv = Importance v;current;N;PTS;PTD 16: Construct the route (Set the binary variables), xvijt 8i;j 2 N; i 6= j; t 2 T = Construction(IMv; v) 17: end for 18: for all v2V 2 do 19: if itr == 1 then // rst iteration, no history is available 20: current = iv //Set current location to the depot of the selected vehicle 21: Calculate the importance for all nodes, such that 22: IMv = Importance v;current;N;PTS;PTD 23: Specify the binary variables, xvijt 8i;j2N; i6= j; t2T = Construction(IMv; v) 24: end if 25: if itr 2 then 26: Use the binary variables associated with the best route as current variables, xvijt = xbvvijt 8i2N; j2Nni; t2T 27: end if 28: end for 29: Binary variable values = Construction function output or set from history 30: Solve the model using CPLEX// CPLEX determines variable values except xvijt, out- put Z and ZC 31: if Z Z then 32: Z = Z 33: Save the new solution ZB = ZC 34: end if 35: for all v2V do 36: Pv = X i2D X t2T X w2W mWw wDwivt + X i2D X t2T X e2E mEeePeivt + X i2D X t2T X c2C mCc zDcivt 37: if Pv BPv then // Performance improved 67 38: Save the current binary variable values of v as best values, xbvvijt = xvijt 8i2 N; j2Nni; t2T. 39: end if 40: end for 41: if ? = 1 then // (A) local search, performed at each iteration 42: XIinitialvijt = XCvijt 43: Local search XIinitialvijt // Function call 44: end if 45: if ? = 2 and Z Z then // (I) local search, performed at each iteration if the current solution improved 46: XIinitialvijt = XCvijt 47: Local search xinitialvijt // Function call 48: end if 49: itr = itr + 1 50: end while// End main loop 51: if ? = 3 then // (B) local search, performed at the end of all iterations 52: XIinitialvijt = XBvijt 53: Local search xinitialvijt // Function call 54: end if The Importance function depends on the node type, the current vehicle, and its loca- tion. Current location is used to incorporate the travel time between it and other nodes in the importance, where nearer nodes have higher importance. The other parameters are incorporated in the importance based on the node type, such as the demand and workers re- quested in the case of demand nodes and available supplies and workers in the case of supply nodes. To give more exploration choices, all importance values are slightly randomized by multiplying the value by a random number from the interval of [0.8, 1.2]. Selecting a wider 68 interval to select the random number increases the randomness. This worsens the results because it performs against the main concept of this proposed solution approach which is the greedy concept. This function is shown in Algorithm 3. Algorithm 3: Importance Function 1: for all t2T do 2: for all i2N do 3: Generate R //Random number [0.8,1.2] IMvt;i = 8 >>> >>> >< >>> >>>> : R tv;current;iPT D ti if i2D R tv;current;iPT S ti if i2S R v;current;i if i2H 4: end for 5: end for 6: Return IMv Route construction is used to set the binary variables to zero or one which is a major part of this solution approach. The pseudo code of the Construction function is shown in Algorithm 4. There are many important steps in this function. First, nodes from each type are sorted based on their importance value (IMv). Next, the time loop begins considering three possibilities for the current selected vehicle; demand node visits, supply node visits, and hospital visits. Only one of these possibilities can be performed at a given time, and each has two conditions. The rst is whether a possibility is selected or not, as in lines 12, 35, and 55. The second tests if this visit is feasible or not by satisfying many sub{conditions, such as determining if this node has been visited before by this vehicle, if it is reachable by the vehicle at time t which is done by check the equation tnow + v; current; sort(t;i) = t, and if the vehicle can return back to its depot before the end of time horizon if the node is visited 69 which is done by checking the inequality tnow + v; current; sort(t;i) + v; sort(t;i); iv jTj. These conditions are in lines 14, 37, and 57. If the demand node visit condition is satis ed, as in line 12, both t{loop in line 11 and demand nodes loop in line 13 are working in parallel to nd the nearest and most important demand node to visit. When a demand node is visited, its prioritized demand by the visiting time is decreased by dividing by 3. As prioritized demand values were calculated at the beginning of while loop in line 7 in Algorithm 2, the new reduced value of the visited demand will be used to calculate the importance values for the next selected vehicles. Reducing the prioritized demand value by a large amount causes the visited demand node to not be visited by other vehicles. After testing many reduction values, it is found dividing by 3 is the most proper value. In case of hospital node visits, as in line 35, a vehicle selects the most important hos- pital where the hospital importance values are calculated based on travel time with some randomness. Supply node visits, as in line 55, are similar to demand node visits; the sub{ conditions inside the supply node loop nd the nearest and most important supply node excluding its depot. Once a supply node is visited, its prioritized supply value is reduced for a period from the second time period to the current time. This is because vehicles can pick supplies from previous periods. To explain this, suppose that a supply node is visited by a vehicle at time t, and the next vehicle wants to visit the same supply node at an earlier time. It should be warned that the importance of this node is reduced. The rst time is excluded from prioritized supply value reduction because vehicles start picking up supplies and workers from the supply nodes at the rst time period. No information will be available about the remaining supplies and workers from the rst time and we can not depend on the rst time to recalculate the importance values. After the time loop ends, the selected vehicle returns back to its depot and the Construction function returns the binary values. 70 Algorithm 4: Construction Function 1: dem = 0 //Set demand node visits to zero 2: sup = 1 //Set supply node visits to one because the current vehicle leaves from its depot which is supply node. 3: hos = 0 //Set hospital node visits to zero 4: tnow = 1 5: for all t2T do 6: Sort demand nodes in descending order based on their total importance to get sortD. 7: Sort supply nodes in descending order based on their total importance to get sortS. 8: Sort hospital nodes in descending order based on their total importance to get sortH. 9: end for 10: Select a random integer number 2 c v 0:7 AvgD + 0:5 2; c v 0:7 AvgD + 0:5 + 2 // Based on vehicle capacity and average masses of workers and demand 11: for all t2T do 12: if dem then 13: for all i jDjdo 14: if it is feasible to visit demand node sortD(t;i) then 15: ^xv; current; sortD(t;i); t = 1 16: tnow = t 17: Update current = sortD(t;i) 18: Reduce the prioritized demand of sortD(t;i), such that 19: PTD(t;i) = PTD(t;i)=3 //to avoid revisiting by other vehicles 20: Recalculate importances for all nodes: // Because the current is updated 21: IMv = Importance v;current;N;PTS;PTD 22: for all k2T do // New sorting because importance values are updated 71 23: Sort demand nodes in descending order based on their total importance to get sortD. 24: Sort supply nodes in descending order based on their total importance to get sortS. 25: Sort hospital nodes in descending order based on their total importance to get sortH. 26: end for 27: dem = dem + 1 28: i = big number >jDj // end loop to avoid infeasibility due to visiting more than one node at the same time. 29: if dem = then 30: Select randomly from [1,2] // To decide the next step 31: end if 32: end if// End if feasible to visit 33: end for 34: end if 35: if == 2 And hos jHj // to exit the for loop 52: end if// End if feasible to visit 53: end for 54: end if// End hospital visit 55: if == 1 And sup jSj // to exit the for loop 74: Generate new value of // As in line 10, next steps must be demand nodes visits 75: end if// End if feasible to visit 76: end for 77: end if// End supply visit 78: end for// End t-loop 79: tnow = tnow + v;current;iv // time to return back 80: xv current iv tnow = 1 81: Return xvijt 8i;j2N; i6= j; t2T The previous approach with ? = 0 (no local search) is called Heuristic-0. Preliminary tests show that the main advantage of this approach is the short computation time, such as 1 minute to perform 100 iterations to solve small scale instance. This good attribute allows for further improvements by spending more time on computational e orts. Two kinds of local search are iteratively applied to improve Heuristic-0. First, if a node in a vehicle route is selected and is then found to be far from the previous or next node in the route, it could waste vehicle time. To solve this problem, an extensive search can be performed to nd two nearer nodes to replace it. In this case, a neighborhood is de ned as any solution which can be constructed by replacing a node with two nodes. This search is called a Replacement local search heuristic. 74 Second, in some routes, vehicles might have an idle time. For example, if three time periods are available to a vehicle, and it can not nd a node to visit before the end of the time horizon, it could return to its depot in one time period and sit idle for the next two. In this event, local search is performed to nd a node which can be inserted in earlier route steps without a ecting the feasibility of the route. In this case, a neighborhood is de ned as any solution which can be constructed by inserting a node at any point in the route. This is called an Insertion local search heuristic. Figure 4.2 provides an explanation of both replacement and insertion. (a) Replacement (b) Insertion Figure 4.2: Local search operations The pseudo codes for both searches are provided in Algorithm 5, where 1 is the number of iterations each local search is repeated using the same starting solution, and 2 is the number of trials used to perform insertions or replacements inside each local search iteration. In other words, each iteration of 1 starts with the same initial solution, and 2 is the number of trials performed inside each iteration of 1. Di erent values of 1 and 2 were tested, and results show that in most data sets the number of local searches required for at least one success is 4, so both 1 and 2 are xed at 2. Let 3 represent the number of random nodes generated and tested for feasibility of use in replacement or insertion; this number is selected to be a large value such as 100 because 75 the chance of success for replacement or insertion using random nodes is very low, and the calculations can be done in a very short time. These local searches start from an initial solution, XIinitialvijt , which is a four dimensional array that contains the value of all binary variables, such that it contains the elements xiinitialvijt 8v 2 V; i;j 2 N; i 6= j; t 2 T. It could be the current solution (XIinitialvijt = XCvijt), the current solution if improved compared with previous solutions (XIinitialvijt = XCvijt and ZC Z ), or the best solution at the end of all iterations (XIinitialvijt = XBvijt). The variable array (^xn0vijt 8v 2 V; i;j 2 N; i 6= j; t 2 T) is used to save the updated binary variable values after replacement in the nth iteration, whereas ^xnvijt 8v2V; i;j 2 N; i6= j; t2T is used to save the updated binary variable values after insertion in the nth iteration. At the end of local search, ^x 2vijt 8v2V; i;j2N; i6= j; t2T is used to save the last updated binary values after replacement and insertion have been performed 2 times. Algorithm 5: Local search function 1: for y = 1 : 1 do 2: ^x0vijt = xinitialvijt // Initialization 3: success = 0 4: for n = 1 : 2 do 5: Try Replacement, ^xn0vijt 8v2V; i;j2N; i6= j; t2T = ReplacementfV; ^xn 1vijtg 6: if replacement succeeded then 7: success = 1 8: end if 9: Try Insertion, ^xnvijt 8v2V; i;j2N; i6= j; t2T = InsertionfV; ^xn0vijtg 10: if insertion succeeded then 11: success = 1 12: end if 76 13: if success = 1 then 14: Solve the model at speci c ^x 2vijt 8v2V; i;j2N; i6= j; t2T variables using CPLEX // Determine all variables except xvijt, output Z and ZC 15: if Z Z then 16: Z = Z 17: Save the new solution ZB = ZC 18: end if 19: end if// end if success = 1 20: end for// end for loop of 2 21: end for// end for loop of 1 The Replacement function is performed using the following approach. Replacement function starts with vehicle loop, creating a route for the current vehicle by putting the nodes that have binary variables of value 1 in ascending order of time index. The bene t of creating routes from the binaries is to facilitate the coding process. A loop for the nodes in the route starts. If the travel time between a node and the next node in the route is greater than or equal to twice the minimum travel time in the network, this means there is a chance of nding two nodes for replacement. Once this condition is satis ed, two random nodes of any type are generated many times (e.g., 100 times) and determined if they can be placed in the route by testing if they are visited anywhere in the route and if the travel times needed to visit them can be satis ed. After this procedure, we might have updated binary variable values or we might not nd any possibilities for replacement. 77 Algorithm 6: Replacement local search function 1: for all v2V do 2: Create route using binary variable values 3: for all i2Routev do 4: if node v;i 1;i or v;i;i+1 2 the shortest time needed by v to pass between any two nodes in the system then 5: while Stopping criterion is not met do // 3 trials 6: Generate two nodes randomly x; y 7: if Feasible to replace i by these two nodes then 8: Replace i by x; y 9: end if 10: end while 11: end if 12: end for 13: end for 14: Return ^xn0vijt 8v2V; i;j2N; i6= j; t2T Insertion is demonstrated in the next approach. The Insertion function starts the vehicle loop that takes the binary variable values from the replacement function as an input. If the time for the current vehicle is less than the total time available, this means there is idle time somewhere in the route and a chance to insert a node or more. A random node is selected and tested to determine if it can be inserted in the route. If the travel time between it and any two nodes in the route is less than or equal to the idle time and if it is not visited by the same vehicle in the route, then it is viable insertion. The condition at line 6 is done by a loop to insert the random node anywhere in the route. After the Insertion function, a new update of binaries might be available. 78 Algorithm 7: Insertion local search function 1: for all v2V do 2: Create route using binary variable values 3: if Total time needed for Routev 1g (5.43) X e2E eDeivt M5:44 X j2N xVvjit 8e2E; i2H; v2V; t2T (5.44) X e2E ePeivt M5:45 X j2N xVvjit 8e2E; i2D; v2V; t2T (5.45) X w2W wDwivt M5:46 X j2N xVvjit 8w2W; i2D; v2V; t2T (5.46) X w2W wSPwivt M5:47 X j2N xVvjit 8w2W;i2Sniv; v2V; t2T (5.47) wPwiVv vt = 0 8w2W; v2V; t2fT : t> 1g (5.48) X j2N xVvjit M5:49 X f2F X j2L[iFf xFfjit 8v2V;i2L;f2F; t2T (5.49) The objective functions (5.1){(5.3), seek to minimize the quantities of unsatis ed de- mand, non-transfered workers, and unserved wounded, respectively. Each of these quantities are scaled by their respective priority values which vary between nodes. The second term in each function is a very small value used to ensure the SFs return to their depot, once they nish distribution. The value of this term should be small compared to the rst term (deviation term) so that it does not a ect the distribution quantities. Constraints (5.4){(5.13) are used to construct the vehicle routes in the following ways. Constraints (5.4) ensure that each vehicle may serve only one node at each time. Constraints (5.5) ensure that each vehicle starts from its initial depot, while Constraints (5.6) ensure that it returns to its initial depot after nishing its route. Constraints (5.7) prevent the creation of infeasible initial visits (e.g., reaching a node in less time than is needed) for the vehicles. Constraints (5.8) restrict each vehicle?s route by the total time available for that vehicle. Constraints (5.9) restrict each vehicle from visiting any node more than once. 120 Hospital nodes are excluded because they can be revisited by the same vehicle multiple times, so Constraints (5.10) and (5.11) are added to ensure the feasibility of revisiting hospitals. Constraints (5.10) ensure that if a vehicle leaves a hospital node it must have traveled to this hospital from another node, and Constraints (5.11) balance the vehicle ows at each hospital node. To maintain feasibility of routes, Constraints (5.12) ensure that no vehicle can reach any node before nishing the arc between that node and the current node. Constraints (5.13) balance the ow of each demand node so each vehicle enters and leaves each node the same number of times. Satellite facilities are routed di erently because they can revisit the same node and stay more than one time period at a given SF location; consequently, variables xFfijf; where i = j, are de ned and can take a value of 1. Constraints (5.14) and (5.15) ensure that each SF leaves from and returns to its depot only once. Constraints (5.16) ensure that each SF can be in only one location at a given time. Constraints (5.17) prevent each SF from making any infeasible initial visit, such as reaching the rst node in the route in less time than is needed. Constraints (5.18) maintain the feasibility of the route series by ensuring that if a SF visits a SF location node, it must come from its depot or another SF location. Constraints (5.19) ensure that the number of SFs leaving a node is less than the number to enter the same node, this balances the SF ows at each node. Similar to the constraints for small vehicles, Constraints (5.20) ensure that each SF must return to its depot before the end of the available time slots. Constraints (5.21), (5.22), and (5.23) de ne the deviation variables: (5.21) address un- satis ed demand, (5.22) address non{evacuated wounded, and (5.23) consider non{transfered workers. Vehicle supply restrictions are found in Constraints (5.24){(5.26). Constraints (5.24) restrict the delivered commodities to the quantity picked up from suppliers and SFs. Con- straints (5.25) restrict the delivered wounded to the number picked up from demand nodes. Constraints (5.26) restrict the delivered workers to the number picked up from suppliers and 121 SFs. Constraints (5.34) ensure that wounded persons picked up from demand nodes are transferred to hospital nodes. Similarly, Constraints (5.27), (5.28), and (5.29) restrict the nodes supply and transfer at each time. Constraints (5.27) ensure that each supply node can provide quantities not exceeding the available supply of each commodity type. Constraints (5.28) limit the number of assisted wounded to be no more than the number waiting at a particular demand node. In the same manner, Constraints (5.29) ensure that the number of workers dispatched from any supply node does not exceed the actual number of available workers. In Constraints (5.27) and (5.29), it is assumed that SFs can pick up commodities and workers only once from their depots and perform one trip to deliver commodities and workers to small vehicles. This assumption can be relaxed by adding new time{based variables representing the amount of commodities and the number of workers that picked up from other supplies nodes (Wwift; Ccift instead of Wwf; Ccf). This complicates the model and makes it hard to be mathematically solved and to be accomplished in practice. Constraints (5.32) prohibit each SF from providing quantities of a commodity type exceeding what was picked up at its depot. Similarly, Constraints (5.33) ensure that SFs can not provide a number of workers from each category exceeding the number picked up by the same SF. Vehicle capacity limitations are included in Constraints (5.30), while Constraints (5.31) consider the SFs? capacity limitations. Constraints (5.34){(5.36) ensure that any picked up commodity, worker, or wounded person must be delivered. Constraints (5.37){(5.48) ensure that all distribution and transfer variables have a value for any node only if a vehicle or SF visits that node. Constraints (5.37) allow for the delivery of commodity type c to a demand node i at time t by vehicle v only if the vehicle visits that node at that time. Constraints (5.38) allow vehicle v to pick up commodities of type c from supply node i if it visits the node at that time; vehicle depots are excluded from this constraint set. For candidate SF locations, Constraints (5.39) ensure that a vehicle can pick up from a SF location only if it visits the SF location. Constraints (5.40) ensure that 122 vehicle v can pick up workers from SF location l only if it visits the SF location at time t. Constraints (5.41) ensure that SF f can deliver commodities to a candidate SF location l if it visits the location at time t. For workers, Constraints (5.42) ensure that SF f can deliver workers to vehicles at candidate SF location l if it visits the location at time t. Constraints (5.43) ensure that each vehicle can pick up commodities from its depot only at the beginning of the time horizon; once it leaves the depot, it can not revisit the depot again until it is nished. Constraints (5.44) allow vehicles to deliver wounded to a hospital only if they visit the hospital. For wounded pick{ups, Constraints (5.45) ensure that a vehicle can pick up wounded from a demand node only if the vehicle visits the demand node. Constraints (5.46) ensure that if a vehicle visits a demand node, then it can deliver workers. Constraints (5.47) ensure that a vehicle can pick up workers only if it visits a supply node which is not its depot. Constraints (5.48) ensure that each vehicle can pick up workers from its depot only at the beginning of a plan series since it can not revisit the depot during the time horizon. The big-M values in Constraints (5.37){(5.42), (5.44){(5.47), and (5.49) are de ned as follows. By using the lowest possible value for each M, the computation e ort is potentially saved because the solver may start with better bound for the linear program relaxation. Value of M in each constraint should be de ned for all indices of the constraint. For simplicity, the notations are slightly abused and big-M values are de ned just once for each constraint. For example, M5:37 is de ned instead of the de nition of Mivt5:37. M5:37 =min dCcit;m V v mCc 8i2D; v2V; t2T M5:38 =min 8 >< >: X s2Ts t sCcis;m V v mCc 9 >= >; 8c2C;i2Sni V v;v2V; t2T M5:39 =m V v mCc c2C; i2L; v2V; t2T M5:40 =m V v mWw 8w2W; i2L; v2V; t2T 123 M5:41 =m F f mCc c2C; i2L; f2F; t2T M5:42 =m F f mWw 8w2W; i2L; f2F; t2T M5:44 =m V v mEe 8e2E;i2H; v2V; t2T M5:45 =min dEeit;m V v mEe 8e2E;i2D;v2V; t2T M5:46 =min dWwit; m V v mWw 8w2W;i2D;v2V; t2T M5:47 =min sWwit;m V v mEe 8w2W;i2D;v2V; t2T M5:49 =jFj 8v2V;i2L;f2F; t2T (5.50) Finally, Constraints (5.49) allow vehicles to visit a candidate SF location only if a SF visits the same SF location at that time, otherwise, such visitations are useless. In the next section, a small example is used to verify this model. 5.5 Numerical Example The goal of the small example presented here is to verify the model, not to discuss how it is solved. Solution approaches are developed and fully explained in the next section. This example is solved by CPLEX{Concert technology using a single objective function that includes all logistic operations, as follows Min X c2C X i2D X t2T pCci vCcit + X w2W X i2D X t2T pWwi vWwit + X e2E X i2D X t2T pEei vEeit (5.51) Two regular vehicles, each of di erent capacity and travel speed are used together, with a single SF. There are four demand nodes, one supply node, and one hospital node. Three candidate SF locations for the SF have been pre{determined. A single commodity type 124 is considered. Similarly, wounded persons are classi ed as being of the same category, as are workers. Additional problem details, including the commodity demands over time, are shown in Figure 5.3a. This example is solved twice: once using the available SF, and again without utilizing the SF. Figure 5.3b shows the route of the SF. Figure 5.3c shows the plan of the rst vehicle while the use of the SF is allowed, and Figure 5.3d shows the plan when the use of the SF is prohibited. Similarly, Figure 5.3e shows the plan of the second vehicle using the SF and Figure 5.3f shows the plan of the second vehicle without using the SF. 125 (a) HLVRPSF Example Data (b) SF Route (c) First vehicle plan using SF (d) First vehicle plan without using SF (e) Second vehicle plan using SF (f) Second vehicle plan without using SF Figure 5.3: Solution of the HLVRPSF model example for both options: with and without using the available SF 126 The rst vehicle visits 3 demand nodes when the SF is not used and only 2 when it is used, as shown in Figures 5.3a and 5.3b. Nevertheless, it delivers less demand quantity (400 food bags) when the SF is not used compared to the other case (640 food bags). This is because when using the SF, the rst vehicle visits a location and loads 240 food bags from the SF which allows it to deliver more quantity, even with a smaller number of demand nodes visited. In both cases, the vehicle evacuates 6 persons and does not transfer any workers. The second vehicle delivers 752 food bags when using the SF (as in Figure 5.3e) and only 400 food bags otherwise (as in Figure 5.3f). In both cases, this vehicle visits the hospital 3 times, but in case when not using the SF, the vehicle visits 2 of the demand nodes empty to pick up wounded without delivering any workers or food bags because no more supplies are available. This results in fewer e cient visits. If more demand nodes were available in the example and the time horizon was longer, this vehicle, when not using a SF, is expected to perform more evacuations. This is not preferable in some actual cases such as if hospitals have limited work capacity and if the demand distribution is much important than evacuation. To quantify the comparison, Table 5.1 summarizes the total numbers of commodities, workers, and wounded in both cases. Using SF Without using SF Food bags delivered 1,392 800 Workers transfered 8 1 Wounded evacuated 24 27 Total mass (lb) 10,576 8,000 Table 5.1: Summary of the HLVRPSF example solution for both options: with and without using the available SF In Table 5.1, it can be obtained that when using a SF, vehicles are more fully utilized since they load 10,576 lb using the SF compared to 8,000 lb when not using the SF. In this particular example, worker priorities are low, and it can be noticed that only 1 worker is transfered when not using a SF. When using a SF, because vehicles know ahead of time that resupplies are allowed during the route, the second vehicle picks up 4 workers at the 127 beginning which improves the operation of work{force transfer. This is another bene t of using a SF in this example. The previous comparisons show that the using SFs improves the logistics system with a single objective. However, using a single objective in the HLVRPSF is not appropriate. Consequently, one of the main ideas of the HLVRPSF is to incorporate multiple objectives. To check how the SFs improve the HLVRPSF with multiple objectives, the next section will solve many instances, where each instance is solved three times considering a single objective function each time. 5.5.1 Examples to Demonstrate SF Bene ts In this section, di erent examples are solved in di erent ways to show the bene ts of using SFs in humanitarian logistic systems. Allowing small vehicles to be resupplied from SFs at SF locations o ers more choices and exibility for resupply operations. This saves time for vehicles and allows them to visit more nodes which results in more commodity delivery, worker transfer, and wounded evacuation. To show an example of such logistic system enhancement, 10 di erent data sets are randomly generated. Each of the 10 sets is solved 6 times using CPLEX{Concert technology with a time limit equal to 3 hours. They are solved 6 times to cover all possible combinations of objective functions and SF utilization options. First, using objective function 5.3 to minimize the total wounded deviation variables and vehicles can be resupplied only from supply nodes. Second, using objective function 5.3 to minimize the total wounded deviation variables and vehicles can be resupplied from supply nodes or from SFs at SF locations. The results of both options are plotted in in Figure 5.4a. Third, using objective function 5.2 to minimize the total worker deviation variables and vehicles can be resupplied only from supply nodes. Fourth, using objective function 5.2 to minimize the total worker deviation variables and vehicles can be resupplied from supply 128 nodes or from SFs at SF locations. The results of the third and fourth options are shown in Figure 5.4b. Fifth, using objective function (5.1) to minimize the total commodity deviation variables and vehicles can be resupplied only from supply nodes. Sixth, using objective function 5.1 to minimize the total commodity deviation variables and vehicles can be resupplied from supply nodes or from SFs at SF locations. Results of these options are shown in Figure 5.4c. 1 2 3 4 5 6 7 8 9 10 1 1.5 2 2.5 3 x 105 Data Set Total Wounded Deviations (Objective Value) Minimize Wounded Deviations Vehicles can be supplied from SFs and supply nodesVehicles can be supplied only from supply nodes (a) Objective Function is to Minimize Wounded Evacuation Devia- tions 1 2 3 4 5 6 7 8 9 101.5 2 2.5 3 3.5 4 4.5 x 105 Data Set Total Workers Deviations (Objective Value) Minimize Workers Deviations Vehicles can be supplied from SFs and supply nodesVehicles can be supplied only from supply nodes (b) Objective Function is to Minimize Workers Transfer Deviations 1 2 3 4 5 6 7 8 9 100.6 0.8 1 1.2 1.4 1.6 1.8 x 105 Data Set Total Commodities Deviations (Objective Value) Minimize Commodities Deviations Vehicles can be supplied from SFs and supply nodesVehicles can be supplied only from supply nodes (c) Objective Function is to Minimize Commodity Delivery Devia- tions Figure 5.4: HLVRPSF model, with SFs vs. without SFs In Figure 5.4, there are no signi cant di erences in part (a) which is expected because in minimizing the wounded evacuation deviations, vehicles are not resupplied, but they are utilized for evacuation only. The small di erences are because some data sets are not solved optimally in 3 hours which causes very tiny di erences between the options of using SFs and not using SFs. In parts (b) and (c), there is an improvement because there are more locations added for resupply instead of depending only on supply nodes. The improvement average in part (b), where the objective is to minimize the worker transfer deviations, is 129 3.7%. In part (c), where the objective is to minimize the commodity delivery deviations, the improvement average is 5%. These improvement values are expected to be higher in medium and large scale sets where longer time horizons are available, more vehicles are considered, and more replenishments are needed by each vehicle. As shown in the previous section, the improvements are achieved by visiting more nodes and/or delivering higher quantities of demand and workers. In this section, an example was solved using CPLEX with a single objective function includes the objective functions (5.1), (5.2), and (5.3) in a linearly weighted manner. Since a single objective function was used in this example, only one solution is provided containing all logistic operations (i.e., demand distribution, work{force transfer, and wounded evacuation). After that, in the sub{section 5.5.1, ten data instances were solved using exact solution procedure by CPLEX three times (considering only the cases of using SFs) where one of the objective functions (5.1), (5.2), and (5.3) is used each time. Three solutions are provided for each data set where each solution contains only one logistic operation based on which objective function was used. For example, if the objective function (5.1) is used, only demand distribution is performed. Based on this, depending on a single objective function includes all functions in a weighted form is not useful because it provides only a single solution, and solving the model three times where one objective function is used each time is not also useful because only three solutions are provided and each solution contains only one logistic operation. Additionally, exact solutions using CPLEX require a very long time. The HLVRPSF model is suggested to be a multiple objective model, and multiple solu- tions should be provided after solving the model with di erent combinations of the logistic operations. In the next sections, di erent solution approaches are suggested to provide a wide range of solutions in a reasonable amount of time. 130 5.6 Description of the HLVRPSF Solution Approach In multi-objective models, many solutions should be provided after solving the models to o er a wide variety of solution options where some of them are excellent for some of objective functions and bad for others. In the case of competing objectives, decision makers seek solutions that are acceptable for all objectives. Before proceeding, some important de nitions and explanations should be considered. Consider a problem with K objectives, and let X represent a solution vector with objective function values equal to z(X) = z1(X);z2(X);:::;zk(X). Solution X is said to dominate some other solution Y in a minimization problem if zi(X) zi(Y) 8 i = 1;:::;k and zi(X)