Efficient City-Scale Patrolling Using Decomposition and Grafting

This paper uses an integer program (IP) to formulate the city-scale patrolling (CSP) problem, with the objective of maximizing the police visibility rate (PVR) and the constraint of incident response time guarantee. We decompose the original CSP into two subproblems: minimizing police problem (MinP) and maximizing PVR (MaxP) problem. A polynomial time approximation algorithm is proposed for MinP, and a polynomial time optimal algorithm is proposed for MaxP. We conduct experiments to demonstrate the efficiency of the proposed algorithm.

Authors

• Wanyuan Wang Department of Computer Science and Engineering, Southeast University
• Zichen Dong Southeast University
• Bo An Nanyang Technological University
• Yichuan Jiang

Keywords

• Police Patrolling
• multi-objective
• Approximation
• Decomposition