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

Resumen

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.