Multi-objective bilevel programming model for optimizing network interdiction deployment

doi:10.1016/j.swevo.2025.102265

2025-12-01

PRE

Wei-Chang Yeh

Chyh-Ming Lai

Tsung-Hua Wu *

DOI：10.1016/j.swevo.2025.102265

原文链接

原文求助

摘要

En 中文

This study introduces a multi-objective bilevel programming model to address the ground force interdiction deployment problem, which is a hierarchical optimization framework where the defender strategically allocates resources to disrupt the attacker's operational routes under resource constraints. At the upper level, the defender seeks to minimize interdiction costs while maximizing disruption to the attacker's most reliable and shortest invasion paths. At the lower level, the attacker responds by minimizing the length of its invasion path and maximizing its reliability. To solve this problem, a novel nested multi-objective evolutionary algorithm, termed iNSSSO, is proposed. The algorithm integrates nondominated sorting simplified swarm optimization to optimize the defender's interdiction strategy at the upper level and Bi-Objective A* to solve the attacker's bi-objective pathfinding problem at the lower level. To further improve solution quality and diversity, the algorithm incorporates dynamic reliability thresholding and min-cut search mechanisms. Experimental validation on 36 test instances demonstrates that iNSSSO consistently outperforms state-of-the-art algorithms, including MOPSDA, NSGA-II, SPEA2, NSGA-III, MOEA/D, and NSSSO, in terms of solution quality, diversity, and convergence. Furthermore, a practical analysis identifies critical network bottlenecks and frequently interdicted edges, offering valuable insights for resource allocation and defensive strategy planning in network interdiction scenarios.

Keyword:

Multi-objective optimization problem

Network interdiction problem

Bilevel programming

Simplified swarm optimization

Bi-Objective A* algorithm