EFFICIENT REPAIR SCHEDULING STRATEGY OF A MULTISOURCE LIFELINE NETWORK USING CONSTRAINED SPANNING FOREST

Abstract

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.