The Patrol Scheduling Problem

Hoong Chuin LAU, Singapore Management University
A Gunawan


This paper presents the problem of scheduling security teams to patrol a mass rapid transit rail network of a large urban city. The main objective of patrol scheduling is to deploy security teams to stations at varying time periods of the network subject to rostering as well as security-related constraints. We present a mathematical programming model for this problem. We then discuss the aspect of injecting randomness by varying the start times, the break times for each team as well as the number of visits required for each station according to their reported vulnerability. Finally, we present results for the case of Singapore mass rapid transit rail network and synthetic instances.