Algorithm for Determining Path of Maximum Reliability on a Network Subject to Random Arc Connectivity Failures. Issue 1 (January 2014)

• Record Type: Journal Article
• Authors: Seshadri, Ravi; Srinivasan, Karthik K.
• Is Part Of: Transportation research record. Volume 2467:Issue 1(2014)
• Page Start: 80
• Page End: 90
• Publication Date: 2014-01
• Subjects: Transportation -- Periodicals; Roads; Transport -- Périodiques; Routes -- Périodiques; Routes -- Conception et construction -- Périodiques; Roads; Transportation; 388.05
• DOI: 10.3141/2467-09
• Languages: English
• ISSNs: 0361-1981

Abstract

Several types of infrastructure networks such as transportation, utility, and pipeline systems may be subject to severe damage from exposure to human-caused and natural disasters (hurricanes, floods, earthquakes, etc.). Assessing the capability of a transportation network to provide basic functionality following catastrophic events involves estimating whether adequate connectivity can be ensured. In that context, this paper addresses the problem of identifying the path of maximum connectivity reliability between a pair of origin and destination nodes on a network subject to random and correlated arc connectivity failures. In view of the failure of the subpath optimality property for this maximum connectivity reliability problem, a reliability bounds–based sufficient condition for optimality is established. Based on this principle, a proposed algorithm estimates the reliability bounds by means of a candidate path set computed by using an efficient K shortest path algorithm. In the absence of convergence of the reliability bounds, an iterative gap reduction procedure is proposed to combine Monte Carlo simulation and network optimization to improve the lower bound by generating additional candidate paths. The proposed gap reduction and reliability evaluation procedures use a stochastic decomposition of the link failure propensity to improve computational efficiency. Empirical experiments on realistically sized synthetic networks show the proposed algorithm to be efficient and requiring limited path enumeration, and the experiments underscore the importance of modeling the correlations in link failures.