Um iterated greedy e uma mateurística para o problema de roteamento de veículos elétricos com dois níveis e janela de tempo

• Ano de defesa: 2024
• Autor(a) principal: Junqueira, Igor de Andrade
• Orientador(a): Bernardino, Heder Soares
• Banca de defesa: Borges, Carlos Cristiano Hasenclever , Ochi, Luiz Satoru , Santos, André Gustavo dos
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de Juiz de Fora (UFJF)
• Programa de Pós-Graduação: Programa de Pós-graduação em Ciência da Computação
• Departamento: ICE – Instituto de Ciências Exatas
• País: Brasil
• Palavras-chave em Português: Roteamento em dois níveis; Roteamento de veículos elétricos; Matheurística; Iterated greedy; Two-echelon routing; Electric vehicle routing; Matheuristic
• Área do conhecimento CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
• Link de acesso: https://repositorio.ufjf.br/jspui/handle/ufjf/17025

O Problema de Roteamento de Veículos Elétricos com Dois Níveis e Janela de Tempo compreende uma variante do problema clássico de Roteamento de Veículos, em que é necessário atender clientes de um depósito central por depósitos intermediários (satélites). Os satélites atendem os clientes usando Veículos Elétricos, sendo que os satélites são atendidos com Veículos a Combustão que partem do depósito central. Estações de Recarga podem ser utilizadas para estender o alcance dos Veículos Elétricos. Esse trabalho propõem duas abordagens baseadas em Iterated Greedy (IG) para resolver o problema de otimização. A primeira consiste em um IG que utiliza operadores de destruição e reconstrução. Além disso, a busca local Random Variable Neighborhood Descent é utilizada para obter um mínimo local e, assim, melhorar a solução após a fase de reconstrução. O segundo método proposto consiste em uma matheurística que utiliza o IG proposto inicialmente com um particionamento de rotas. A matheurística usa o IG proposto inicialmente para gerar um conjunto de rotas de Veículos Elétricos. A solução desse problema consiste em uma seleção de um subconjunto de rotas de forma que todos os clientes sejam atendidos, modelo de Programação Linear Inteira Mista, enquanto minimiza o somatório total das distâncias das rotas selecionadas. Os métodos propostos foram comparados com o método do estado da arte e obtiveram resultados significativamente melhores, considerando a distância (função objetivo) e tempo de processamento.