Urban rail patrolling: a game theoretic approach

Abdolmajid Yolmeh, Melike Baykal-Gürsoy

Research output: Contribution to journalArticlepeer-review

10 Scopus citations


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, we develop a game theoretic model for the problem of scheduling security teams to patrol an urban mass transit rail network. Our main objective is to minimize the expected potential damage caused by terrorist activities while observing scheduling constraints. We model this problem as a non-cooperative simultaneous move game between a defender and an attacker. We then develop column generation based algorithms to find a Nash equilibrium for this game. We 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. We then run computational experiments to investigate the efficiency of the proposed algorithms and to gain insight about the value of the patrolling game. Our results show the efficiency of the proposed algorithms. Finally, we present results for the case of a real urban rail network.

Original languageEnglish (US)
Pages (from-to)23-40
Number of pages18
JournalJournal of Transportation Security
Issue number1-2
StatePublished - Jun 1 2018

All Science Journal Classification (ASJC) codes

  • Transportation
  • Sociology and Political Science
  • Safety Research
  • Political Science and International Relations
  • Management Science and Operations Research
  • Law


  • Column generation
  • Patrolling game
  • Urban rail
  • Zero sum games


Dive into the research topics of 'Urban rail patrolling: a game theoretic approach'. Together they form a unique fingerprint.

Cite this