Abordagens Exatas e Heurísticas para o Problema Restrito dos Multiciclos de Steiner

• Processo: 25/19181-2
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de fevereiro de 2026
• Data de Término da vigência: 31 de janeiro de 2027
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Mário César San Felice
• Beneficiário: Gustavo Cesar Bento Laurindo
• Instituição Sede: Centro de Ciências Exatas e de Tecnologia (CCET). Universidade Federal de São Carlos (UFSCAR). São Carlos , SP, Brasil
• Assunto(s): Programação linear inteira Otimização combinatória
• Palavra(s)-Chave do Pesquisador: Heurísticas Construtivas | programação linear inteira | Roteamento Colaborativo de Veículos | Otimização Combinatória

Resumo

Problemas de Roteamento de Veículos consistem na busca por uma ou mais rotas para que veículos atendam às demandas, seja de transporte de clientes ou de fornecimento de produtos. Dessa forma, o objetivo é minimizar o custo total da operação realizada, que pode envolver tempo, combustível, etc. Essa família de problemas possui grande importância para a indústria, por modelar diversas questões logísticas.Este projeto tem como foco o Problema Restrito dos Multiciclos de Steiner, que é uma variante dos Problemas de Roteamento de Veículos, na qual busca-se um conjunto de ciclos de custo mínimo. Vale destacar que as demandas correspondem a pares de terminais que devem pertencer a um mesmo ciclo. Por se tratar de um problema NP-difícil, não é possível obter uma solução ótima, para todas as instâncias, em tempo polinomial. Sob esse aspecto, este projeto propõe o uso de abordagens exatas e heurísticas, com o objetivo de comparar suas soluções quanto ao custo computacional e a sua qualidade. Como Iniciação Científica, tal projeto também tem como objetivo a introdução do candidato na área de pesquisa científica e a complementação de sua formação em Engenharia de Computação. (AU)