A length-based, multiple-resource formulation for shortest path network interdiction problems in the transportation sector

This paper analyzes a variation of the shortest path network interdiction problem for homeland security scenarios pertaining to attacks on critical infrastructure and key resources that use highways in the transportation sector as conduits for gaining proximity to targets. The model represents a static Stackelberg game and may be formulated as a bi-level mixed integer program with two players: an attacker and a defender. Using highway segments as arcs, a set of predetermined highway entry points and a target set, the attacker seeks the path of maximum non-detection between any entry and target node. The defender impacts the minimum value of this maximum non-detection path through the allocation of a limited number of defense sensors that reduce the non-detection probabilities for arcs that fall within the range of influence of a sensor. Two types of sensors, static and dynamic sensors, are available to the defender and separate influence functions model their respective effects on arc non-detection. A geographic information system is used to collect, store and process network information and sensor influence information stored in a relational database. The results of the problem formulation are analyzed in a case study involving a California highway sub-network. The case study also examines the effects of sensor parameters, budget levels and target sets on the solutions that are obtained.