Modelos e algoritmos para variações modernas do problema de roteamento de veículos
Author:
Escarrone, Viccenzo
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.
