Transportation Research Part E: Logistics and Transportation Review
A hierarchical clustering and routing procedure for large scale disaster relief logistics planning
Highlights
► Hierarchical method is developed for logistics of large scale post disaster relief. ► Top level model is solved to assign depots and hospitals to demand cluster centers. ► Detailed routing decisions for each cluster are optimized using network flow model. ► Relief activities with networks up to 900 nodes are coordinated successfully. ► Scenarios show that procedure obtains solutions within 12% above the lower bound.
Introduction
Disaster relief logistical planning is crucial for the effectiveness and speed of response in aid distribution programs, such as health, food, shelter, water and sanitation. In disaster response logistics, distribution of relief materials and evacuation of injured persons are two major activities. The evacuation of the injured takes place primarily during the initial response phase, whereas the distribution of relief materials tends to continue for a longer time.
Beamon and Balcik (2008) define the objective of the disaster relief supply chain as “to provide humanitarian assistance in the forms of food, water, medicine, shelter, and supplies to areas affected by large scale emergencies”. Tomasini and Van Wassenhove (2009) point out the differences between commercial and humanitarian supply chains and state that the ultimate effective humanitarian supply chain management has to be able to respond to multiple interventions as quickly as possible and within a short time frame.
In this study, we focus on the last stage of the relief supply chain, in particular, “the last mile distribution problem” that arises in disaster response. Based on the logistics module of the UNDP’s Disaster Management Training Programme, Balcik et al. (2008) define the last mile distribution problem as “the last stage of humanitarian operations that involves delivery from local distribution centers (tertiary hub) or from central warehouses (secondary hub) to a population in need (beneficiaries)”.
Here, we extend the above definition to include both delivery and pickup functions, and call it “the last mile delivery and pickup problem”, where the last mile delivery is concerned with materials transported from warehouses to affected locations and the last mile pickup is concerned with the evacuation of injured people from affected areas to hospitals.
In a post-disaster situation, the Disaster Coordination Center (DCC) conducts air surveys over affected areas and information starts to flow from districts using other channels as well. Hence, the DCC has very rough estimates of the quantities of aid materials to be delivered to survivors in various areas. Similar estimates are made for the rising number of urgent evacuations while access to the region is enabled. Here, it is assumed that the operational logistics plans are made based on such estimates. These plans are updated as more precise information reaches the DCC. It is also noted that during post-disaster relief activities, requests on transportation capacity often surpass the available capacity significantly and vehicles depart from and arrive to warehouses/hospitals with full load. Therefore, it is not quite possible to modify the courses of vehicles en route whenever new information arrives. Usually, new requests are assigned to vehicles that are about to complete their tours. The latter approach reduces the nervousness of the logistics plans that might be caused by the rough estimates of parameters that the DCC puts into the plans.
An efficient network flow model and a parallel hierarchical optimization guided “cluster and route” procedure (HOGCR) are proposed here for preparing the transportation plans of the last mile delivery and pickup problem described above. The goal of the model is to minimize total travel time of vehicles and to promote efficient resource utilization while respecting vehicle and supply availability restrictions.
The proposed HOGCR is able to deal with large scale relief networks (here scenarios of up to 1000 nodes are tested), achieving a good quality solution within a few minutes of CPU time. The HOGCR applies the “divide and conquer” approach, where the relief network is divided recursively into demand node clusters until the final cluster sizes enable the optimal solution of the cluster networks’ routing problems. The procedure is hierarchical because each demand node cluster also includes the warehouse and hospital nodes with their allocated partial capacities. The latter allocation is optimized in an upper level aggregate problem. Hence, the consistency of the transportation capacity, hospital space and supply availability is preserved throughout the planning hierarchy. In the HOGCR, the routing problems of cluster networks are solved in parallel and independently, creating a computationally efficient environment.
The HOGCR is a novel approach in both the emergency and the commercial logistics-vehicle routing literature, where Genetic Algorithms, Tabu Search and Scatter Search are proposed (Archetti et al., 2006, Archetti et al., 2008, Yi and Kumar, 2007, Campos et al., 2008, Berkoune et al., 2010, Lin Batta et al., 2011) as well as methods such as sequential MIP solution (Chen et al., 2007). These approaches can solve networks with up to 300 nodes and their solution quality has not been verified against optimal solutions.
In the subsequent sections of this paper, we describe the HOGCR and test the performance of the algorithm on a number of hypothetical disaster relief networks as well as on a large scale earthquake scenario for the city of Istanbul.
Section snippets
Survey of models proposed for disaster relief logistics
Commercial and humanitarian supply chains are very different in nature (Tomasini and Van Wassenhove, 2009). While commercial chains are concerned with profit maximization, humanitarian chains are involved with maximizing the beneficiaries’ satisfaction (Beamon and Balcik, 2008). Yet, in the disaster relief literature, we observe different objective functions described in logistical models concerned with the last mile relief distribution (Balcik et al., 2008). Examples include maximizing
Overview of the HOGCR
The HOGCR utilizes an efficient network flow model in a hierarchical “cluster first, route second” approach. The method always produces feasible solutions and it offers the flexibility of adjusting the solution quality by imposing different runtime restrictions on the optimization software package CPLEX.
As Bard and Jarrah (2009) point out, large scale delivery and pickup operations are best dealt with by clustering demand nodes and downsizing the network. In our approach, we divide the demand
The mathematical model
The model represents the last mile delivery and pickup vehicle routing problem of cluster networks, and it is a modified static version of the model described in Yi and Ozdamar (2007).
The assumptions of the model are as follows: (i) estimates of demands at affected locations are known; (ii) the demand for materials at affected locations and the number of injured persons waiting to be picked up at each location might be larger than a vehicle’s cargo capacity and split deliveries and pickups are
Description of the HOGCR
In the HOGCR, the demand nodes in the relief network are first sub-divided into K demand clusters using the k-means partitioning heuristic. The reason for selecting this particular clustering algorithm is to limit cluster sizes. In the k-means partitioning heuristic, K demand nodes are randomly selected from the set CD as cluster centroids and each of the remainder demand nodes is assigned to the nearest centroid. Then, centroid positions are re-calculated according to the clusters formed and
Numerical experiments on hypothetical relief networks
The performance of the HOGCR is tested on 15 hypothetical relief networks, the first eleven instances having 100 nodes and the last four instances having 200, 300, 400 and 500 nodes, respectively. The number of warehouses in these networks varies between 5 and 15. We assume that a hospital exists beside each warehouse. The relief network consists of demand and supply node locations that are generated randomly within the main grid. The smallest grid size is 50 × 50 and the largest is 100 × 100
Description of the scenario
We illustrate the implementation of the HOGCR on a clean water distribution scenario that might take place after an earthquake hits Istanbul. This would be one of the response actions to be taken up by AKOM (the Disaster Coordination Center in Istanbul) against cholera and other water born diseases. The sewage system in Istanbul is not expected to be safe after an earthquake hits the city and the citizens need to have non-infected water at least to wash their hands and take care of their basic
Conclusion
Our target is to coordinate the logistics of the last mile delivery and pickup activities in disaster relief supply chains. With this goal, we propose an efficient mathematical model and a hierarchical cluster and route procedure (HOGCR) that uses this model. This approach is based on clustering demand nodes and solving the aggregate problem in order to find the optimal allocation of warehouses and hospitals to demand cluster centers. Once, the aggregate solution is obtained, the detailed
Acknowledgment
We would like to express our sincere thanks to The Editor, and to the anonymous referees whose detailed reviews and constructive comments helped us improve the article. We also thank The Scientific and Technological Research Council of Turkey (TUBITAK) who partially supported this study with the research Grant No. 110M578.
References (25)
- et al.
OR/MS research in disaster operations management
European Journal of Operational Research
(2006) - et al.
Resource allocation in state dependent emergency evacuation networks
European Journal of Operations Research
(1996) - et al.
An interactive approach for hierarchical analysis of helicopter logistics in disaster relief operations
European Journal of Operational Research
(2002) - et al.
Large scale constrained clustering for rationalizing pickup and delivery operations
Transportation Research Part B
(2009) - et al.
Real time mobilization decision for multi-priority emergency response resources and evacuation groups: model formulation and solution
Transportation Research: Part E
(2007) - et al.
Multiperiod integrated routing and scheduling of World Food Programme cargo planes in Angola
Computers and Operations Research
(2007) - et al.
Formulation and solution of a multi-commodity, multi-modal network model for disaster relief operations
Transportation Research Part A – Policy and Practice
(1996) - et al.
Stochastic optimization of medical supply location and distribution in disaster management
International Journal of Production Economics
(2010) - et al.
A dynamic logistics coordination model for evacuation and support in disaster response activities
European Journal of Operational Research
(2007) Humanitarian logistics: a new field of research and action
Foundations and Trends in Technology, Information and Operations Management
(2009)
A tabu search algorithm for the split delivery vehicle routing problem
Transportation Science
Cited by (224)
Multi-period vehicle routing problem with time windows for drug distribution in the epidemic situation
2024, Transportation Research Part C: Emerging TechnologiesComputational approaches for solving two-echelon vehicle and UAV routing problems for post-disaster humanitarian operations
2024, Expert Systems with ApplicationsLocating and deploying essential goods and equipment in disasters using AI-enabled approaches: A systematic literature review
2023, Progress in Disaster ScienceRobust vehicle routing with drones under uncertain demands and truck travel times in humanitarian logistics
2023, Transportation Research Part B: MethodologicalAI for large-scale evacuation modeling: promises and challenges
2023, Interpretable Machine Learning for the Analysis, Design, Assessment, and Informed Decision Making for Civil InfrastructureBibliometric analysis and system review of vehicle routing optimization for emergency material distribution
2022, Journal of Traffic and Transportation Engineering (English Edition)