خوشه بندی سلسله مراتبی و روش مسیریابی برای برنامه ریزی لجستیک(تدارکات) امداد رسانی بلایای طبیعی در مقیاس بزرگ

We describe a hierarchical cluster and route procedure (HOGCR) for coordinating vehicle routing in large-scale post-disaster distribution and evacuation activities. The HOGCR is a multi-level clustering algorithm that groups demand nodes into smaller clusters at each planning level, enabling the optimal solution of cluster routing problems. The routing problems are represented as capacitated network flow models that are solved optimally and independently by CPLEX on a parallel computing platform. The HOGCR preserves the consistency among parent and child cluster solutions obtained at consecutive levels. We assess the performance of the algorithm by using large scale scenarios and find satisfactory results.

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 and 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.

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 routing problem within each cluster’s sub-network is solved by letting relevant parts of the top level solution become problem parameters. The solutions for the cluster sub-networks are obtained on parallel machines because they are not inter-dependent. The hierarchical clustering system always generates feasible vehicle routes without the need for route repair and no discrepancies arise between the solutions at consecutive aggregation levels. Our numerical results show that we obtain solutions within a percentage deviation of less than 12% from a strong lower bound for large scale relief networks. In other words, we expect our solutions to deviate from the optimal solution by less than 12%. Due to the parallel computing environment, we achieve these results within 15 min of CPU time. If we allow longer CPU times for cluster problems, we can achieve an even better solution quality. The parallel multi-level clustering approach is quite flexible in the sense that its solution quality can be controlled by the runtime parameter of CPLEX. This feature is important in the dynamic environment of disaster relief activities, where information updates are very frequent and plans are re-generated on a rolling horizon basis. The contribution of this paper to the literature is that it describes a novel optimization based hierarchical planning method that uses the “divide and conquer” approach in order to coordinate large scale relief activities. To our knowledge, the disaster relief logistics literature is at its early stage and solution approaches can deal with smaller scenarios (e.g., Barbarosoglu et al., 2002, DeAngelis et al., 2007, Yi and Kumar, 2007, Ozdamar and Yi, 2008, Berkoune et al., 2010 and Lin Batta et al., 2011). On the other hand, the commercial split delivery and pickup vehicle routing problem (SDPVRP) is a related logistics problem that makes similar but less complicated assumptions. In the SDVRP literature, none of the proposed solution methods include such a hierarchical clustering approach (e.g., see Belenguer et al., 2000 for a cutting plane algorithm; Archetti et al., 2006 for a tabu search algorithm; Archetti et al., 2008 for integer programming plus tabu search; Campos et al., 2008 for Scatter Search algorithm; Chen et al., 2007 for sequential MIP solution). In these studies, the size of the SDPVRP networks solved by such heuristics is below 300 nodes (Chen et al., 2007), and the solution times for networks over 100 nodes exceed 5000 CPU sec. Performance assessment of these heuristics is made with respect to each other and a strong lower bound such as the one identified in this study is not available. In contrast to these studies, the proposed HOGCR can attack larger problems and its performance assessment is quite reliable.