Simple algorithms for updating multi-resource allocations in an unreliable flow network

In this paper, algorithms are developed to update the reliability-maximizing resource allocation in an unreliable flow network when either resource demand or the characteristic of the flow network changes. An unreliable flow network consists of nodes, characterized as source nodes, which supply resources of various types, sink nodes, at which resource demand takes place, and intermediate nodes, as well as unreliable directed arcs, which join pairs of nodes and whose capacities have multiple operational states. The network reliability of such an unreliable flow network is the probability that resources can be transmitted successfully from source nodes to sink nodes. With earlier developments on evaluating network reliability and resolving reliability-maximizing resource allocation problems in an unreliable flow network, one may recompute a new resource allocation strategy, when either resource demand or the characteristic of the flow network changes, without incorporating the efforts that have been made in obtaining the existing resource allocation. This study, in contrast, proposes updating, rather than recomputing, alternatives that take advantage of existing minimal path vectors and corresponding flow patterns. Procedural comparisons and numerical examples indicate that the updating schemes would perform better than the recomputing scheme in a large-sized flow network that transmits various resource types.