Novo algoritmo acelera rotas para frotas elétricas
No cenário dinâmico da logística moderna, onde a eficiência operacional e a sustentabilidade ambiental são pilares fundamentais, uma nova conquista computacional está chamando a atenção de empresas e pesquisadores em todo o mundo. Um grupo de cientistas da Escola de Inteligência Artificial da Universidade de Anhui, liderado por Wang Chao, Qin Fang, Liu Rongrong e Jiang Hao, desenvolveu um algoritmo inovador que promete transformar a forma como as frotas de veículos elétricos (VEs) são gerenciadas, abordando um dos maiores desafios da logística verde: a otimização simultânea de rotas e recargas.
O problema, conhecido na literatura acadêmica como o Problema de Roteirização de Veículos Elétricos (EVRP), é notoriamente complexo. Diferentemente dos veículos movidos a combustão interna, cuja principal limitação é a capacidade de carga, os veículos elétricos introduzem uma segunda e crítica restrição: a autonomia da bateria. Isso significa que um planejador de rotas não pode simplesmente determinar a sequência mais eficiente para visitar todos os clientes; ele também precisa decidir com precisão quando, onde e por quanto tempo recarregar. Essa dupla otimização — da trajetória e da energia — expande exponencialmente o espaço de soluções possíveis, tornando o EVRP um problema classificado como NP-difícil. Em termos práticos, isso implica que o tempo necessário para encontrar a solução perfeita cresce de forma descontrolada à medida que o número de clientes aumenta, tornando métodos tradicionais inviáveis para operações do mundo real envolvendo centenas ou milhares de entregas.
Os métodos existentes para resolver o EVRP podem ser divididos em duas grandes categorias. A primeira é composta pelos algoritmos exatos, como a programação linear inteira mista. Esses métodos são capazes de encontrar a solução ótima, mas seu tempo de computação se torna proibitivo para problemas de grande escala. A segunda categoria inclui algoritmos heurísticos e metaheurísticos, como a busca tabu, a busca em vizinhança variável (VNS) e a busca adaptativa de grande vizinhança (ALNS). Esses algoritmos conseguem encontrar soluções boas em um tempo razoável, mas são suscetíveis a um problema comum: o aprisionamento em ótimos locais. Isso ocorre quando o algoritmo encontra uma solução razoável, mas fica “preso” nela, incapaz de explorar outras áreas do espaço de soluções que poderiam conter uma resposta muito melhor.
Os algoritmos evolutivos surgiram como uma alternativa promissora, pois se baseiam em uma população de soluções candidatas que “evoluem” ao longo do tempo por meio de processos de seleção, cruzamento e mutação. Sua natureza populacional permite uma exploração paralela de múltiplas regiões do espaço de soluções, o que reduz significativamente o risco de aprisionamento em ótimos locais. No entanto, mesmo esses métodos sofisticados enfrentam dificuldades ao lidar com a complexidade intrínseca do EVRP, especialmente quando se trata de equilibrar a minimização da distância total percorrida, a redução do número de veículos utilizados e a garantia de que nenhum veículo fique sem energia no meio de sua rota.
É neste contexto que o trabalho de Wang Chao, Qin Fang, Liu Rongrong e Jiang Hao representa um avanço significativo. A equipe da Universidade de Anhui propôs um algoritmo evolutivo cooperativo de dupla população (COEA), uma abordagem que representa uma mudança de paradigma na forma de atacar problemas de otimização complexos. Em vez de tentar resolver diretamente o intrincado problema do EVRP, os pesquisadores adotaram uma estratégia de “problema auxiliar”. A ideia central é criar um problema mais simples, mas relacionado, que possa ser resolvido rapidamente, e usar a solução desse problema para acelerar a resolução do problema principal.
O problema auxiliar escolhido é uma versão simplificada do clássico Problema de Roteirização de Veículos com Capacidade (CVRP). O CVRP considera as restrições de capacidade de carga dos veículos e a necessidade de visitar todos os clientes, mas ignora completamente a restrição de energia. Ao eliminar essa variável, o CVRP torna-se muito mais fácil de resolver, e sua população de soluções pode convergir para soluções de alta qualidade em um número muito menor de iterações.
A verdadeira genialidade do algoritmo COEA reside na forma como o conhecimento é transferido entre essas duas populações: a do problema simples (CVRP) e a do problema complexo (EVRP). Um simples intercâmbio de soluções seria ineficaz, pois uma rota ótima para um veículo a combustão não leva em conta os pontos de recarga. Para superar este obstáculo, os pesquisadores implementaram duas inovações fundamentais: uma nova forma de representar as soluções e um mecanismo de tradução inteligente.
A primeira inovação é uma matriz de adjacência de distância aprimorada. Em vez de representar uma rota apenas como uma sequência de números (por exemplo, 1-3-2-0, onde 0 é o depósito), o COEA utiliza uma matriz que codifica informações muito mais ricas. Cada célula dessa matriz não contém apenas a distância física entre dois pontos, mas também incorpora um valor relativo que indica a “afinidade” entre eles dentro da solução. Por exemplo, se dois clientes são atendidos pelo mesmo veículo, a “distância” entre eles nessa matriz é artificialmente reduzida. Se pertencem a rotas diferentes, essa “distância” é amplificada. Esse artifício permite que a matriz capture implicitamente a estrutura de agrupamento de clientes por veículo, uma informação crucial que um algoritmo de aprendizado pode utilizar para entender a lógica por trás de uma boa solução.
A segunda e mais revolucionária inovação é o uso de um codificador automático de remoção de ruído (DAE), uma técnica de aprendizado de máquina. O DAE atua como um tradutor entre os dois “idiomas” dos problemas. Durante o processo evolutivo, as melhores soluções de ambas as populações são convertidas em suas representações matriciais e usadas para treinar o DAE. O DAE aprende, assim, o mapeamento entre a estrutura de uma solução CVRP (ótima em termos de distância e capacidade) e como essa mesma estrutura poderia ser transformada em uma solução EVRP viável (que também leve em conta as baterias e as estações de recarga).
Uma vez treinado, esse DAE se torna um motor de transferência de conhecimento. Ele pega as soluções de elite da população CVRP, que convergiu rapidamente para padrões de agrupamento eficientes, e as “traduz” em soluções iniciais para a população EVRP. Isso é crucial: em vez de começar a busca do EVRP com soluções aleatórias, a população complexa recebe continuamente “sementes” de alta qualidade que já contêm uma lógica de agrupamento de clientes bem otimizada. Isso acelera dramaticamente o processo de convergência, pois o algoritmo EVRP não precisa perder tempo descobrindo como agrupar clientes de forma eficiente; esse conhecimento já foi transferido.
O processo é bidirecional. Não apenas soluções são enviadas do CVRP para o EVRP, mas também soluções de elite do EVRP são enviadas de volta para o CVRP. Esse feedback é vital, pois orienta a evolução do problema simples em direção a estruturas que são mais úteis e relevantes para o problema complexo. É um ciclo de melhoria contínua, no qual cada população ajuda a outra a evoluir em direção a um objetivo comum.
Para validar a eficácia de seu algoritmo, a equipe da Universidade de Anhui realizou uma série de testes exaustivos utilizando um conjunto de testes padrão para o EVRP que inclui instâncias de médio e grande porte, com até 400 clientes. Eles compararam o COEA com cinco dos algoritmos mais avançados da atualidade: BACO, KBEA, HVNS, ALNS e TS-MCWS. Os resultados foram conclusivos.
O COEA demonstrou uma velocidade de convergência significativamente mais rápida. Nos gráficos que mostram o custo médio da solução em função do número de iterações, a curva do COEA caiu muito mais rapidamente do que a de seus concorrentes, alcançando soluções de melhor qualidade em menos tempo. Em termos de resultados finais, o COEA obteve as melhores soluções conhecidas em 11 das 18 instâncias de teste, um desempenho particularmente notável nos problemas de grande escala, que são os mais relevantes para as operações logísticas do mundo real.
Em comparação direta, o COEA superou consistentemente BACO, HVNS e TS-MCWS, com melhorias no custo total que frequentemente excederam 20%. Mesmo em comparação com o KBEA, um algoritmo evolutivo avançado que utiliza informações históricas da população para guiar sua busca, o COEA obteve resultados superiores na maioria dos casos. Isso demonstra que a estratégia de transferência de conhecimento entre problemas é mais eficaz do que os métodos de aprendizado intra-populacional.
Estudos de ablação, nos quais os pesquisadores desativaram componentes-chave do COEA, confirmaram a importância de cada parte do design. Ao remover a matriz de distância aprimorada, o algoritmo perdeu sua capacidade de capturar a estrutura de agrupamento, o que desacelerou a convergência. Ao desativar o DAE e substituí-lo por uma troca direta de soluções, o desempenho se degradou severamente, confirmando que o mecanismo de tradução é essencial para uma transferência de conhecimento eficaz. Esses experimentos demonstraram que o COEA não é simplesmente a soma de suas partes, mas um sistema integrado no qual a interação entre a representação da solução, o DAE e a evolução cooperativa das populações cria um efeito sinérgico.
As implicações práticas dessa pesquisa são profundas. Para as empresas de logística, um algoritmo como o COEA significa a capacidade de operar frotas de veículos elétricos de maneira mais eficiente, reduzindo custos operacionais, estendendo a autonomia de seus veículos e melhorando a pontualidade das entregas. Isso pode ser a diferença entre uma operação rentável e uma que luta para cobrir seus custos.
Para as cidades e os planejadores urbanos, essa tecnologia oferece uma ferramenta poderosa para simular o comportamento das frotas elétricas e otimizar a colocação da infraestrutura de recarga. Em vez de instalar estações de recarga baseadas em suposições, os municípios podem usar modelos como este para prever com precisão onde os pontos de recarga serão necessários, maximizando sua utilização e minimizando o custo da rede.
Além da logística, este trabalho abre um novo caminho para a resolução de problemas de otimização complexos em diversos setores. O conceito de usar um problema auxiliar mais simples para guiar a solução de um mais complexo, facilitado por técnicas de aprendizado de máquina, poderia ser aplicado ao planejamento de redes de drones, à gestão de frotas híbridas ou à otimização de sistemas de transporte multimodal.
Em um momento em que a pressão por alcançar a neutralidade de carbono é cada vez maior, a inteligência do software que governa a logística verde é tão importante quanto a tecnologia dos veículos. O algoritmo COEA, desenvolvido por Wang Chao, Qin Fang, Liu Rongrong e Jiang Hao, não é apenas um avanço técnico; é um passo crucial em direção a um sistema de transporte mais inteligente, mais eficiente e verdadeiramente sustentável.
Novo algoritmo acelera rotas para frotas elétricas
Wang Chao, Qin Fang, Liu Rongrong, Jiang Hao, Escola de Inteligência Artificial, Universidade de Anhui, CAAI Transactions on Intelligent Systems, DOI: 10.11992/tis.202209007