A Graph Patrol Problem with Random Attack Times

Kyle Y. Lin (), Michael P. Atkinson (), Timothy H. Chung () and Kevin D. Glazebrook ()
Additional contact information
Kyle Y. Lin: Operations Research Department, Naval Postgraduate School, Monterey, California 93943
Michael P. Atkinson: Operations Research Department, Naval Postgraduate School, Monterey, California 93943
Timothy H. Chung: Systems Engineering Department, Naval Postgraduate School, Monterey, California 93943
Kevin D. Glazebrook: Department of Management Science, Lancaster University Management School, Lancaster LA1 4YX, United Kingdom

Operations Research, 2013, vol. 61, issue 3, 694-710

Abstract: This paper presents a patrol problem, where a patroller traverses a graph through edges to detect potential attacks at nodes. To design a patrol policy, the patroller needs to take into account not only the graph structure, but also the different attack time distributions, as well as different costs incurred due to successful attacks, at different nodes. We consider both random attackers and strategic attackers. A random attacker chooses which node to attack according to a probability distribution known to the patroller. A strategic attacker plays a two-person zero-sum game with the patroller. For each case, we give an exact linear program to compute the optimal solution. Because the linear programs quickly become computationally intractable as the problem size grows, we develop index-based heuristics. In the random-attacker case, our heuristic is optimal when there are two nodes, and in a suitably chosen asymptotic regime. In the strategic-attacker case, our heuristic is optimal when there are two nodes if the attack times are deterministic taking integer values. In our numerical experiments, our heuristic typically achieves within 1% of optimality with computation time orders of magnitude less than what is required to compute the optimal policy.

Keywords: military; search/surveillance; dynamic programming/optimal control; game/group decisions (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (13)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1120.1149 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:61:y:2013:i:3:p:694-710

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().