Fortifying Distribution Network Nodes Subject to Network-Based Disruptions

We consider a distribution network for delivering a natural resource or physical good to a set of nodes, each of which serves a set of customers, in which disruptions may occur at one or more nodes. Each node receives flow through a path from a source node, implying that the service at a node is interrupted if one or more nodes on the path from a source node experience a disruption. All network nodes are vulnerable to a future disturbance due to a potential natural or man-made disaster, the severity of which follows some measurable probability distribution. For each node in the network, we wish to determine a fortification level that enables the node to withstand a disturbance up to a given severity level, while minimizing the expected number of customers who experience a service interruption under a limited fortification budget. We formulate this problem as a continuous, nonlinear knapsack problem with precedence constraints, demonstrate that this optimization problem is $\mathcal{NP}$-Hard for general tree networks and general disturbance severity distributions, and provide a polynomial-time solution algorithm for serial systems, which forms the basis for an effective heuristic approach to problems on tree networks. Our computational test results demonstrate the ability of the proposed heuristic methods to quickly find near-optimal solutions.