A Greedy Scheduling of Post-Disaster Response and Restoration using Pressure-Driven Models and Graph Segment Analysis

A Greedy Scheduling of Post-Disaster Response and Restoration using Pressure-Driven Models and Graph Segment Analysis

Deuerlein, Jochen (3S Consult GmbH)
Gilbert, Denis (Irstea; Bordeaux Regional Centre)
Abraham, E. (TU Delft Water Resources)
Piller, Olivier (Irstea; Bordeaux Regional Centre)

2018-07-15

In this manuscript, we consider the problem of optimally scheduling the restoration of a water distribution network with multiple failures after a disaster. The decisions made are the sequence of burst/broken pipes and leaks that need to be replaced or repaired, respectively, subject to constraints on workforce availability and physical hydraulic conditions. In order to sufficiently capture the objectives of the utility (e.g. service levels, resilience loss and customer minutes lost without service), which are all pressure dependent, pressure driven leakage and demand models (PDM) are employed.
The restoration decisions are modelled as time-dependent closure and opening of links and are simulated using a PDM in EPANET, propagating decisions as pressure-driven hydraulic constraints and computing a posteriori their impact on the multiple desired restoration objectives, some of which have trade-offs. The combination of discrete decisions with time-dependent couplings, and the presence of objectives that are conditional functions of demands met and time indices make it difficult to pose this optimal task scheduling problem as a standard numerically tractable mixed-integer programming problem. To make the problem tractable for the given large-scale water distribution system, we propose greedy heuristics that use a hierarchical decomposition of the decision space using structural properties of the network graph and hydraulics. Firstly, PDM simulations are used to sort the breaks and leaks from the biggest losses to the smallest, or determine visibility of the damages. In addition to solving the multi-criteria scheduling problem, we also use engineering principles to derive metaheuristic that can prioritise water loss reductions. The greedy algorithm is employed to iteratively schedule isolation and repairs by first stabilizing the system with the isolation of the biggest breaks; an alternative approach considers all objectives ‘equally’. With these we explore the trade-offs in response between water loss and resilience indicators.
To enable the scheduling, we use graph decomposition techniques to identify the valves that need to be closed to isolate a hydraulic segment (i.e. set of links sharing same closing valves) for replacement; this gives us a map (or look up table) that will be used in the scheduling. The map also includes information about the number of nodes isolated, unsatisfied demand when isolating each segment and the total pipe length of the segments. We also analyse the system flows, network pressures and how the depletion of tanks affects service levels. Using these, we make recommendations for improving the capacity of the system, including the improvement of pumping stations, installation of control valves and some pipe re-enforcement. The same greedy task scheduling algorithm is then used under these alternative network improvements, to show a much better response in all criteria.

Disaster Response Scheduling
Graph Decomposition
greedy algorithms
Resilience
Pressure Driven Modelling

http://resolver.tudelft.nl/uuid:9d2335c8-29ef-4404-9628-3a6c54d766d2

WDSA / CCWI Joint Conference 2018, Vol 1 (2018)

1st International WDSA / CCWI 2018 Joint Conference, 2018-07-23 → 2018-07-25, Kingston, Canada

Institutional Repository

conference paper

© 2018 Jochen Deuerlein, Denis Gilbert, E. Abraham, Olivier Piller