Security Routing Games with Multivehicle Chinese Postman Problem

Key in the efforts to deter and prevent nuclear terrorism is the ability to detect the presence of possible nuclear threats in a given area. Resources capable of detecting such threats are limited, expensive, and only capable of scanning a certain total area in a given amount of time. This limit on the ability to detect nuclear threats makes imperative the development of efficient deployment strategies of the detection resources. In this work, we propose a Stackelberg game-based model to determine the optimal patrolling strategy of security assets over a network in the presence of a strategic adversary that seeks to place a nuclear threat on edges of the network. To efficiently solve this model, we introduce a novel decomposition of the problem which requires the solution of a multivehicle rural Chinese postman problem (CPP). Our theoretical contributions present hardness and approximation results for the k-vehicle rural CPP. Our computational results demonstrate the benefit of this decomposition for the nuclear threat detection security problem. (c) 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 64(3), 181-191 2014