Desenvolvimento de um modelo de programação linear inteira mista para a otimização do roteamento de frotas de veículos elétricos considerando estações de carregamento

Abstract

Os veículos elétricos (VEs) têm sido gradualmente incorporados na indústria do transporte como parte das estratégias globais para a minimização das mudanças climáticas, porém sua autonomia continua sendo uma limitante para sua incorporação em diferentes cenários de entrega de mercadorias. Portanto, desenvolvimentos em otimização ainda são necessários para resolver o problema de roteamento com serviço de entrega. Este trabalho propõe um modelo de programação linear inteira mista para solucionar o problema de roteamento de uma frota de VEs com janelas de tempo (PRFVE) e aborda o algoritmo k-means para agrupar clientes por zonas com o intuito de remover arcos pouco prometedores reduzindo o espaço de busca. O modelo considera o estado de carga, capacidade de mercadorias e da bateria dos VEs, assim como as janelas de tempo e posição dos clientes. A avaliação contempla dois sistemas teste com 4 e 45 clientes para 8 casos específicos com o objetivo de mostrar sua generalidade e o requerimento de tempo computacional para diferentes características da frota. Além disso, inclui-se o desenvolvimento de uma interface gráfica de usuário em linguagem de programação Python em conexão com a linguagem de modelação matemática AMPL para automatizar o processamento de dados, bem como permitir a representação gráfica das rotas e análise das soluções. Conclui-se que a proposta apresenta potencial de aplicação na definição de rotas ótimas para frotas de VEs de empresas que distribuem mercadorias ou oferecem serviços que requerem visitas aos clientes e definição das estações de carregamento no médio das rotas.

Electric vehicles (EVs) have been gradually incorporated into the transport industry as part of the global strategies for minimizing climate change. However, autonomy remains a limiting factor for their incorporation in different freight delivery scenarios. This work proposes a mixed-integer linear programming model to solve the electric vehicle fleets routing problem with time windows (E-VRPTW) and the approach of the k-means algorithm to group customers by zones to remove unpromising arcs reducing the space search. The model considers the state of charge, freights, and battery capacity of EVs, as well as the customer's time windows and position. E-VRPTW was evaluated using two test systems with 4 and 45 clients for 8 specific cases to show its generality and the behavior of computational time for different fleet characteristics. Also, it includes a graphical user interface developed in Python programming language in connection with the mathematical modeling language AMPL to automate data processing, allowing graphics representation of routes and analysis of solutions. It is concluded that the proposal has potential for application in defining optimal routes for EV fleets of companies that distribute freights or offer services that require visits to customers and definition of recharging stations in the middle of the road.