Defesa de Dissertação de Mestrado de Alexandre dos Santos Mello, em 31/08/2023, às 08:30 horas, na sala 310 do Instituto de Computação e por videoconferência.
Link para defesa: https://meet.google.com/gko-
Algoritmos Heurísticos Eficientes para o Problema de Roteamento de Veículos Elétricos com Frota Heterogênea e Entregas Fracionárias
Resumo:
Esta dissertação aborda algoritmos eficientes para o Problema de Roteamento de Veículos Elétricos com Frota Heterogênea e Entregas Fracionárias, uma derivação ainda pouco explorada do Problema de Roteamento de Veículos (PRV) clássico. Diferente do modelo clássico, a frota é composta por veículos elétricos de tamanhos e custos distintos, no qual o objetivo é encontrar as melhores rotas para atender um determinado conjunto de clientes. Para essa variação, a demanda de um cliente pode ser atendida de maneira fracionária, permitindo mais de uma visita ao mesmo cliente. O primeiro algoritmo proposto trata da união das meta-heurísticas Multi-Start e Iterated Local Search nomeado de MultILS-PRVE-DFH. O segundo método une as meta-heurísticas Multi-Start e Variable Neighborhood Search nomeado de VNS-PRVE-DFH. Para os dois métodos propostos, a busca local foi realizada com o Randomized Variable Neighborhood Descent utilizando um conjunto de 11 estruturas de vizinhanças. A partir dos resultados dos experimentos computacionais realizados em um conjunto de instâncias presentes na literatura, observou-se uma eficiência das duas abordagens propostas. Com a adição de novas características e restrições, os algoritmos conseguiram gerar soluções para atender o mesmo conjunto de clientes, diminuindo o número de veículos e/ou a distância percorrida, consequentemente, diminuindo o custo.
Abstract:
This dissertation addresses efficient algorithms for the Electric Vehicle Routing Problem with Heterogeneous Fleet and Fractional Deliveries, a still little explored derivation of the classic Vehicle Routing Problem (VRP). Unlike the classic model, the fleet is made up of electric vehicles of different sizes and costs, in which the objective is to find the best routes to serve a certain set of customers. For this variation, a customer’s demand can be met in a fractional way, allowing more than one visit to the same customer. The first proposed algorithm deals with the union of the meta-heuristics Multi-Start and Iterated Local Search named MultILS-PRVE-DFH. The second method joins the meta-heuristics Multi-Start and Variable Neighborhood Search named VNS-PRVE-DFH. For the two proposed methods, the local search was performed with Randomized Variable Neighborhood Descent using a set of 11 neighborhood structures. From the results of the computational experiments carried out on a set of instances present in the literature, an efficiency of the two proposed approaches was observed. With the addition of new features and restrictions, the algorithms were able to generate solutions to serve the same set of customers, reducing the number of vehicles and/or the distance traveled, consequently reducing the cost.
Banca examinadora:
Prof. Luiz Satoru Ochi, UFF – Presidente
Prof. Igor Machado Coelho, UFF
Prof. Matheus Nohra Haddad, UFV
Prof. Marcone Jamilson Freitas Souza, UFOP