Otimizando o layout do campus com o problema das P-Medianas capacitado

Autores

DOI:

https://doi.org/10.14571/brajets.v18.n4.1425-1437

Palavras-chave:

problema das p-medianas, programação linear inteira, metaheurísticas

Resumo

Muitos problemas do mundo real envolvem a tomada de decisões. Tais cenários se baseiam em medidas de custo ou desempenho para avaliar a qualidade das soluções, e são frequentemente modelados como problemas de otimização. Sua solução consiste na formulação matemática do problema e, em alguns casos, na adoção de algoritmos heurísticos. Este trabalho apresenta um estudo de caso que aplica programação matemática e a metaheurística iterated greedy para resolver um problema de planejamento urbano em um campus universitário. Para isso, o cenário foi modelado como o problema das p-medianas capacitado e foram geradas diferentes instâncias. Os resultados mostram que a abordagem exata é capaz de resolver instâncias pequenas, enquanto o iterated greedy fornece boas soluções para instâncias maiores. Além disso, a metaheurística produz soluções de alta qualidade em tempo menor que o método exato, demonstrando sua viabilidade para cenários reais de planejamento urbano.

Biografias do Autor

  • Clara dos Santos Becker, Universidade do Estado de Santa Catarina

    Estudante do curso de Bacharelado em Engenharia de Software da Universidade do Estado de Santa Catarina.

  • Marcelo de Souza, Universidade do Estado de Santa Catarina

    Professor Adjunto do Departamento de Engenharia de Software e do Programa de Pós Graduação em Gestão da Informação da Universidade do Estado de Santa Catarina. Possui mestrado e doutorado em Ciência da Computação pela Universidade Federal do Rio Grande do Sul, e graduação em Bacharelado em Sistemas de Informação pela Universidade do Estado de Santa Catarina, com período sanduíche realizado na Universidade de León (Espanha). Também atuou como pesquisador visitante na Alliance Manchester Business School da Universidade de Manchester (Reino Unido). Trabalha nas áreas de inteligência artificial, otimização combinatória, algoritmos e grafos.

  • Tailini Schultz, Universidade do Estado de Santa Catarina

    Estudante do curso de Bacharelado em Engenharia de Software da Universidade do Estado de Santa Catarina.

Referências

Aloise, D., Noronha, T., Maia, R., Bittencourt, V. G., & Aloise, D. J. (2002). Heurísticas de colônia de formigas com path-relinking para o problema de otimização da alocação de sondas de produção terrestre. In XXXIV Simpósio Brasileiro de Pesquisa Operacional (SBPO).

Barcelos, F. B., Pizzolato, N. D., & Lorena, L. A. N. (2004). Localização de escolas do ensino fundamental com modelos capacitado e não-capacitado: Caso de Vitória/ES. Pesquisa Operacional, 24, 133–149.

Bynum, M. L., Hackebeil, G. A., Hart, W. E., Laird, C. D., Nicholson, B. L., Siirola, J. D., Watson, J.-P., & Woodruff, D. L. (2021). Pyomo: Optimization modeling in Python (3rd ed., Vol. 67). Springer Science & Business Media.

De Oliveira, J. G., Vianna, D. S., & Vianna, M. F. D. (2012). Uma heurística GRASP+VND para o problema de programação de horário escolar. Sistemas & Gestão, 7(3), 326–335.

Dorigo, M., Di Caro, G., & Gambardella, L. M. (1999). Ant algorithms for discrete optimization. Artificial Life, 5, 137–172.

Endler, K. D., Scarpin, C. T., & Steiner, M. T. A. (2017). Proposed system for analyzing the location of preschools: A Brazilian case study. Brazilian Journal of Operations & Production Management, 14(4), 446–460.

Feo, T. A., & Resende, M. G. C. (1995). Greedy randomized adaptive search procedures. Journal of Global Optimization, 6(2), 109–133.

Glover, F. (1986). Future paths for integer programming and links to artificial intelligence. Computers & Operations Research, 13, 533–549.

Hakimi, S. L. (1964). Optimum locations of switching centers and the absolute centers and medians of a graph. Operations Research, 12(3), 450–459.

