Stochastic network interdiction optimization via capacitated network reliability modeling and probabilistic solution discovery

José Emmanuel Ramirez-Marquez, Claudio M. Rocco S.

    Research output: Contribution to journalArticlepeer-review

    75 Scopus citations

    Abstract

    This paper introduces an evolutionary optimization approach that can be readily applied to solve stochastic network interdiction problems (SNIP). The network interdiction problem solved considers the minimization of the cost associated with an interdiction strategy such that the maximum flow that can be transmitted between a source node and a sink node for a fixed network design is greater than or equal to a given reliability requirement. Furthermore, the model assumes that the nominal capacity of each network link and the cost associated with their interdiction can change from link to link and that such interdiction has a probability of being successful. This version of the SNIP is for the first time modeled as a capacitated network reliability problem allowing for the implementation of computation and solution techniques previously unavailable. The solution process is based on an evolutionary algorithm that implements: (1) Monte-Carlo simulation, to generate potential network interdiction strategies, (2) capacitated network reliability techniques to analyze strategies' source-sink flow reliability and, (3) an evolutionary optimization technique to define, in probabilistic terms, how likely a link is to appear in the final interdiction strategy. Examples for different sizes of networks are used throughout the paper to illustrate the approach.

    Original languageEnglish
    Pages (from-to)913-921
    Number of pages9
    JournalReliability Engineering and System Safety
    Volume94
    Issue number5
    DOIs
    StatePublished - May 2009

    Keywords

    • Capacitated reliability
    • Network interdiction
    • Solution discovery optimization

    Fingerprint

    Dive into the research topics of 'Stochastic network interdiction optimization via capacitated network reliability modeling and probabilistic solution discovery'. Together they form a unique fingerprint.

    Cite this