Otimizando o layout do campus com o problema das P-Medianas capacitado
DOI:
https://doi.org/10.14571/brajets.v18.n4.1425-1437Palavras-chave:
problema das p-medianas, programação linear inteira, metaheurísticasResumo
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.
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
Edição
Seção
Licença
Copyright (c) 2025 Clara dos Santos Becker, Marcelo de Souza, Tailini Schultz
Este trabalho está licenciado sob uma licença Creative Commons Attribution 4.0 International License. A revista segue a política para Periódicos de Acesso Livre, oferecendo acesso livre, imediato e gratuito ao seu conteúdo, seguindo o princípio de que disponibilizar gratuitamente o conhecimento científico ao público proporciona mais democratização internacional do conhecimento. Por isso, não se aplica taxas, sejam elas para submissão, avaliação, publicação, visualização ou downloads dos artigos. Além disso, a revista segue a licença Creative Common (CC BY) permitindo qualquer divulgação do artigo, desde que sejam referenciados o artigo original. Neste sentido, os autores que publicam nesta revista concordam com os seguintes termos: A) Os autores mantém os direitos autorais e concedem à revista o direito de primeira publicação, com o trabalho simultaneamente licenciado sob a Creative Commons Attribution License (CC BY), permitindo o compartilhamento do trabalho com reconhecimento da autoria do trabalho e publicação inicial nesta revista. B) Autores têm autorização para distribuição não-exclusiva da versão do trabalho publicada nesta revista (ex.: publicar em repositório institucional e não institucional, bem como capítulo de livro), com reconhecimento de autoria e publicação inicial nesta revista. C) Autores sãoo estimulados a publicar e distribuir seu trabalho online (ex.: repositórios online ou na sua página pessoal), bem como aumentar o impacto e a citação do trabalho publicado.
