A hybrid modified-NSGA-II VNS algorithm for the Multi-Objective Critical Disruption Path Problem

This paper considers a Multiple Objective variant of the Critical Disruption Path problem to extend itssuitability in a range of security operations relying on path-based network interdiction, including flight patternoptimisation for surveillance. Given a pair of nodes s and t from the network to be monitored, the problemseeks for loopless s - t paths such that, within the induced subgraph obtained via deletion of the path, thesize 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 arepossibly in conflict with each other, and the scope of this work is to allow for an efficient and insightfulapproximation of the Pareto front, looking for a trade-off between costs and effectiveness to secure the mostconvenient paths for security and surveillance operations. We first introduce and formulate the Multi-ObjectiveCritical 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 forfinding an approximation of the Pareto front, as well as a procedure securing the efficient generation of a highquality pool of initial solutions. The experimental performance of the proposed algorithm, as compared witha variety of competing approaches, proves to be fully satisfactory in terms of time efficiency and quality ofthe solutions obtained on a set of medium to large benchmark instances.