A Hybrid Heuristic for the Problem of Routing Police Vehicles in Large Urban Centers
Abstract
In this paper, a hybrid heuristic, based on the Iterated Local Search metaheuristic, with local search based on Variable Neighborhood Descent, is proposed to solve an optimization problem related to Routing Police Vehicles in Large Urban Centers (RVP-Urb), where the main goal is to reduce the risk of areas with the high crime rate.
Keywords:
optimization, routing, smart cities
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.
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.
Chawathe, S. S. (2007). Organizing hot-spot police patrol routes. In 2007 IEEE Intelligence and Security Informatics, pages 79–86.
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, II4/W2:103–109.
Duarte, A., Sánchez-Oro, J., Mladenovíc, N., and Todosijevíc, R. (2018). Variable neighborhood descent. In Martí, R., Pardalos, P. M., and Resende, M. G. C., editors, Handbook of Heuristics, pages 341–367. Springer.
Gendreau, M., Laporte, G., and Semet, F. (2006). The maximal expected coverage relocation problem for emergency vehicles. J. Oper. Res. Soc., 57:22–28.
Jans, R. (2009). Solving lot-sizing problems on parallel identical machines using symmetry-breaking constraints. INFORMS J. on Computing, 21:123–136.
Lenstra, J. K. and Rinnooy Kan, A. H. G. (1981). Complexity of vehicle routing and scheduling problems. Networks, 11:221–227.
Lourenço, H., Martin, O., and Stützle, T. (2001). A beginner’s introduction to iterated local search. In 4th Metaheuristics International Conference, pages 1–11, Porto, Portugal.
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, pages 99–114.
Reis, D., Melo, A., Coelho, A. L. V., and Furtado, V. (2006). Towards optimal police patrol routes with genetic algorithms. In IEEE ISI, pages 485–491.
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:869–885.
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:1038–1053.
Sá, B., Muller, G., Banni, M., Santos, W., Lage, M., Rosseti, I., Frota, Y., and de Oliveira, D. (2021). PolrouteDS: 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.
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.
Chawathe, S. S. (2007). Organizing hot-spot police patrol routes. In 2007 IEEE Intelligence and Security Informatics, pages 79–86.
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, II4/W2:103–109.
Duarte, A., Sánchez-Oro, J., Mladenovíc, N., and Todosijevíc, R. (2018). Variable neighborhood descent. In Martí, R., Pardalos, P. M., and Resende, M. G. C., editors, Handbook of Heuristics, pages 341–367. Springer.
Gendreau, M., Laporte, G., and Semet, F. (2006). The maximal expected coverage relocation problem for emergency vehicles. J. Oper. Res. Soc., 57:22–28.
Jans, R. (2009). Solving lot-sizing problems on parallel identical machines using symmetry-breaking constraints. INFORMS J. on Computing, 21:123–136.
Lenstra, J. K. and Rinnooy Kan, A. H. G. (1981). Complexity of vehicle routing and scheduling problems. Networks, 11:221–227.
Lourenço, H., Martin, O., and Stützle, T. (2001). A beginner’s introduction to iterated local search. In 4th Metaheuristics International Conference, pages 1–11, Porto, Portugal.
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, pages 99–114.
Reis, D., Melo, A., Coelho, A. L. V., and Furtado, V. (2006). Towards optimal police patrol routes with genetic algorithms. In IEEE ISI, pages 485–491.
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:869–885.
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:1038–1053.
Sá, B., Muller, G., Banni, M., Santos, W., Lage, M., Rosseti, I., Frota, Y., and de Oliveira, D. (2021). PolrouteDS: 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.
Published
2022-07-31
How to Cite
LEARDINI, Raphael; CANELLAS, Eduardo; SÁ, Bruno; SANTOS, Wagner; FROTA, Yuri; OLIVEIRA, Daniel de; ROSSETI, Isabel.
A Hybrid Heuristic for the Problem of Routing Police Vehicles in Large Urban Centers . In: BRAZILIAN WORKSHOP ON INTELLIGENT CITIES (WBCI), 3. , 2022, Niterói.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2022
.
p. 13-24.
DOI: https://doi.org/10.5753/wbci.2022.222491.
