Assessing the effectiveness of k-shortest path sets in problems of network interdiction

This paper focuses on the network interdiction problem and integration of a solution methodology based on k-shortest path sets. We design and conduct an experiment using the road network of Northridge, California to assess performance of the k-shortest path approach under varying assumptions which include homogeneous and heterogeneous arc metrics, the use or non-use of pseudo nodes and alternate origin-destination scenarios. We compare the obtained solutions from the k-shortest path set approach to optimal solutions obtained by implementing Benders Decomposition and observe the differences in computation time and the objective gap for all cases of the experimental design. We also introduce a similarity measure based on spatial analysis techniques to compare coverage as a secondary measure of performance. The observed findings support the use of a k-shortest path set approach in situations where computation time prohibits the need to derive an optimal solution. Additionally, we show that the k-shortest path set approach performs better on heterogeneous networks and that only a small number need be used for k to achieve strong interdiction solutions.