O Problema de Roteamento de Veículos Ativos e Passivos: Métodos Exatos Baseados em Decomposição de Benders

• Processo: 24/19351-2
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Data de Início da vigência: 01 de abril de 2025
• Data de Término da vigência: 31 de agosto de 2026
• Área de conhecimento: Engenharias - Engenharia de Produção - Pesquisa Operacional
• Pesquisador responsável: Maristela Oliveira dos Santos
• Beneficiário: Gabriel Vinicius Bacci
• Instituição Sede: Instituto de Ciências Matemáticas e de Computação (ICMC). Universidade de São Paulo (USP). São Carlos , SP, Brasil
• Vinculado ao auxílio: 22/05803-3 - Problemas de corte, empacotamento, dimensionamento de lotes, programação da produção, roteamento e localização e suas integrações em contextos industriais e logísticos, AP.TEM
• Palavra(s)-Chave do Pesquisador: Branch-and-Benders-Cut | Decomposição de Benders Baseado em Lógica | Problema de Roteamento de Veículos Ativos e Passivos | Otimização Inteira

Resumo

O Problema de Roteamento de Veículos Ativos e Passivos (APVRP, do inglês Active Passive Vehicle Routing Problem) surge em operações logísticas importantes, envolvendo a coordenação eficiente entre veículos ativos, que se deslocam de forma autônoma, e veículos passivos, que dependem dos veículos ativos para serem transportados. Esse problema é fundamental no apoio à tomada de decisão em diversos cenários práticos, como no transporte de contêineres em portos e na movimentação de materiais em fábricas, sendo classificado como NP-difícil devido à sua natureza combinatória. O {APVRP} apresenta características específicas que o tornam ainda mais desafiador que as variantes tradicionais do problema de roteamento de veículos, como a necessidade de sincronização eficiente das operações entre os dois tipos de veículos, além de restrições de compatibilidade e janelas de tempo. O objetivo deste trabalho é desenvolver novos métodos de solução exatos para o APVRP, utilizando a técnica de decomposição de Benders baseada em lógica. Pretende-se propor um algoritmo Branch-and-Benders-Cut que permita solucionar o problema de forma mais eficiente que os métodos existentes na literatura. Para avaliar as abordagens propostas, serão conduzidos experimentos computacionais com instâncias de teste disponíveis na literatura, comparando os resultados obtidos com o estado-da-arte.