Optimizing Evacuation of Disaster Victims
A guest article written by students Arielle Sanford and Arjun Sethi-Olowin, edited by Tyler Perini.
Natural disasters have plagued humanity for all of history. However, in recent years with the rise of climate change, major weather events such as hurricanes have come with even increasing intensity [1]. The number of hurricanes has also seen a slightly trended upward in recent years (see Figure 1), which is thought to be in part due to global warming. Higher intensity and greater frequency of natural disasters results in more loss of life and property damage, including destruction of critical infrastructure. To specifically address the loss of life, studies have been conducted to optimize the transport of injured civilians between disaster zones and treatment facilities, be they hospitals or temporary shelters.
The research paper Integer Linear Program Approach for Evacuation of Disaster Victims with Different Urgency Levels — authored by Byung Hoon Oh, Kwangyeon Kim, Han-Lim Choi, and Inseok Hwang — aims to tackle the question of transporting patients with degrees of injury varying from severe to light, which generalizes the assumption that all patients require hospital care with equal urgency. Their novel approach to this feature uses the following intuition: “different urgency levels can be posed as time constraints that vary among victims.” In a broad sense, they use previous work on the pickup and delivery problem with time window (PDPTW) to deliver all demand (patients in this case) within each demand’s time window — think of the classic problem faced by Uber Eats. The PDPTW problem has been explored previously by Baldacci et al. (2011)[3]. Baldacci provides a solution to minimize costs in transportation of goods by customer requests while satisfying time windows and capacity constraints. Building off this work, Hoon Oh et al. are able to expand said model to include priority.
The authors maximize the number of patients transported to safety in time, including constraints to model: the carrying capacity of each helicopter (as the mode of transportation); the endurance in terms of fuel of each helicopter; the varying survival times of patients with varying degrees of injury; and routing constraints to avoid unnecessary (i.e., suboptimal) helicopter flights that might refuel or pick-up/drop-off patients.
The primary decision variable is defined as x, which represents the number of trips of a vehicle from node i to node j to deliver the patients of a given urgency-category in a given cycle. This cycle concept is key to understanding the model: it includes all the patients serviced at various locations before having to refuel the vehicle. One cycle can be modeled as a max flow network. Then the total number of cycles represents the total number of refueling stops for a helicopter.
This network diagram illustrates an example cycle for some vehicle. The vehicle must start and end at its base, B (the node has two copies for illustration purposes). The vehicle will depart from its base and arrive at one of the demand sites, labeled D (denoted by the blue arrows). Then it must move to the demand site’s corresponding destination, labeled R (denoted by the bidirectional orange arrows). From a destination, the vehicle can move to any of the demand sites or back to its base B (denoted by the green arrows). Notably, a vehicle is not allowed to pick up a patient from a demand site and then head directly to its base without delivering the patient to their destination, first.
As an example, we demonstrate one potential cycle which maps the flight of a helicopter as it delivers and patients to hospitals before returning to base to refuel and embark upon its next cycle.
With this network and these decision variables, the model can now be outlined with an objective function and constraints. The objective is to minimize the total number of unserviced demands, represented by W, summed over all categories and all demand sites. The first constraint represents the number of flights into and out of a base must be the same. The second constraint represents a vehicle is only allowed to depart and arrive at a base once per refueling cycle.
The remaining constraints represent the conditions on the serviced, unserviced, and “excessively serviced” demands. To solve the either-or constraint, the two binary decision variables, y and z, and two sufficiently large positive constants (M) are used.
Figure 4 depicts example proportions of demand types within different demand sites. Here, the “type” of demand is a categorial measure for urgency of medical attention.
Figure 5 illustrates a single demand site with different demand types, each with serviced, unserviced and excessively served demands. The purpose of these constraints is to assign the excessive service to the next underserviced category. In this example the excessively serviced portion of demand type 2 would instead be used to service the unserviced portion of demand type 3.
Further constraints are also used to prevent redundant flight pathing of helicopters — as explored in The Vehicle Routing Problem by Paolo Toth and Daniele Vigo [4] — and to prioritize completing patients of a certain priority within their given time window before proceeding to the next priority group.
With this IP, Hoon Oh et al. provide a model in which the degree of injury is considered when saving lives. However, it ignores some crucial, practical features of disaster zones; for example, delivery sites, hospitals or temporary shelters would almost certainly have capacity constraints. Naturally, whether we transport a patient to a hospital or not, if the hospital cannot treat them, we have failed in our endeavor to save them. As a result, further research is essential, including potentially a multiobjective approach.
As a potential secondary objective, the capacity of delivery sites could be considered. In addition to minimizing the unserviced demand, we would also minimize the patients delivered to a site (proportional to its capacity). This way, the biobjective nondominated frontier would give us a clearer picture of not only how many patients are transported from danger zones, but also how many are then saved in hospitals — and, crucially, how many aren’t. This could give disaster responders information on how best to proceed instead of blindly transporting as many people as possible that meets fuel budgets, they instead invest excess resources to transport people to hospitals more sparsely: rather than overwhelming a few hospitals, this strategy would aim to transport patients to a treatment site with the space to service them.
Nevertheless, Hoon Oh et al. shows how optimization can be used to save lives in natural disasters while deadly catastrophes become more common in the face of global warming.
[1] https://news.sciencebrief.org/cyclones-mar2021/
[2] https://noaanhc.wordpress.com/2021/06/30/was-2020-a-record-breaking-hurricane-season-yes-but/
[3] https://pubsonline.informs.org/doi/pdf/10.1287/opre.1100.0881
