A Robust Model for the Network Violator Interception Problem

This paper studies planning interceptor locations in a general transportation network to maximize the benefits of reducing public exposure to violators (e.g., violators in urban transportation networks and terrorists in airline networks). A robust optimization model is proposed to address uncertainties associated with link traffic volumes and the likelihood of having a violator on a particular network route. The potential failure of interceptors and subsequent uncertainties is also considered. The consequent mathematical model has a bi-level program structure and a non-convex inner problem. We propose a number of solution approaches, including the alternating ascent algorithm, convex relaxation, duality techniques and commercial solvers for the inner problem, and greedy randomized adaptive search program (GRASP) algorithms for the outer problem. Several numerical experiments are conducted to illustrate the computational efficiency and solution quality of the proposed algorithms.