Problema de roteamento de veículos elétricos capacitados com localização de estações de troca de baterias

Abstract

O aumento do número de veículos movidos a combustíveis fósseis, principalmente nos meios urbanos, elevou consideravelmente a quantidade de poluentes lançados ao meio ambiente. Com a criação da área de pesquisa denominada Logística Verde, foi possível propor soluções para a linha de produção e distribuição de produtos onde o impacto ao meio ambiente sejam reduzidos. Uma alternativa sustentável para a distribuição de produtos em grandes centros urbanos é a utilização de veículos elétricos. Neste trabalho, apresenta-se o Problema de Roteamento de Veículos Elétricos (PRVE) juntamente com a definição de locais estratégicos para a instalação de estações de trocas de baterias, considerando a autonomia limitada das baterias. Para tratar o problema, foi desenvolvido um algoritmo heurístico, baseado na meta-heurística Iterated Local Search (ILS). Na fase de construção da solução inicial foram utilizados dois métodos gulosos: o método do vizinho mais próximo e um segundo que considera maior demanda. No método de busca local, foi utilizado o Randomized Variable Neighborhood Descent (RVND) com um conjunto de 9 (nove) vizinhanças. Experimentos computacionais em instâncias da literatura mostram que foi possível obter resultados de alta qualidade, evidenciando a eficiência da abordagem proposta.

The increase in the number of vehicles powered by fossils fuels, mainly in urban areas, has considerably increased the number of pollutants released into the environment. With the creation of the Green Logistics research area, it was possible to propose solutions for the production line and product distribution where the impact on the environment is reduced. A sustainable alternative for distributing products in large urban centers is electric vehicles. In this work, the Electric Vehicle Routing Problem is presented along with the definition of strategic locations for the installation of battery exchange stations, considering the limited autonomy of the batteries. We developed a heuristic algorithm based on the Iterated Local Search meta-heuristic to solve the problem. In the construction phase of the initial solution, we used two greedy methods: the nearest neighbor method and a second that considers greater demand. In the local search method, we used the Randomized Variable Neighborhood Descent was used with a set of 9 neighborhoods. Computational experiments in instances of the literature show that it was possible to obtain high-quality results, showing the efficiency of the proposed approach.