Urban Rail Patrolling: a Game Theoretic Approach

Patrol scheduling is a critical operational decision in protecting urban rail networks against terrorist activities. Designing patrols to protect such systems poses many challenges that have not been comprehensively addressed in the literature of patrol scheduling so far. These challenges include strategic attackers, dynamically changing station occupancy levels and human resource related limitations. In this paper, the authors develop a game theoretic model for the problem of scheduling security teams to patrol an urban mass transit rail network. The main objective is to minimize the expected potential damage caused by terrorist activities while observing scheduling constraints. The authors model this problem as a non-cooperative simultaneous move game between a defender and an attacker. They then develop column generation based algorithms to find a Nash equilibrium for this game. They also present a lower bound for the value of the game which can be used to terminate the column generation algorithm when a desired solution quality is reached. The authors then run computational experiments to investigate the efficiency of the proposed algorithms and to gain insight about the value of the patrolling game. The results show the efficiency of the proposed algorithms. Finally, the authors present results for the case of a real urban rail network.


  • English

Media Info

Subject/Index Terms

Filing Info

  • Accession Number: 01675249
  • Record Type: Publication
  • Files: TRIS
  • Created Date: May 29 2018 11:01AM