O ex-aluno de mestrado do Departamento de Ciência da Computação (DCC) da UFMG, Luciano Ermelindo de Almeida, conquistou o 3º lugar no Prêmio de Dissertação do LVIII Simpósio Brasileiro de Pesquisa Operacional (SBPO), realizado de 28 de setembro a 1º de outubro, na UFMG. A dissertação, intitulada “Problema de orientação clusterizado com subgrupos”, foi desenvolvida sob orientação do professor do departamento Douglas G. Macharet. O trabalho foi defendido em novembro de 2025.
O estudo propõe o Clustered Orienteering Problem with Subgroups (COPS), uma nova variante de um problema clássico de planejamento de rotas. O modelo amplia os problemas conhecidos como Clustered Orienteering Problem (COP) e Set Orienteering Problem (SOP) ao introduzir uma estrutura hierárquica de subgrupos dentro dos agrupamentos. Com isso, é possível representar diferentes alternativas de visita em uma mesma região, considerando níveis distintos de esforço e recompensa.
A proposta tem aplicações em situações nas quais não é possível visitar todos os destinos e é necessário definir quais pontos devem ser priorizados. Entre os possíveis usos estão o planejamento de rotas para robôs móveis, logística, inspeção e monitoramento ambiental.
Para resolver o problema, Luciano desenvolveu duas abordagens. A primeira utiliza Programação Linear Inteira (ILP) e é direcionada a instâncias menores, nas quais é possível buscar soluções exatas. A segunda, denominada COPS-TABU, utiliza uma meta-heurística baseada em Busca Tabu para tratar instâncias maiores. Os experimentos mostraram que a abordagem apresenta resultados competitivos em relação a métodos utilizados como referência para os problemas relacionados.
Os resultados da pesquisa também deram origem a um artigo publicado na IEEE Robotics and Automation Letters (RA-L), em 2025, com Luciano E. Almeida, e os professores do DCC Cristiano Arbex Valle e Douglas G. Macharet como autores.
O SBPO é o principal evento anual da Sociedade Brasileira de Pesquisa Operacional (SOBRAPO) e reúne pesquisadores, estudantes e profissionais interessados em diferentes áreas da Pesquisa Operacional. A edição de 2026 foi organizada pela UFMG e pelo CEFET-MG e contou com sessões técnicas, apresentações orais e de pôsteres, palestras e minicursos.
O Prêmio de Dissertação integra as quatro premiações concedidas anualmente pela SOBRAPO para reconhecer trabalhos de pesquisa em Pesquisa Operacional. A categoria é destinada a dissertações de mestrado defendidas no período previsto pelo regulamento e submetidas ao processo de avaliação do SBPO.
