Security routing games with multivehicle Chinese postman problem
Security routing games with multivehicle Chinese postman problem
复制标题
多车辆中国邮递员问题的安全路由博弈
作者：
D. Hochbaum;Cheng Lyu;F. Ordóñez
威慑和防止核恐怖主义的努力的关键是有能力在特定地区发现可能存在的核威胁。能够检测这种威胁的资源是有限的、昂贵的，并且只能在给定的时间量内扫描特定的整个区域。由于探测核威胁的能力受到限制，因此必须制定有效的探测资源部署战略。在这项工作中，我们提出了一个基于Stackelberg博弈的模型，以确定当战略对手试图在网络边缘放置核威胁时，网络上安全资产的最优巡逻策略。为了有效地求解这个模型，我们引入了一种新的问题分解，该问题需要解决一个多车辆中国农村邮递员问题(CPP)。我们的理论贡献给出了k车农村CPP的困难和近似结果。我们的计算结果证明了这种分解对于核威胁检测安全问题的好处。《威利期刊网络》2014年第3卷第181-191期
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. © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 64(3), 181–191 2014