Hart, W. E., Watson, J.-P., & Woodruff, D. L. (2011). Pyomo: Modeling and solving mathematical programs in Python. Mathematical Programming Computation, 3(3), 219–260.

Holland, J. H. (1975). Adaptation in natural and artificial systems. MIT Press.

Imran, A., Utomo, E. W., Ramadhan, F., Desrianty, A., Helianty, Y., & Mustofa, F. H. (2022). A simulation-based optimisation for the stochastic green capacitated p-median problem. Journal of Industrial Engineering and Management, 15(4), 552–565.

Isler, C., Bonassa, A., & Cunha, C. (2012). Algoritmo genético para resolução do problema de p-medianas capacitado associado à distribuição de peças automotivas. TRANSPORTES, 20.

Kirkpatrick, S., Gelatt, C., & Vecchi, M. (1983). Optimization by simulated annealing. Science, 220, 671–680.

Kocatepe, A., Ozguven, E. E., Horner, M., & Ozel, H. (2018). Pet-and special needs-friendly shelter planning in South Florida: A spatial capacitated p-median-based approach. International Journal of Disaster Risk Reduction, 31, 1207–1222.

López-Ibáñez, M., Dubois-Lacoste, J., Cáceres, L. P., Birattari, M., & Stützle, T. (2016). The irace package: Iterated racing for automatic algorithm configuration. Operations Research Perspectives, 3, 43–58.

Menezes, R. C., & Pizzolato, N. D. (2014). Locating public schools in fast expanding areas: Application of the capacitated p-median and maximal covering location models. Pesquisa Operacional, 34(2), 301–317.

Mesa, J., Ortega, F., & Pozo, M. (2013). Locating optimal timetables and vehicle schedules in a transit line. Annals of Operations Research, 222, 1–18.

Ruiz, R., & Stützle, T. (2007). A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. European Journal of Operational Research, 44, 2033–2049.

Song, G., He, X., Kong, Y., Li, K., Song, H., Zhai, S., & Luo, J. (2022). Improving the spatial accessibility of community-level healthcare service toward the “15-Minute City” goal in China. ISPRS International Journal of Geo-Information, 11(8), 436.

Silva, P., & Resendo, L. (2023). Heurística de busca de vizinhança variável para otimização do problema de roteamento de veículos. Anais do Computer on the Beach, 14, 145–150.

Vigneron, A., Gao, L., Golin, M., Italiano, G., & Li, B. (2000). An algorithm for finding a k-median in a directed tree. Information Processing Letters, 74, 81–88.

Downloads

Publicado

2025-12-28

Edição

Vol. 18 N.º 4 (2025)

Secção

Article

Licença

Direitos de Autor (c) 2025 Clara dos Santos Becker, Marcelo de Souza, Tailini Schultz

Creative Commons License

Este trabalho encontra-se publicado com a Licença Internacional Creative Commons Atribuição 4.0.

The BRAJETS follows the policy for Open Access Journals, provides immediate and free access to its content, following the principle that making scientific knowledge freely available to the public supports a greater global exchange of knowledge and provides more international democratization of knowledge. Therefore, no fees apply, whether for submission, evaluation, publication, viewing or downloading of articles. In this sense, the authors who publish in this journal agree with the following terms: A) The authors retain the copyright and grant the journal the right to first publication, with the work simultaneously licensed under the Creative Commons Attribution License (CC BY), allowing the sharing of the work with recognition of the authorship of the work and initial publication in this journal. B) Authors are authorized to distribute non-exclusively the version of the work published in this journal (eg, publish in the institutional and non-institutional repository, as well as a book chapter), with acknowledgment of authorship and initial publication in this journal. C) Authors are encouraged to publish and distribute their work online (eg, online repositories or on their personal page), as well as to increase the impact and citation of the published work.

Como Citar

dos Santos Becker, C., de Souza, M., & Schultz, T. (2025). Otimizando o layout do campus com o problema das P-Medianas capacitado. Cadernos De Educação Tecnologia E Sociedade, 18(4), 1425-1437. https://doi.org/10.14571/brajets.v18.n4.1425-1437