Humanitarian relief supply network design: Expander graph based approach and a case study of 2013 Flood in Northeast China. (February 2021)

• Record Type: Journal Article
• Authors: Shu, Jia; Lv, Wenya; Na, Qing
• Is Part Of: Transportation research. Volume 146(2021)
• Publication Date: 2021-02
• Subjects: Disaster operations management -- Emergency facility location -- Relief supply pre-positioning -- Expander graph; Logistics -- Periodicals; Transportation -- Periodicals; 388.011
• DOI: 10.1016/j.tre.2020.102178
• Languages: English
• ISSNs: 1366-5545

Abstract

Highlights: A model is presented to design a Ψ -expander based humanitarian relief supply network. We implement the model using a case study of 2013 Flood in Northeast China. We analyze the complexity of the separation problem and prove that it is NP-hard. We outline a cutting-plane approach to solve the model with Ψ-expander constraints. Abstract: The frequent occurrence and catastrophic consequence of natural disasters have made it important to design an appropriate humanitarian relief supply network that can provide (cost-) effective and timely rescue for affected people. This paper presents a humanitarian relief supply network design model for large-scale natural disasters such as flood and hurricane. The model is constructed through the adoption of a Ψ -expander structure which is a variant of expander graph and a sparse yet highly connected structure with good flexibility. The Ψ -expander structure guarantees that either the network can satisfy the total demand among affected areas or utilize at least Ψ proportion of the total pre-positioned relief supply. The model optimizes the decisions of emergency facility location and relief supply pre-positioning simultaneously under uncertain demand in each affected area. The objective is to minimize the total cost of fixed location and relief supply pre-positioning. The model is cast as a nonlinear integer program with an exponential size of the Ψ -expander constraints. We address it using a cutting-plane approach. We also analyze the complexity of the separation problem that must be solved in each iteration of the cutting-plane approach and prove that it is NP-hard. A case study based on the 2013 Flood in Northeast China is presented to verify the performance of the model. Computational results demonstrate that the model is able to design a humanitarian relief supply network with a high demand fill rate effectively.