BRKGA-MP-IPR aplicado ao Problema de Localização de Contadores de Tráfego em redes de transporte

Ennio Willian Lima Silva; Francisco Glaubos Nunes Clímaco

doi:10.5753/semish.2026.23684

Ennio Willian Lima Silva IFTO https://orcid.org/0000-0002-0820-3692
Francisco Glaubos Nunes Clímaco UFMA https://orcid.org/0000-0002-1357-1318

DOI: https://doi.org/10.5753/semish.2026.23684

Resumo

O Problema de Localização de Contadores de Tráfego (PLCT) caracteriza-se por determinar o número e a localização das bases de contagem de tráfego em redes de transporte com o objetivo de estimar matrizes de origem-destino. Classificado como um problema NP-difícil, a resolução deste problema por métodos exatos em redes de grande porte apresenta um custo computacional muito alto para a convergência à otimalidade. Neste contexto, este trabalho propõe uma abordagem baseada no algoritmo BRKGA-MP-IPR associado a três heurísticas construtivas para a solução do PLCT. A eficácia do algoritmo foi avaliada em 26 instâncias reais, mapeadas a partir da infraestrutura rodoviária brasileira. Os experimentos computacionais demonstram que o BRKGA-MP-IPR superou metaheurísticas da literatura (GA e BRKGA padrão) em quase todas as instâncias e encontrou soluções melhores que o solver exato CPLEX em instâncias de alta densidade. Estes resultados evidenciam que a abordagem proposta é robusta e promissora para o PLCT.

Referências

Andrade, C. E., Toso, R. F., Gonçalves, J. F., and Resende, M. G. (2021). The multi-parent biased random-key genetic algorithm with implicit path-relinking and its real-world applications. European Journal of Operational Research, 289(1):17 – 30.

Bean, J. C. (1994). Genetic algorithms and random keys for sequencing and optimization. ORSA journal on computing, 6:154–160.

Chen, A., Pravinvongvuth, S., Chootinan, P., Lee, M., and Recker, W. (2007). Strategies for selecting additional traffic counts for improving o-d trip table estimation. Transportmetrica, 3:191 – 211.

Clímaco, G., Gonzalez, P. H., Ribeiro, G. M., Mauri, G. R., and Simonetti, L. (2019). A biased random-key genetic algorithm for the traffic counting location problem. In 2019 8th Brazilian Conference on Intelligent Systems (BRACIS), pages 275–280.

Garber, N. J. and Hoel, L. A. (2014). Traffic and highway engineering. Cengage Learning,.

Glover, F. (1998). A template for scatter search and path relinking. In Hao, J.-K., Lutton, E., Ronald, E., Schoenauer, M., and Snyers, D., editors, Artificial Evolution, pages 1–51, Berlin, Heidelberg. Springer Berlin Heidelberg.

González Silva, P. H., Clímaco, G., Simonetti, L., Gomes, H., and Ribeiro, G. (2016). HeurÍsticas para o problema de localizaÇÃo de contadores de trÁfego em redes de transporte. In Anais do XXX ANPET.

Gonçalves, J. F., Resende, M. G., and Toso, R. F. (2014). AN EXPERIMENTAL COMPARISON OF BIASED AND UNBIASED RANDOM-KEY GENETIC ALGORITHMS. Pesquisa Operacional, 34:143 – 164.

Guerriero, F., Macrina, G., Mosca, V., Scalzo, E., and Di Puglia Pugliese, L. (2026). Smart routing for perishable products: A multi objective brkga-based decoder ensuring quality and sustainability. Procedia Computer Science, 277:2085–2094. 7th International Conference on Industry of the Future and Smart Manufacturing (former International Conference on Industry 4.0 and Smart Manufacturing).

Karakose, G. and İslam Diri (2025). A path-free modelling approach for the traffic counting location problem. Computers Industrial Engineering, 204:111079.

LIMA, I. L. C. (2018). Meta-Heurística GRASP aplicada ao problema de localização de contadores de tráfego. Monografia (Bacharel em Ciência da Computação), UFMA (Universidade Federal do Maranhão), São Luís, Brasil.

Monteiro, R. C., Mauri, G. R., Boeres, M. C. S., Ribeiro, G., Filho, R., Júnior, N., and Abramides, C. (2019). Variações da meta-heurística cs para resolução de um problema de localização de contadores de tráfego. SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL.

Pinto, B. Q., Ribeiro, C. C., Rosseti, I., and Plastino, A. (2018). A biased randomkey genetic algorithm for the maximum quasi-clique problem. European Journal of Operational Research, 271(3):849 – 865.

Resende, M. G., Martí, R., Gallego, M., and Duarte, A. (2010). Grasp and path relinking for the max–min diversity problem. Computers & Operations Research, 37(3):498–508.

Ribeiro, C. C. and Resende, M. G. (2012). Path-relinking intensification methods for stochastic local search algorithms. Journal of heuristics, 18(2):193–214.

Silva, P., Clímaco, G., Mauri, G., Vieira, B. S., Ribeiro, G. M., Filho, R. O., Simonetti, L., Perim, L. R., and Hoffmann, I. C. S. (2019). New approaches for the traffic counting location problem. Expert Syst. Appl., 132:189–198.

Souffriau, W., Vansteenwegen, P., Vanden Berghe, G., and Van Oudheusden, D. (2010). A path relinking approach for the team orienteering problem. Computers and Operations Research, 37(11):1853 – 1859. Metaheuristics for Logistics and Vehicle Routing.

Yang, H., Yang, C., and Gan, L. (2006). Models and algorithms for the screen line-based traffic-counting location problems. Computers & Operations Research, 33:836–858.