 Optimal Patrol on a Graph Against Random and Strategic AttackersRichard G. McGrath ()
A chapter in Optimization Problems in Graph Theory, 2018, pp 215-263 from Springer Abstract: Abstract We present a patrol problem where several patrollers move between locations dispersed throughout an area of interest in order to detect enemy attacks. To formulate an effective patrol policy, the patrollers must take into account travel time between locations, as well as location-specific parameters, which include patroller inspection times, enemy attack times, and cost incurred due to an undetected attack. We consider both random and strategic attackers. A random attacker chooses a location to attack according to a probability distribution, while a strategic attacker plays a two-person zero-sum game with the patrollers. We model the area of interest on a graph and, in some cases, can compute an optimal patrol solution using linear programming. This method, however, becomes computationally intractable as the problem size grows. Therefore, we present efficient heuristics, based on aggregate index values, fictitious play, and shortest paths. Numerical experiments using the heuristic methods produce excellent results on several graph sizes and structures, with computation time orders of magnitude less than what is required to compute an optimal solution. Date: 2018 There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it. Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:spr:spochp:978-3-319-94830-0_10 Ordering information: This item can be ordered from DOI: 10.1007/978-3-319-94830-0_10 Access Statistics for this chapter More chapters in Springer Optimization and Its Applications from Springer |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.