Premium
A single facility location problem on a tree with unreliable edges
Author(s) -
Melachrinoudis Emanuel,
Helander Mary E.
Publication year - 1996
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199605)27:3<219::aid-net7>3.0.co;2-l
Subject(s) - tree traversal , node (physics) , shortest path problem , vertex (graph theory) , mathematics , pairwise comparison , mathematical optimization , computer science , undirected graph , algorithm , tree (set theory) , facility location problem , graph , combinatorics , structural engineering , engineering , statistics
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 e 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. © 1996 John Wiley & Sons, Inc.