An integrated network design and scheduling problem for network recovery and emergency response

Abstract

Effective recovery and restoration of infrastructure systems play a crucial role in recovery after disasters. This issue is particularly critical when delivering time-sensitive services and commodities. Damage to infrastructure can lead to disruptions and diminished capacity to respond to emergencies. We model the interdependencies between infrastructure systems and service providers as a network model, where emergency responders deliver critical services while network recovery crews repair damage to critical infrastructure. We present a novel extension to the P-median problem, where the objective is 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 models 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 models, which we solve using subgradient optimization. A feasible solution is obtained using the Lagrangian relaxation, which provides an upper bound to the original models. We test our models with both real-world data and data sets from Beasley’s OR Library to demonstrate the effectiveness of the algorithm in solving large-scale models. The results give insight into the optimal schedule for restoring critical arcs in a network when delivering critical services and commodities after a disruptive event. Keywords: OR in disaster relief, P-median problem, Network restoration, Scheduling on parallel servers, Emergency response