Portal de Periódicos da CAPES

Artigo Acesso aberto Produção Nacional

BIBTEX RIS

Formulação p-step para o problema de caminho mínimo com restrições de recursos

2021; Linguagem: Português

10.5540/03.2021.008.01.0413

2359-0793

Júnior César Bonafim, Pedro Munari,

Transport Systems and Technology

Neste artigo, aborda-se o problema de caminho elementar com restrições de recursos (RCESPP, do inglês resource-constrained elementary shortest path problem) que, al ́em de formular diversas situações reais importantes, ocorre comumente como subproblema na resolução de outros problemas clássicos de otimiza ̧c ̃ao combinatória. Por exemplo, em formulações do roteamento de veículos cujas variáveis de decis ̃ao se relacionam a rotas factíveis, comumente resolvidos pela técnica de gera ̧c ̃ao de colunas, tais rotas s ̃ao obtidas pela resolução do RCESPP. Recentemente, foram introduzidas novas formulações para problemas de roteamento de veículos com base em variáveis que estão relacionadas a caminhos parciais de comprimento p, chamados p-steps. Tais formulações têm mostrado limitantes mais fortes em relação `as formulações tradicionais com variáveis baseadas em um único arco e, portanto, tem o potencial de beneficiar métodos de solução que dependem dessa característica. O objetivo deste trabalho é propor formulações p-step para a modelagem do RCESPP, dado que ainda n ̃ao foram usadas nesse contexto, explorando propriedades e características especiais do problema. Experimentos computacionais com instâncias da literatura foram realizados de modo a comparar o desempenho das formulações propostas em relação à formulação tradicional, considerando diferentes valores dep.