Book Description

Effective restoration of infrastructure systems play a crucial role in recovery after disasters. Understanding the functions and services of infrastructure systems, especially during the response to natural and man-made disasters, requires accounting for the interdependencies and decentralized nature of these systems. This issue is particularly critical when delivering time-sensitive services and commodities. We model the recovery of infrastructure systems by including interdependencies between them as network models, and we present three integer programming models. First, we present an integrated restoration and location (IRLP) problem, which is a P-median problem variation, with the objective to minimize the cumulative weighted distance between the emergency responders and the calls for service over the time horizon by coordinating the activities of two types of service providers. We locate emergency responders (facilities) on a network over a finite time horizon while network recovery crews install arcs. The installation part of the problem is modeled as a scheduling problem with identical parallel servers (the repair crews), where an arc can be used by the emergency responders when installation is completed. We propose Lagrangian relaxation formulations of the problem, which we solve using subgradient algorithm. A feasible solution is obtained using the Lagrangian relaxation, which provides an upper bound to the original problem. We test our problem with both real-world data and data sets from Beasley's OR Library to demonstrate the effectiveness of the algorithm in solving large-scale problem. The results shed light on critical components of a network whose restoration can aid emergency response efforts. Second, we present a maximal multiple coverage and network recovery problem for the recovery and restoration of infrastructure systems after disasters. In the model, recovery crews make damaged arcs available by repairing components over a time horizon in a disrupted network. The model relocates emergency responders using the available arcs in the network to maximize multiple coverage of emergency service demand over the time horizon. We present two heuristics for the model. The first uses the Lagrangian and the linear programming relaxation solutions of the problem, and the second uses an integer rounding procedure applied to the linear programming relaxation solution. We test the model using a real-world example representing the road infrastructure and emergency services of the Bronx Borough in New York, NY during Hurricane Sandy. Our computational study suggests that our model can aid emergency managers in achieving their goals by scheduling effective restoration activities for real-time disaster recovery and long-term recovery planning. The results show that the heuristics and algorithms are effective for solving large--scale problem instances. Third, we model the recovery of interdependent infrastructure systems after disasters as a non-cooperative game in a two-layer network, each belongs to a player. The goal of the model is to plan short term recovery of infrastructure systems after a disaster in which each player wants to minimize the cost to satisfy their own demand. For comparison, we present a centralized model, where a central decision maker controls the restoration decisions of both players. The central decision maker plays a role as an authority/third player in the game and splits the recovery budget to each player according to the social welfare solution, which is the optimal solution of the centralized model. In addition, the central decision maker provides incentives to players to motivate them for collaboration in the non-cooperative game. A mechanism is proposed to decide incentives using an inverse optimization method and the inverse optimization mechanism is compared with another mechanism based on an [alpha]-approximation algorithm to decide the fees for using inter-edges. The goal of the mechanisms is to set incentives so that a pure Nash equilibrium aligns with the social welfare solution. We compare the Nash equilibria in which players use fees obtained from the mechanisms. We prove that with the inverse optimization method fees, the centralized optimal solution value becomes a pure Nash equilibrium, and with the [alpha]-approximation algorithm fees, the centralized model optimal solution value becomes an [alpha]-approximate pure Nash equilibrium in the facility location and restoration games. We use the potential function method to analyze the efficiency of the game using the Price of Stability (PoS). We present a case study in which we consider the recovery efforts of telecommunication infrastructure companies and provide results for the facility location and restoration games.