Abstract
In a network where nodes represent cities and edges represent roads connecting cities, we consider a set of possible disasters that destroy passageways between cities and render areas in need of emergency supplies. Relief must be provided to affected nodes from a set of facilities that are to be placed at a subset of candidate cities. This general problem statement applies in several situations. Natural disasters such as earthquakes and tornados not only leave certain areas in need of emergency supplies, but also destroy roads, making them impassable. Refugee crises require emergency ad hoc shelter construction but also have limited accessibility due to political or military interventions. Thus, emergency supplies can include food and water, shelter, rescue, or medical aid depending on the situation examined. Our research focuses on the optimal placement of relief locations such that in the case of a disaster affected areas are supplied with aid in the shortest amount of time, incurring the smallest cost possible. Each arc in the network has two components associated with it: a capacity (i.e. maximum number of units of flow that can be transported across it) and a cost of travel that is defined in terms of time per unit of flow. There is a fixed cost of establishing a facility at any candidate city. A discrete number of failure scenarios can arise, each with some probability of occurrence, such that the sum of the scenario probabilities adds up to one. A failure scenario consists of any combination of failed arcs and affected nodes. Affected nodes require emergency aid from facilities. It is also possible for nodes that serve as relief locations to be affected by failure scenarios. Failed arcs are considered to be passable, but utilizing them incurs a larger travel time. The costs incurred in the model are due to establishing facilities and the expected time required to provide relief to affected areas. For a given scenario, if the placement of facilities is known in advance, we are faced with a network flow problem that can be solved efficiently. We use the Benders' Decomposition strategy in order to take advantage of this special structure. This involves two stages. In the first stage the Master Problem (MP) is solved by determining a candidate set of facility locations. This solution is then fed into the second-stage subproblems, each representing a possible scenario, which determines the optimal routing of products from the relief facilities to the affected areas. This information is passed back to the MP, which is resolved according to the traditional Benders' framework. We evaluate the computational efficacy of our model as solved by standard integer programming formulations versus decomposition methodologies. There are several challenges involved when using the Benders' Decomposition principle. Do we aggregate the cuts generated by subproblems, or do we add them to the master problem one at a time? For large problem instances, how quickly will the decomposition strategy converge to the optimal solution? How can the process be accelerated? We close by discussing an earthquake relief problem in Turkey. We illustrate our methodology using real Turkish economic and fault line analyses, and illustrate how different modeling paradigms yield competing options for earthquake asset propositioning.
Original language | English (US) |
---|---|
Pages | 1119 |
Number of pages | 1 |
State | Published - 2004 |
Externally published | Yes |
Event | IIE Annual Conference and Exhibition 2004 - Houston, TX, United States Duration: May 15 2004 → May 19 2004 |
Conference
Conference | IIE Annual Conference and Exhibition 2004 |
---|---|
Country/Territory | United States |
City | Houston, TX |
Period | 5/15/04 → 5/19/04 |
Keywords
- Decomposition
- Disaster relief
- Facility location
- Integer programming
ASJC Scopus subject areas
- General Engineering