Modelos e algoritmos para variações modernas do problema de roteamento de veículos

Abstract

O problema de roteamento de veículos elétricos (Electric Vehicle Routing Problem – EVRP) constitui uma importante extensão do problema clássico de roteamento de veículos, incorporando restrições relacionadas à autonomia das baterias e à necessidade de recarga durante a realização das rotas. Este trabalho tem como objetivo implementar e comparar quatro formulações compactas para o EVRP com estações de recarga, combinando formulações baseadas nas restrições de Miller- Tucker-Zemlin (MTZ) e em fluxo (FL) com diferentes estratégias de representação das estações de recarga. As formulações foram implementadas em Python por meio da biblioteca PuLP e resolvidas utilizando o solver CBC, sendo avaliadas em instâncias derivadas dos benchmarks de Solomon. A comparação foi realizada considerando os limitantes inferior e superior obtidos, o gap entre esses limitantes e o tempo computacional necessário para a resolução das instâncias. Os resultados indicaram diferenças entre as formulações principalmente em relação à qualidade dos limitantes e ao esforço computacional. A formulação MTZ-A apresentou o menor gap médio, de 16,10%, enquanto a FL-A apresentou o menor tempo médio de resolução, de 1678,57 segundos. Esses resultados evidenciam que as diferentes estratégias de modelagem produzem impactos distintos sobre o desempenho do solver, não havendo uma formulação que apresente superioridade simultânea em todos os indicadores analisados. Dessa forma, a escolha da formulação deve considerar conjuntamente a qualidade dos limitantes obtidos e o custo computacional associado à resolução das instâncias.