Estudo e definição de modelos de computação evolucionária para o problema de roteamento de veículos com múltiplos depósitos.

Abstract

O Problema de Roteamento de Veículos com Múltiplos Depósitos (do inglês, Multiple Deposit Vehicle Routing Problem – MDVRP) é uma importante variante do clássico Problema de Roteamento de Veículos (PRV) (Vehicle Routing Problem – VRP). O MDVRP tem ampla aplicação prática e representa o contexto de diversas empresas. Como não existe até então um método capaz de obter a solução ótima do problema em tempo polinomial, este trabalho tem como objetivo o estudo do MDVRP a partir da construção de modelos de computação evolucionária. O problema é investigado no contexto monoobjetivo, considerando a redução do custo das rotas percorridas pelos veículos. Este trabalho apresenta uma meta-heurística híbrida baseada na Estratégia Evolutiva (Evolution Strategy – ES) com a incorporação de procedimentos de busca local. A estratégia aplicada é a (μ + lambda)-ES, a qual é responsável pela geração de descendentes a partir da mutação e a seleção dos indivíduos. A busca local é composta por nove estratégias, considerando os critérios de parada Best Improvement e First Improvement. A validação do algoritmo proposto foi realizada por meio de instâncias de teste disponíveis na literatura. Considerando o contexto experimental estabelecido, os resultados foram satisfatórios, sendo que alguns valores estão com um GAP de 10% em relação a literatura. Mesmo não atingindo o valor esperado em todas as instâncias, foi possível obter uma comparação com bons resultados e que podem ainda ser melhorados.