A single facility location problem on a tree with unreliable edges

This paper addresses the problem of determining a single facility location on an undirected tree with n nodes and edges that fail independently with probability (1 - p(e)) so that service provided to demand points can be achieved with reliability. Termed the relisum problem, the objective is to find a network location that maximizes the expected number of nodes reachable by operational paths. A decomposition formula is developed for which several properties are analytically derived and realistic vertex optimality conditions are identified. Two polynomial algorithms are presented: an O(n(3)) algorithm which is an adaptation of the Floyd-Warshall algorithm for finding all pairwise shortest paths in a graph and an O(n(2)) algorithm based on a depth-first node traversal and the decomposition nature of an operational path. Computational results are provided, and sensitivity analysis ranges and marginal values for p, are analytically derived. Properties and algorithms for the weighted version of the problem are discussed, as well as a polynomial heuristic for finding a relisum node on a cyclic network. (C) 1996 John Wiley & Sons, Inc.