Multi-objective network interdiction using evolutionary algorithms

Claudio M. Rocco, Daniel E. Salazar, Jose E. Ramirez-Marquez

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

10 Scopus citations

Abstract

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.

Original languageEnglish
Title of host publication2009 Proceedings - Annual Reliability and Maintainability Symposium, RAMS 2009
Pages170-175
Number of pages6
DOIs
StatePublished - 2009
Event2009 - Annual Reliability and Maintainability Symposium, RAMS 2009 - Fort Worth, TX, United States
Duration: 26 Jan 200929 Jan 2009

Publication series

NameProceedings - Annual Reliability and Maintainability Symposium
ISSN (Print)0149-144X

Conference

Conference2009 - Annual Reliability and Maintainability Symposium, RAMS 2009
Country/TerritoryUnited States
CityFort Worth, TX
Period26/01/0929/01/09

Keywords

  • MOEA
  • Multi-objective optimization
  • Network interdiction
  • Resource allocation

Fingerprint

Dive into the research topics of 'Multi-objective network interdiction using evolutionary algorithms'. Together they form a unique fingerprint.

Cite this