Soluções híbridas de geração de colunas e algoritmo genético para o problema de escalonamento de veículos elétricos com múltiplos depósitos

Abstract

Nos últimos anos, o uso de Veículos Elétricos (EVs) tem crescido significativamente devido à necessidade de reduzir as emissões de gases de efeito estufa. Esse contexto impulsiona a pesquisa sobre o Problema de Escalonamento de Veículos Elétricos (EVSP), que visa otimizar a operação de frotas elétricas. Esta dissertação aborda a resolução de uma variante complexa, o Problema de Escalonamento de Veículos Elétricos com Múltiplos Depósitos (MD-EVSP). Para tanto, neste trabalho, desenvolveu-se e comparou-se quatro arquiteturas híbridas que integram a Geração de Colunas (GC) e os Algoritmos Genéticos (AG), em diferentes estágios: GC-AG, pool-AG-GC, pool-GC e pool-AG e, em que pool é um conjunto inicial numeroso de diversas colunas. Todas as técnicas foram testadas em instancia adaptada de estudos prévios. Os resultados demonstraram que as arquiteturas que utilizam o AG como etapa final de solução (GC-AG e pool-AG) mostraram-se incapazes de gerar soluções factíveis, violando restrições essenciais do problema. Por outro lado, as abordagens que empregam a GC para a solução final (pool-GC e pool-AG-GC) produziram resultados válidos e de alta qualidade. Destaca-se a arquitetura pool-AG-GC como a mais promissora, na qual o AG atua como um filtro inteligente para o conjunto inicial de rotas, alcançando, em média, os menores custos.

In recent years, the use of Electric Vehicles (EVs) has grown significantly due to the need to reduce greenhouse gas emissions. This context drives research on the Electric Vehicle Scheduling Problem (EVSP), which aims to optimize the operation of electric fleets. This dissertation addresses a complex variant, the Multi-Depot Electric Vehicle Scheduling Problem (MD-EVSP). To this end, in this work there were developed and compared four hybrid architectures that integrate Column Generation (GC) and Genetic Algorithms (AG) at different stages: GC-AG, pool-AG-GC, pool-GC, and pool-AG, where pool is a large initial set of diverse columns. All techniques were tested on an adapted instance from previous studies. The results demonstrated that the architectures using AG as the final solution step (GC-AG and pool-AG) were unable to generate feasible solutions, violating essential problem constraints. On the other hand, the approaches employing GC for the final solution (pool-GC and pool-AG-GC) produced valid and high-quality results. The pool-AG-GC architecture stands out as the most promising, in which the AG acts as an intelligent filter for the initial set of routes, achieving, on average, the lowest costs.