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

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.