Security routing games with multivehicle Chinese postman problem

Security routing games with multivehicle Chinese postman problem

0.00 Avg rating0 Votes
Article ID: iaor201522266
Volume: 64
Issue: 3
Start Page Number: 181
End Page Number: 191
Publication Date: Oct 2014
Journal: Networks
Authors: , ,
Keywords: game theory, networks, graphs, heuristics
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.