TY - JOUR
T1 - Bi and tri-objective optimization in the deterministic network interdiction problem
AU - Rocco S., Claudio M.
AU - Emmanuel Ramirez-Marquez, José
AU - Salazar A., Daniel E.
PY - 2010/8
Y1 - 2010/8
N2 - Solution approaches to the deterministic network interdiction problem have previously been developed for optimizing a single figure-of-merit of the network configuration (i.e. flow that can be transmitted between a source node and a sink node for a fixed network design) under constraints related to limited amount of resources available to interdict network links. These approaches work under the assumption that: (1) nominal capacity of each link is completely reduced when interdicted and (2) there is a single criterion to optimize. This paper presents a newly developed evolutionary algorithm that for the first time allows solving multi-objective optimization models for the design of network interdiction strategies that take into account a variety of figures-of-merit. The algorithm provides an approximation to the optimal Pareto frontier using: (a) techniques in Monte Carlo simulation to generate potential network interdiction strategies, (b) graph theory to analyze strategies' maximum source-sink flow and (c) an evolutionary search that is driven by the probability that a link will belong to the optimal Pareto set. Examples for different sizes of networks and network behavior are used throughout the paper to illustrate and validate the approach.
AB - Solution approaches to the deterministic network interdiction problem have previously been developed for optimizing a single figure-of-merit of the network configuration (i.e. flow that can be transmitted between a source node and a sink node for a fixed network design) under constraints related to limited amount of resources available to interdict network links. These approaches work under the assumption that: (1) nominal capacity of each link is completely reduced when interdicted and (2) there is a single criterion to optimize. This paper presents a newly developed evolutionary algorithm that for the first time allows solving multi-objective optimization models for the design of network interdiction strategies that take into account a variety of figures-of-merit. The algorithm provides an approximation to the optimal Pareto frontier using: (a) techniques in Monte Carlo simulation to generate potential network interdiction strategies, (b) graph theory to analyze strategies' maximum source-sink flow and (c) an evolutionary search that is driven by the probability that a link will belong to the optimal Pareto set. Examples for different sizes of networks and network behavior are used throughout the paper to illustrate and validate the approach.
KW - Evolutionary
KW - Interdiction
KW - Multi-objective
KW - Network
KW - Optimization
UR - http://www.scopus.com/inward/record.url?scp=79251610757&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79251610757&partnerID=8YFLogxK
U2 - 10.1016/j.ress.2010.03.008
DO - 10.1016/j.ress.2010.03.008
M3 - Article
AN - SCOPUS:79251610757
SN - 0951-8320
VL - 95
SP - 887
EP - 896
JO - Reliability Engineering and System Safety
JF - Reliability Engineering and System Safety
IS - 8
ER -