Benchmarking General-Purpose Metaheuristics for Shortest-Path and Maximum-Flow Network Interdiction: Effects of Network Topology and Size

Abstract

This study compares three general-purpose metaheuristics (a genetic algorithm, an elitist evolution strategy, and simulated annealing) for deterministic shortest-path and maximum-flow network interdiction problems. All methods use the same row-wise binary arc encoding, cardinality repair, partial-interdiction model, and exact lower-level network evaluator; they differ in search mechanism through tournament selection and row-wise crossover in GA, mutation-only elitist population search in ES, and a bit-flip neighbourhood with rational cooling in SA. The benchmark comprises 180 synthetic instances spanning Erdős–Rényi, Voronoi, and layered graphs at three nominal sizes (50, 100, and 200 vertices), with 30 independent runs and 10,000 objective evaluations per run. GA obtained the lowest final Friedman rank in 16 of 18 conditions and the best early-search rank in all conditions, while ES and SA became best on the largest layered shortest-path and maximum-flow instances, respectively. To calibrate absolute solution quality, shortest-path Benders/dual reformulations and maximum-flow min-cut dual reconstruction were used to certify all nominal-50 instances and additional layered maximum-flow instances. The certificates show that empirical best-known references can be exact on structured instances but remain substantially suboptimal on other topologies. The results support topology-aware heuristic selection within the tested configurations while emphasizing the complementary roles of exact certification and formulation-light metaheuristic search.