Uma Heurística Híbrida para o Problema de Roteamento de Viaturas Policiais em Grandes Centros Urbanos
Resumo
Neste artigo uma heurística híbrida, baseada na metaheurística Iterated Local Search, com busca local Variable Neighborhood Descent, é proposta para resolver, de maneira aproximada, um problema de otimização relacionado ao Roteamento de Viaturas Policiais em Grandes Centros Urbanos (RVP-Urb), onde o principal objetivo é diminuir o risco de áreas com alta taxa de criminalidade, reduzindo a violência nas cidades.
Palavras-chave:
otimização, roteamento, cidades inteligentes
Referências
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.
Publicado
31/07/2022
Como Citar
LEARDINI, Raphael; CANELLAS, Eduardo; SÁ, Bruno; SANTOS, Wagner; FROTA, Yuri; OLIVEIRA, Daniel de; ROSSETI, Isabel.
Uma Heurística Híbrida para o Problema de Roteamento de Viaturas Policiais em Grandes Centros Urbanos. In: WORKSHOP BRASILEIRO DE CIDADES INTELIGENTES (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.
