A Graph Theoretic-Based Approach for Optimizing Location-Routing and Crew Assignment in Police Patrols

Document Type : Research Paper

Authors

1 Ph.D., School of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran.

2 Professor, School of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran.

Abstract

Ensuring urban safety and preventing crime are paramount responsibilities of municipal managers. Police patrolling plays a crucial role in securing urban areas, yet limited resources and budget constraints necessitate an efficient patrolling system. This study introduces a multi-objective mathematical programming model aimed at maximizing the total effectiveness of a police patrolling system while minimizing associated costs. The approach utilizes a two-stage bi-objective Mixed Integer Linear Programming based on the K-windy postman problem. In the first stage, the model determines optimal locations for constructing police stations, while in the second stage, it allocates vehicle modes, plans patrolling routes, and assigns crew members to each vehicle. For small-size problems, the model is solved using the ε-constraint method, whereas a cluster-based algorithm is proposed for tackling medium- and large-size problems. To illustrate the model's applicability, a real-world case study involving various city zones in Tehran, Iran is examined. The proposed model offers a practical tool for optimizing police patrolling systems in similar urban settings.

Keywords

Main Subjects

References

Ahr, D., & Reinelt, G. (2002). New heuristics and lower bounds for the min-max k-Chinese postman problem. In Lecture Notes in Computer Science (pp. 64-74).
Ahr, D., & Reinelt, G. (2006). A tabu search algorithm for the min–max k-Chinese postman problem. Computers & Operations Research, 33(12), 3403-3422.
Akyurt, İ. Z., Keskinturk, T., & Kalkanci, Ç. (2015). Using Genetic Algorithm For Winter Maintenance Operations: Multi Depot K-Chinese Postman Problem. Emerging Markets Journal, 5(1), 50.
Amponsah, S. K., & Salhi, S. (2004). The investigation of a class of capacitated arc routing problems: the collection of garbage in developing countries. Waste Management, 24(7), 711-721.
Applegate, D., Cook, W., Dash, S., & Rohe, A. (2002). Solution of a min-max vehicle routing problem. INFORMS Journal on Computing, 14(2), 132-143.
Bodin, L. D., & Kursh, S. J. (1978). A computer-assisted system for the routing and scheduling of street sweepers. Operations Research, 26(4), 525-537.
Bowerman, R. L., Calamai, P. H., & Hall, G. B. (1994). The spacefilling curve with optimal partitioning heuristic for the vehicle routing problem. European Journal of Operational Research, 76(1), 128-142.
Chawathe, S. S. (2007). Organizing hot-spot police patrol routes. Intelligence and Security Informatics, 2007 IEEE,
Chen, H., Wu, Y., Wang, W., Zheng, Z., Ma, J., & Zhou, B. (2023). A Risk-aware Multi-objective Patrolling Route Optimization Method using Reinforcement Learning. 2023 IEEE 29th International Conference on Parallel and Distributed Systems (ICPADS),
Chen, X. (2012). Fast patrol route planning in dynamic environments. IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans, 42(4), 894-904.
Chen, X., Wu, S., Liu, Y., Wu, W., & Wang, S. (2022). A patrol routing problem for maritime crime-fighting. Transportation Research Part E: Logistics and Transportation Review, 168, 102940.
Chircop, P., Surendonk, T., van den Briel, M., & Walsh, T. (2013). A column generation approach for the scheduling of patrol boats to provide complete patrol coverage. Proceedings of the 20th International Congress on Modelling and Simulation,
Dewil, R., Vansteenwegen, P., Cattrysse, D., & Van Oudheusden, D. (2015). A minimum cost network flow model for the maximum covering and patrol routing problem. European Journal of Operational Research, 247(1), 27-36.
Dewinter, M., Vandeviver, C., Vander Beken, T., & Witlox, F. (2023). Analysing the police patrol routing problem: a review. ISPRS International Journal of Geo-Information, 9(3), 157.
Dondo, R., & Cerdá, J. (2007). A cluster-based optimization approach for the multi-depot heterogeneous fleet vehicle routing problem with time windows. European Journal of Operational Research, 176(3), 1478-1507.
Eiselt, H. A., Gendreau, M., & Laporte, G. (1995). Arc routing problems, part I: The Chinese postman problem. Operations Research, 43(2), 231-242.
Frederickson, G. N., Hecht, M. S., & Kim, C. E. (1976). Approximation algorithms for some routing problems. Foundations of Computer Science, 1976., 17th Annual Symposium on,
Haimes, Y. Y. (1971). On a bicriterion formulation of the problems of integrated system identification and system optimization. IEEE Transactions on Systems, Man, and Cybernetics, 1(3), 296-297.
Jiang, Y., Li, H., Feng, B., Wu, Z., Zhao, S., & Wang, Z. (2022). Street patrol routing optimization in smart city management based on genetic algorithm: a case in Zhengzhou, China. ISPRS International Journal of Geo-Information, 11(3), 171.
Joe, W., Lau, H. C., & Pan, J. (2023). Reinforcement learning approach to solve dynamic bi-objective police patrol dispatching and rescheduling problem. Proceedings of the International Conference on Automated Planning and Scheduling,
Kajita, M., Murakami, D., Kajita, S., Ribeiro, G., Zeferino, G., & Beato, C. (2024). Urban Crime Deterrence Through Patrol Route Optimization and Security Performance Evaluation: An Experiment in Belo Horizonte. Available at SSRN 4745611.
Katole, R., Mallya, D., Vachhani, L., & Sinha, A. (2023). Balancing Priorities in Patrolling with Rabbit Walks. arXiv preprint arXiv:2312.16564.
Keskin, B. B., Li, S. R., Steil, D., & Spiller, S. (2012). Analysis of an integrated maximum covering and patrol routing problem. Transportation Research Part E: Logistics and Transportation Review, 48(1), 215-232.
Keskin, M. E., Yılmaz, M., & Triki, C. (2023). Solving the hierarchical windy postman problem with variable service costs using a math-heuristic algorithm. Soft Computing, 27(13), 8789-8805.
Khorramizadeh, M., & Javvi, R. (2024). A branch-and-cut algorithm for the windy profitable location rural postman problem. Annals of Operations Research, 1-30.
Li, M., Zhen, L., Wang, S., Lv, W., & Qu, X. (2018). Unmanned Aerial Vehicle Scheduling Problem for Traffic Monitoring. Computers & Industrial Engineering.
Li, S. R., & Keskin, B. B. (2014). Bi-criteria dynamic location-routing problem for patrol coverage. Journal of the Operational Research Society, 65(11), 1711-1725.
Lum, O., Zhang, R., Golden, B., & Wasil, E. (2017). A hybrid heuristic procedure for the windy rural postman problem with zigzag time windows. Computers & Operations Research, 88, 247-257.
Mavrotas, G. (2009). Effective implementation of the ε-constraint method in multi-objective mathematical programming problems. Applied Mathematics and Computation, 213(2), 455-465.
Mei-Ko, K. (1962). Graphic programming using odd or even points. Chinese Math., 1, 273-277.
Minieka, E. (1979). The Chinese postman problem for mixed networks. Management Science, 25(7), 643-648.
Muaafa, M., & Ramirez-Marquez, J. E. (2017). Bi-objective evolutionary approach to the design of patrolling schemes for improved border security. Computers & Industrial Engineering, 107, 74-84.
Perrier, N., Langevin, A., & Amaya, C. A. (2008). Vehicle routing for urban snow plowing operations. Transportation Science, 42(1), 44-56.
Perrier, N., Langevin, A., & Campbell, J. F. (2007). A survey of models and algorithms for winter road maintenance. Part IV: Vehicle routing and fleet sizing for plowing and snow disposal. Computers & Operations Research, 34(1), 258-294.
Reis, D., Melo, A., Coelho, A. L., & Furtado, V. (2006). Towards optimal police patrol routes with genetic algorithms. In International Conference on Intelligence and Security Informatics (pp. 485-491). Springer.
Rumiantsev, B. V., Kochkarov, R. A., & Kochkarov, A. A. (2023). Graph-Clustering Method for Construction of the Optimal Movement Trajectory under the Terrain Patrolling. Mathematics, 11(1), 223.
Sá, B. C., Muller, G., Banni, M., Santos, W., Lage, M., Rosseti, I., Frota, Y., & de Oliveira, D. (2022). Polroute-ds: a crime dataset for optimization-based police patrol routing. Journal of Information and Data Management, 13(1).
Samanifar, S., Ahmadzade, H., & Nehi, H. M. (2024). Windy postman problem under uncertainty. Journal of Uncertain Systems, 17(01), 2350014.
Samanta, S., Sen, G., & Ghosh, S. K. (2022). A literature review on police patrolling problems. Annals of Operations Research, 316(2), 1063-1106.
Shafahi, A., & Haghani, A. (2015). Generalized Maximum Benefit Multiple Chinese Postman Problem. Transportation Research Part C: Emerging Technologies, 55, 261-272.
Sherman, L. W., & Weisburd, D. (1995). General deterrent effects of police patrol in crime “hot spots”: A randomized, controlled trial. Justice Quarterly, 12(4), 625-648.
Takamiya, M., & Watanabe, T. (2011). Planning high responsive police patrol routes with frequency constraints. Proceedings of the 5th International Conference on Ubiquitous Information Management and Communication,
Thabet, M., Messaadia, M., & Al-Khalifa, A. K. (2023). Police Patrol Routes Optimization: A Literature Review. 2023 International Conference On Cyber Management And Engineering (CyMaEn),
Thomassen, C. (1997). On the complexity of finding a minimum cycle cover of a graph. SIAM Journal on Computing, 26(3), 675-677.
Tohyama, H., & Tomisawa, M. (2022). Complexity of the Police Officer Patrol Problem. Journal of Information Processing, 30, 307-314.
Vincent, F. Y., & Lin, S. W. (2015). Iterated greedy heuristic for the time-dependent prize-collecting arc routing problem. Computers & Industrial Engineering, 90, 54-66.
Willemse, E. J., & Joubert, J. W. (2012). Applying min–max k postmen problems to the routing of security guards. Journal of the Operational Research Society, 63(2), 245-260.
Win, Z. (1987). Contributions to routing problems.
Wong, S., Joe, W., & Lau, H. C. (2023). Dynamic police patrol scheduling with multi-agent reinforcement learning. SpringerLink.
Advances in Industrial Engineering
Volume 59, Issue 1
June 2025
Pages 133-152

Files

Share

How to cite

Statistics