Stochastic shortest path network interdiction with a case study of Arizona–Mexico border

One of the key challenges in securing the U.S.-Mexico border is the smuggling of illicit goods and humans between Ports-of-Entry (POEs). A confluence of factors advantageous to traffickers including inconsistent levels of fencing, favorable terrain, and expansive knowledge of specific pathways have contributed to the establishment of preferred routes of illicit transit, yet little is known about the strategic interaction between adversaries and defenders between the POEs. To address this challenge, this paper studies a stochastic shortest-path network interdiction problem where the attacker (drug smugglers, illegal immigrants, or terrorists) attempts to minimize the expected shortest traveling time between the source and the destination, while the defender attempts to maximize the attacker’s expected shortest traveling time by allocating sensors to the arcs to detect the attacker with a limited budget. Using a probabilistic detection likelihood, we formulate bi-level max-min mixed-integer problems on a multi-modal licit and illicit transportation network along the Arizona–Mexico border considering single source and single destination, and multiple sources and multiple destinations, respectively. We find that (a) the expected shortest traveling time will increase as the budget/detection probability increase; (b) the expected shortest time by walking is more than 3 times long than by driving; (c) the multiple sources and multiple destinations model which allows the attacker to choose a random source-destination pair leads to a shorter time than the single source and single destination model. A graphical user interface (GUI) is developed to assist decision making and demonstrate the results.