Abstract
This paper considers a Multiple Objective variant of the Critical Disruption Path problem to extend its
suitability in a range of security operations relying on path-based network interdiction, including flight pattern
optimisation for surveillance. Given a pair of nodes s and t from the network to be monitored, the problem
seeks for loopless s - t paths such that, within the induced subgraph obtained via deletion of the path, the
size of the largest connected component is minimised, the number of connected components is maximised,
while concurrently reducing as much as possible the cost of such disruption path. These three objectives are
possibly in conflict with each other, and the scope of this work is to allow for an efficient and insightful
approximation of the Pareto front, looking for a trade-off between costs and effectiveness to secure the most
convenient paths for security and surveillance operations. We first introduce and formulate the Multi-Objective
Critical Disruption Path Problem (Multi-Objs-CDP) as a mixed integer programming formulation (MO-CDP),
then we propose an original evolutionary metaheuristic algorithm hybridising modified-NSGA-II and VNS for
finding an approximation of the Pareto front, as well as a procedure securing the efficient generation of a high
quality pool of initial solutions. The experimental performance of the proposed algorithm, as compared with
a variety of competing approaches, proves to be fully satisfactory in terms of time efficiency and quality of
the solutions obtained on a set of medium to large benchmark instances.
Anno
2023
Autori IAC
Tipo pubblicazione
Altri Autori
Granata, Donatella and Sgalambro, Antonino
Editore
Pergamon,
Rivista
Computers & operations research