TY - GEN
T1 - Multi-objective network interdiction using evolutionary algorithms
AU - Rocco, Claudio M.
AU - Salazar, Daniel E.
AU - Ramirez-Marquez, Jose E.
PY - 2009
Y1 - 2009
N2 - The deterministic network interdiction problem (DNIP) is a classical problem in network optimization. In the traditional single objective (SO) approach, the basic idea is to select the network links that should be interdicted so that the maximum flow between source and sink nodes is minimized while the interdiction cost is constrained by the allocated budget. This paper considers the multiple-objective DNIP (MO- DNIP) where several objectives are optimized simultaneously in order to determine the efficient or Pareto frontier which provides valuable trade-off information to the Decision-Maker (DM). For example, the DM can select a strategy with higher flow interdicted and higher cost or a design with lower cost sacrificing flow interdiction. The possibility of the network being restored by its users is also considered in a three objective model where the restoration speed is to be minimized in order to ensure durability of the interdiction. The MO-DNIP is solved by Multiple-Objective Evolutionary Algorithms (MOEA), a family of Evolutionary Algorithms tailored to efficiently solve constrained multi- objective optimization models. A common characteristic among EA is that they do not rely on any mathematical prerequisites and can be applied, in principle, to any function or constraint. As with any heuristic, this approach does not guarantee the determination of the exact Pareto frontier but an important number of comparisons performed in Evolutionary Multiple-Criterion Optimization (EMO) on benchmark problems have shown that results are very close to the exact solution. The advantages of using multiple-objective formulations supported by MOEA are illustrated by solving problems taken from the literature.
AB - The deterministic network interdiction problem (DNIP) is a classical problem in network optimization. In the traditional single objective (SO) approach, the basic idea is to select the network links that should be interdicted so that the maximum flow between source and sink nodes is minimized while the interdiction cost is constrained by the allocated budget. This paper considers the multiple-objective DNIP (MO- DNIP) where several objectives are optimized simultaneously in order to determine the efficient or Pareto frontier which provides valuable trade-off information to the Decision-Maker (DM). For example, the DM can select a strategy with higher flow interdicted and higher cost or a design with lower cost sacrificing flow interdiction. The possibility of the network being restored by its users is also considered in a three objective model where the restoration speed is to be minimized in order to ensure durability of the interdiction. The MO-DNIP is solved by Multiple-Objective Evolutionary Algorithms (MOEA), a family of Evolutionary Algorithms tailored to efficiently solve constrained multi- objective optimization models. A common characteristic among EA is that they do not rely on any mathematical prerequisites and can be applied, in principle, to any function or constraint. As with any heuristic, this approach does not guarantee the determination of the exact Pareto frontier but an important number of comparisons performed in Evolutionary Multiple-Criterion Optimization (EMO) on benchmark problems have shown that results are very close to the exact solution. The advantages of using multiple-objective formulations supported by MOEA are illustrated by solving problems taken from the literature.
KW - MOEA
KW - Multi-objective optimization
KW - Network interdiction
KW - Resource allocation
UR - http://www.scopus.com/inward/record.url?scp=70349147425&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=70349147425&partnerID=8YFLogxK
U2 - 10.1109/RAMS.2009.4914670
DO - 10.1109/RAMS.2009.4914670
M3 - Conference contribution
AN - SCOPUS:70349147425
SN - 9781424425099
T3 - Proceedings - Annual Reliability and Maintainability Symposium
SP - 170
EP - 175
BT - 2009 Proceedings - Annual Reliability and Maintainability Symposium, RAMS 2009
T2 - 2009 - Annual Reliability and Maintainability Symposium, RAMS 2009
Y2 - 26 January 2009 through 29 January 2009
ER -