Optimizing campus layout with the capacitated P-Median problem

Authors

DOI:

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

Keywords:

p-medians problem, integer linear programming, metaheuristics

Abstract

Many real-world problems involve decision-making. Such scenarios rely on cost or performance measures to assess the quality of solutions and are often modeled as optimization problems. Their solution involves the mathematical formulation of the problem and, in some cases, the adoption of heuristic algorithms. This study presents a case study that applies mathematical programming and the iterated greedy metaheuristic to solve a urban planning problem in a university campus. To this end, the scenario was modeled as the capacitated p-median problem and different instances were generated. The results indicate that the exact approach is capable of solving small instances, while the iterated greedy provides good solutions for larger instances. Moreover, the metaheuristic produces high-quality solutions in less time than the exact method, demonstrating its feasibility for real-world urban planning scenarios.

Author Biographies

  • Clara dos Santos Becker, Santa Catarina State University

    NA

  • Marcelo de Souza, Santa Catarina State University

    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, Santa Catarina State University

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

References

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

Published

28-12-2025

Issue

Vol. 18 No. 4 (2025)

Section

Article

License

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

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

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.

How to Cite

dos Santos Becker, C., de Souza, M., & Schultz, T. (2025). Optimizing campus layout with the capacitated P-Median problem. Cadernos De Educação Tecnologia E Sociedade, 18(4), 1425-1437. https://doi.org/10.14571/brajets.v18.n4.1425-1437