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)