Multi-objective network interdiction using evolutionary algorithms

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.