Optimizing Preventive Police Patrol Routes in Brazilian Cities Using a GRASP-Based Routing Heuristic
DOI:
https://doi.org/10.5753/jisa.2026.6805Keywords:
Preventive Policing, Preventive Police Patrol Routes, GRASP, MetaheuristicAbstract
Criminal activity is a major challenge for governments in large urban centers worldwide. Within Smart City initiatives, ensuring urban safety is a key priority. However, developing and applying data-driven approaches to reduce urban crime remains an open, yet important, issue. This paper addresses the Routing of Police Vehicles in Large Urban Centers (RVP-Urb) problem, which aims to maximize crime coverage while considering resource constraints. The proposed solution, called PROTECTOR, is a heuristic based on the Greedy Randomized Adaptive Search Procedure (GRASP), designed to generate preventive patrol routes that enhance police visibility in crime hotspots. Unlike existing methods, PROTECTOR mirrors the structure of Brazilian police departments by dividing urban areas into smaller zones and generating both intra- and inter-zone routes. The heuristic uses real-world crime hotspot data over defined time intervals to create daptive patrol plans that can be updated as hotspot patterns change. Experimental results using the RolRoute-DS ataset demonstrate that PROTECTOR performs effectively, producing near-optimal routes comparable to those enerated by exact mathematical models while maintaining computational efficiency.
Downloads
References
Alikhademi, K., Drobina, E., Prioleau, D., Richardson, B., Purves, D., and Gilbert, J. E. (2022). A review of predictive policing from the perspective of fairness. Artif. Intell. Law, 30:1-17. DOI: 10.1007/s10506-021-09286-4.
Bertsimas, D., van Ryzin, G., and Management, S. (1991). A stochastic and dynamic vehicle routing problem in the euclidean plane. Operations Research, 39:601-615. DOI: 10.1287/opre.39.4.601.
Bilal, M., Usmani, R. S. A., Tayyab, M., Mahmoud, A. A., Abdalla, R. M., Marjani, M., Pillai, T. R., and Targio Hashem, I. A. (2020). Smart Cities Data: Framework, Applications, and Challenges, pages 1-29. Springer International Publishing, Cham. DOI: 10.1007/978-3-030-15145-4_6-1.
Boba, R. (2005). Crime analysis and crime mapping. DOI: 10.4324/9780202101148-18.
Borrion, H., Ekblom, P., Alrajeh, D., Borrion, A. L., Keane, A., Koch, D., Mitchener-Nissen, T., and Toubaline, S. (2019). The problem with crime problem-solving: Towards a second generation pop? The British Journal of Criminology, 60(1):219-240. DOI: 10.1093/bjc/azz029.
Chawathe, S. S. (2007). Organizing hot-spot police patrol routes. In 2007 IEEE Intelligence and Security Informatics, pages 79-86. DOI: 10.1109/ISI.2007.379538.
Chen, H., Cheng, T., and Wise, S. (2015). Designing daily patrol routes for policing based on ant colony algorithm. ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences, II-4/W2:103-109. DOI: 10.5194/isprsannals-II-4-W2-103-2015.
Chen, H., Cheng, T., and Wise, S. (2017). Developing an online cooperative police patrol routing strategy. Computers, Environment and Urban Systems, 62:19-29. DOI: 10.1016/j.compenvurbsys.2016.10.013.
Coelho, V. N., Coelho, I. M., Oliveira, T. A., and Ochi, L. S. (2019). Smart and Digital Cities - From Computational Intelligence to Applied Social Sciences. Springer. DOI: 10.1007/978-3-030-12255-3.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2001). Introduction to Algorithms. The MIT Press, 2nd edition. DOI: 10.1017/cbo9781107279667.013.
Cunha Sá, B., Muller, G., Banni, M., Santos, W., Lage, M., Rosseti, I., Frota, Y., and de Oliveira, D. (2022). Polroute-ds: a crime dataset for optimization-based police patrol routing. Journal of Information and Data Management, 13(1). DOI: 10.5753/jidm.2022.2355.
Dewinter, M., Vandeviver, C., Vander Beken, T., and Witlox, F. (2020). Analysing the police patrol routing problem: A review. ISPRS International Journal of Geo-Information, 9(3). DOI: 10.3390/ijgi9030157.
Dos Anjos Júnior, O. R., Lombardi Filho, S. C., and Maia do Amaral, P. V. (2018). Determinantes da criminalidade na região sudeste do brasil: uma aplicação de painel espacial. Econ. Soc. Territ., (57). DOI: 10.22136/est20181176.
Duarte, A., Sánchez-Oro, J., Mladenović, N., and Todosijević, R. (2018). Variable neighborhood descent. In Martí, R., Pardalos, P. M., and Resende, M. G. C., editors, Handbook of Heuristics, pages 341-367. Springer. DOI: 10.1007/978-3-319-07153-4_9-1.
Eysenck, H. J. and Gudjonsson, G. H. (2013). The causes and cures of criminality. Springer Science & Business Media. DOI: 10.5860/choice.27-0986.
García-Ponce, O. and Laterzo, I. (2023). The legacy of mexico’s drug war on youth political attitudes. 2023(96). DOI: 10.35188/UNU-WIDER/2023/404-5.
Gendreau, M., Laporte, G., and Semet, F. (2006). The maximal expected coverage relocation problem for emergency vehicles. J. Oper. Res. Soc., 57(1):22-28. DOI: 10.1057/palgrave.jors.2601991.
Hale, C. D. and Chapman, S. G. (1981). Police patrol: Operations and management. Wiley NJ. Book.
Hjalmarsson, R., Machin, S., and Pinotti, P. (2024). Chapter 9 - crime and the labor market. volume 5 of Handbook of Labor Economics, pages 679-759. Elsevier. DOI: 10.1016/bs.heslab.2024.11.008.
Inmon, W., Welch, J., and Glassey, K. (2005). Building the Data Warehouse., volume 39. Sons Inc, New York. DOI: 10.1145/240455.240470.
Kim, D., Kan, Y., Aum, Y., Lee, W., and Yi, G. (2023). Hotspots-based patrol route optimization algorithm for smart policing. Heliyon, 9(10). DOI: 10.1016/j.heliyon.2023.e20931.
Lenstra, J. K. and Rinnooy Kan, A. H. G. (1981). Complexity of vehicle routing and scheduling problems. Networks, 11:221-227. DOI: 10.1002/net.3230110211.
Lourenço, V., Mann, P., Guimaraes, A., Paes, A., and de Oliveira, D. (2018). Towards safer (smart) cities: Discovering urban crime patterns using logic-based relational machine learning. In 2018 International Joint Conference on Neural Networks, IJCNN 2018, Rio de Janeiro, Brazil, July 8-13, 2018, pages 1-8. IEEE. DOI: 10.1109/IJCNN.2018.8489374.
López-Ibáñez, M., Dubois-Lacoste, J., Pérez Cáceres, L., Stützle, T., and Birattari, M. (2016). The irace package: Iterated racing for automatic algorithm configuration. Operations Research Perspectives, 3:43-58. DOI: 10.1016/j.orp.2016.09.002.
M. Ball, B. L. G. and Bodin, L. D. (1983). Planning for truck fleet size in the presence of a common‐carrier option. Decision Sciences, 14(1):103-120. DOI: 10.1111/j.1540-5915.1983.tb00172.x.
Melo, A., Belchior, M., and Furtado, V. (2005). Analyzing police patrol routes by simulating the physical reorganization of agents. In Sichman, J. S. and Antunes, L., editors, MABS 2005, volume 3891 of Lecture Notes in Computer Science, pages 99-114. Springer. DOI: 10.1007/11734680_8.
Obagbuwa, I. C. and Abidoye, A. P. (2021). South africa crime visualization, trends analysis, and prediction using machine learning linear regression technique. Appl. Comput. Intell. Soft Comput., 2021:5537902:1-5537902:14. DOI: 10.1155/2021/5537902.
Oliveira, L. F., Oliveira, D., and Frota, Y. (2023). Defining routes for emergency response from climate events: a data-oriented approach. IEEE Latin America Transactions, 21(10):1064-1072. DOI: 10.1109/TLA.2023.10255445.
Oliveira, W. A. d., Moretti, A. C., and Reis, E. F. (2015). Multi-vehicle covering tour problem: Building routes for urban patrolling. Pesqui. Oper., 35(3):617-644. DOI: 10.1590/0101-7438.2015.035.03.0617.
Reis, D., Melo, A., Coelho, A. L. V., and Furtado, V. (2006). Towards optimal police patrol routes with genetic algorithms. In Mehrotra, S., Zeng, D. D., Chen, H., Thuraisingham, B. M., and Wang, F., editors, IEEE ISI, volume 3975 of Lecture Notes in Computer Science, pages 485-491. Springer. DOI: 10.1007/11760146_45.
Resende, M. G. C. and Ribeiro, C. C. (2016). Optimization by GRASP: Greedy Randomized Adaptive Search Procedures. Springer Publishing Company, Incorporated. DOI: 10.1007/978-1-4939-6530-4.
Ristvej, J., Lacinák, M., and Ondrejka, R. (2020). On smart city and safe city concepts. Mob. Networks Appl., 25(3):836-845. DOI: 10.1007/s11036-020-01524-4.
Saint-Guillain, M., Paquay, C., and Limbourg, S. (2021). Time-dependent stochastic vehicle routing problem with random requests: Application to online police patrol management in brussels. Eur. J. Oper. Res., 292(3):869-885. DOI: 10.1016/j.ejor.2020.11.007.
Samanta, S., Sen, G., and Ghosh, S. K. (2022). A literature review on police patrolling problems. Annals of Operations Research, 316(2):1063-1106. DOI: 10.1007/s10479-021-04167-0.
Shen, Y., Lee, J., Jeong, H., Jeong, J., Lee, E., and Du, D. H. C. (2018). SAINT+: Self-adaptive interactive navigation tool+ for emergency service delivery optimization. IEEE Transactions on Intelligent Transportation Systems, 19(4):1038-1053. DOI: 10.1109/TITS.2017.2710881.
Silva, L. J. S., Fiol-González, S., Almeida, C. F. P., Barbosa, S. D. J., and Lopes, H. (2017). Crimevis: An interactive visualization system for analyzing crime data in the state of rio de janeiro. In Hammoudi, S., Smialek, M., Camp, O., and Filipe, J., editors, ICEIS 2017 - Proceedings of the 19th International Conference on Enterprise Information Systems, Volume 1, Porto, Portugal, April 26-29, 2017, pages 193-200. SciTePress. DOI: 10.5220/0006258701930200.
Sá, B., Muller, G., Banni, M., Santos, W., Lage, M., Rosseti, I., Frota, Y., and de Oliveira, D. (2021). Polroute-ds: um dataset de dados criminais para geração de rotas de patrulhamento policial. In Anais do III Dataset Showcase Workshop, pages 117-127, Porto Alegre, RS, Brasil. SBC. DOI: 10.5753/dsw.2021.17420.
Tregle, B., Smith, M. R., Fahmy, C., and Tillyer, R. (2025). More than meets the eye: examining the impact of hot spots policing on the reduction of city-wide crime. Crime Science, 14(1):3. DOI: 10.1186/s40163-025-00247-9.
Turchan, B. and Braga, A. A. (2024). The effects of hot spots policing on violence: A systematic review and meta-analysis. Aggression and Violent Behavior, 79:102011. DOI: 10.1016/j.avb.2024.102011.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2026 Journal of Internet Services and Applications
This work is licensed under a Creative Commons Attribution 4.0 International License.
