The weighted intruder path covering problem

Effectively detecting and interdicting intruders within a defender’s territory is a common security problem. Often, the defender’s territory is decomposed into spatially distinct stages for organizational convenience. Given an intruder attempting to traverse a spatially-decomposed region via multiple possible paths, this research aims to effectively and cost-efficiently identify a defensive strategy that locates sets of detection resources and interdiction resources, each of which has different types of resources that vary by cost and capability. We formulate and validate a mixed-integer nonlinear programming model to solve the underlying problem first using a leading commercial solver (BARON) and then via two genetic algorithms (RWGA and NSGA-II). Computational testing first identifies instance size limitations for identifying a global optimal solution via BARON, motivating the use of metaheuristics. Subsequent testing demonstrates the superior performance of RWGA and NSGA-II on 10 randomly generated instances for each of 20 various instance sizes. For each 20 of these instance sizes, both RWGA and NSGA-II produce higher-quality and more non-dominated solutions than BARON while using much less computational effort. Subsequent testing of only RWGA and NSGA-II over a designed set of test instances identifies NSGA-II as the recommended technique to solve larger-sized instances of the underlying problem.