A bi-objective approach for shortest-path network interdiction

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

Research output: Contribution to journalArticlepeer-review

58 Scopus citations

Abstract

In the literature, solution approaches to the shortest-path network interdiction problem have been developed for optimizing a single figure-of-merit of the network configuration when considering limited amount of resources available to interdict network links. This paper presents a newly developed evolutionary algorithm that allows approximating the optimal Pareto set of network interdiction strategies when considering bi-objective shortest path problems. Thus, the paper considers the concurrent optimization of two objectives: (1) maximization of shortest-path length and (2) minimization of interdiction strategy cost. Also, the paper considers the transformation of the first objective into the minimization of the most reliable path reliability. To solve these multi-objective optimization problems, an evolutionary algorithm has been developed. This algorithm is based on Monte Carlo simulation, to generate potential network interdiction strategies, graph theory to analyze strategies' shortest path or most reliable path and, an evolutionary search driven by the probability that a link will appear in the optimal Pareto set. Examples for different sizes of networks and network behavior are used throughout the paper to illustrate and validate the approach.

Original languageEnglish
Pages (from-to)232-240
Number of pages9
JournalComputers and Industrial Engineering
Volume59
Issue number2
DOIs
StatePublished - Sep 2010

Keywords

  • Evolutionary
  • Multi-objective
  • Network interdiction
  • Optimization
  • Reliability

Fingerprint

Dive into the research topics of 'A bi-objective approach for shortest-path network interdiction'. Together they form a unique fingerprint.

Cite this