Reinforcement learning approach to solve dynamic bi-objective police patrol dispatching and rescheduling problem

• Main Authors: JOE, Waldy, LAU, Hoong Chuin, PAN, Jonathan
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2022
• Subjects: Dynamic Vehicle Routing Problem; Reinforcement Learning; Police Patrol; Scheduling; Bi-Objective; Artificial Intelligence and Robotics; Software Engineering
• Online Access: https://ink.library.smu.edu.sg/sis_research/7739; https://ink.library.smu.edu.sg/context/sis_research/article/8742/viewcontent/19831_Article_Text_23844_1_2_20220613.pdf
• Institution: Singapore Management University

Police patrol aims to fulfill two main objectives namely to project presence and to respond to incidents in a timely manner. Incidents happen dynamically and can disrupt the initially-planned patrol schedules. The key decisions to be made will be which patrol agent to be dispatched to respond to an incident and subsequently how to adapt the patrol schedules in response to such dynamically-occurring incidents whilst still fulfilling both objectives; which sometimes can be conflicting. In this paper, we define this real-world problem as a Dynamic Bi-Objective Police Patrol Dispatching and Rescheduling Problem and propose a solution approach that combines Deep Reinforcement Learning (specifically neural networks-based Temporal-Difference learning with experience replay) to approximate the value function and a rescheduling heuristic based on ejection chains to learn both dispatching and rescheduling policies jointly. To address the dual objectives, we propose a reward function that implicitly tries to maximize the rate of successfully responding to an incident within a response time target while minimizing the reduction in patrol presence without the need to explicitly set predetermined weights for each objective. The proposed approach is able to compute both dispatching and rescheduling decisions almost instantaneously. Our work serves as the first work in the literature that takes into account these dual patrol objectives and real-world operational consideration where incident response may disrupt existing patrol schedules.