Efficient Repair Scheduling Strategy of a Multi-Source Lifeline Network Using Constrained Spanning Forest

• Main Authors: Garciano, Lessandro Estelito, Garciano, Agnes, Tolentino, Mark Anthony C, Carandang, Abraham Matthew
• Format: text
• Published: Archīum Ateneo 2019
• Subjects: Water lifeline; Horn’s algorithm; Constrained spanning forest; Emergency and Disaster Management; Mathematics
• Online Access: https://archium.ateneo.edu/mathematics-faculty-pubs/55; https://www.geomatejournal.com/sites/default/files/articles/49-54-8201-Garciano-Nov-2019-63g.pdf
• Institution: Ateneo De Manila University

Pre-disaster programs, especially for seismic hazards, are necessary to quickly recover the services of a lifeline network. In the case of a multi-source (or multi-root) water lifeline network, an efficient repair schedule must be implemented immediately after an earthquake to assist in post-disaster activities as well as to minimize the subsequent health problems caused by the lack of potable water supply. As such water lifeline operators must establish restoration strategies especially if the supply of water comes from different sources and spatially distributed. For a single-source water network, Horn’s algorithm can be used to determine an optimal restoration strategy. However, a variation of this algorithm is necessary in order to allow simultaneous repairs at any given time for a multiple-source lifeline water network. In this research, the authors employ a constrained spanning forest (CSF) algorithm to decompose the network into trees rooted at each source. After the decomposition, Horn’s algorithm is used to determine the optimal restoration strategy for each tree in the network with the objective of minimizing a penalty value. Restoration of each node in the spanning forest is carried in sequence according to availability of the crew and allows simultaneous jobs to be done on consecutive arcs in the sequence.