This paper was published through Galoá and has a deposited DOI. To cite this paper, use one of the standards below:
In case you are one of the co-authors and want to register this paper in your Lattes, use the following code: doi > 10.59254/sbpo-2020-122557
If you've NEVER registered a DOI in your Lattes, check our tutorial!MODELO DE PROGRAMAÇÃO LINEAR INTEIRA MISTA PARA A OTIMIZAÇÃO DO ROTEAMENTO DE FROTAS DE VEÍCULOS ELÉTRICOS COM SERVIÇOS DE ENTREGA
Danny García Sanchéz
Universidade Estadual Paulista (Unesp)
Now you could share with me your questions, observations and congratulations
Create a topicComo parte das estratégias globais para a minimização das mudanças climáticas os veículos elétricos têm sido gradualmente incorporados a indústria dos transportes, porém, os problemas técnicos relacionados com a sua autonomia continuam a ser uma limitante para sua utilização comercial em massa. Portanto, desenvolvimentos em otimização continuam sendo necessários para resolver o problema do roteamento de veículos elétricos. Este trabalho propõe um modelo de programação linear inteira mista para solucionar o problema de roteamento de uma frota de veículos elétricos, considerando o estado de carga, capacidade de transporte, estações de carregamento e a localização dos clientes. O modelo proposto foi avaliado utilizando dois sistemas teste com 4 e 20 clientes, conformando 6 casos específicos. Conclui-se que a proposta apresenta potencial de aplicação na definição de rotas ótimas para frotas de veículos elétricos de empresas que distribuem mercadorias ou oferecem serviços que que requer visitas aos clientes.
Rafael Ajudarte de Campos
Olá! Este trabalho foi muito legal e muito bem explicado!
Eu fiquei com algumas curiosidades:
1)Por que cada estação de carregamento pode ser visitada apenas uma vez? E é uma vez no total do planejamento ou por rota?
Poderia se limitar a uma visita por veículo sem problemas eu acho (não sei exatamente como elas funcionam, então posso estar falando besteira kkk), já que vocês estão trabalhando com o índice k no modelo.
Para eventuais extensão em problemas com deadlines (e possivelmente janelas de tempo), é possível permitir ter múltiplas visitas em uma mesma estação de abastecimento se, caso use uma variável de carga de tempo wjk (horário em que se finaliza o serviço no nó j, em uma formulação com restrições estilo MTZ para o tempo), poderia-se adicionar uma restrição do tipo:
Para um dado centro de abastecimento j
wjk>=wik'-wjk' +M(xjik'-1), i \in N e k',k \in K k'!=k
(e a carga seria restituída baseado na diferença entre (wik'-wjk'-tij), que é o tempo que ele ficou carregando)
Não é a formulação ideal, mas permitira a extensão nesse caso kkk
Na formulação de fluxo de commodities (em que wij seria a carga de tempo no arco ij) poderia ser algo:
\sum_{i \in N} wijk>= \sum_{i \in N}(wjik'-Mxjik')-\sum_{e\inN}wejk', para todo j, k' e k: k'!=k
Eu imagino que as estações de abastecimentos parecem postos de combustivel com varias bombas (posso estar completamente enganado kkkk), mas uma opção para considerar isso é simplesmente criar mais nós de abastecimento que ficam exatamente na mesma posição (um pra cada "bomba")
2)Vocês pretendem aplicar algum método heurístico para resolver instâncias maiores?
Mais uma vez, meus parabéns pelo trabalho, ficou bem legal!
With nearly 200,000 papers published, Galoá empowers scholars to share and discover cutting-edge research through our streamlined and accessible academic publishing platform.
Learn more about our products:
This proceedings is identified by a DOI , for use in citations or bibliographic references. Attention: this is not a DOI for the paper and as such cannot be used in Lattes to identify a particular work.
Check the link "How to cite" in the paper's page, to see how to properly cite the paper
Danny García Sanchéz
Olá Rafael! Muito obrigado por dispensar seu tempo para ver a apresentação e revisar o trabalho proposto. Agradecemos também por compartilhar suas dúvidas e apreciações conosco.
Com respeito às estações de carregamento, estas podem ser visitadas até uma vez se for necessário, ou seja, por rota.
Até o momento, a modelagem apresentada foi realizada com o objetivo de mostrar a flexibilidade das soluções em diferentes casos para uma frota heterogênea (em termos de capacidade de mercadoria e estado de bateria) de veículos elétricos e tomar como base sua formulação matemática e expandi-lo em trabalhos posteriores nas diferentes variações que podemos encontrar na literatura, como a incorporação de janelas de tempo, estações de carregamento rápida e rotas abertas.
Hoje em dia, conseguimos modelar as janelas de tempo sem perder a lógica de modelagem oferecida pelo trabalho apresentado e nesta se incorpora a variável w_jk que você indica como sugestão, onde representa o tempo de carga de um veículo em uma estação de carregamento j. Quanto às restrições sugeridas, parecem-nos excelentes, porque é assim que as obtemos. No entanto, deve-se levar em consideração que este fluxo de tempo difere em alguns aspectos para os clientes e estações de carregamento.
Além disso, você está correto em relação ao layout físico das estações de carregamento. Estes possuem vários módulos de carga para uma quantidade m de veículos. Embora a consideração de ter vários nós sobrepostos no grafo para simular os módulos seja uma boa ideia, parâmetros como a capacidade de carga de cada uma das estações também devem ser levados em consideração no modelo matemático, o que leva a modelos mais complexos que considerem parâmetros estocásticos nos tópicos de carga e descarga de veículos e considerar a rede de distribuição de energia elétrica, que é um grande desafio de estudo atualmente enfrentado pelos pesquisadores (incorporação do planejamento com a operação).
Por último, o modelo consegue resolver casos de 24 nós em 21 minutos. Embora para instâncias maiores não obtenha soluções em tempos razoáveis devido à sua natureza matemática, pretende-se utilizar estratégias (como agrupamento de clientes por áreas de serviço) ou o uso de metaheurísticas, para obter boas soluções em tempos razoáveis, que para esse caso, seria obtida uma solução muito próxima da solução exata do problema.
Mais uma vez agradecemos a disposição e as perguntas apresentadas
Bom congresso!
Rafael Ajudarte de Campos
Olá Danny! Muito Obrigado pela resposta! Primeiro queria me desculpar pela formatação da minha primeira. Eu achei que apenas apertar "enter" trocaria a linha, e não foi o que aconteceu no momento da publicação, e a tornou bem mais complicada de se ler (então agradeço novamente pelo tempo adicional necessário para compreender o que eu escrevi kkk).
Bastante interessante as colocações, e uma ótima ideia o uso estratégico dos parâmetros, deve tornar uma formulação bem melhor. Uma outra curiosidade que me surgiu com esta resposta, mais especificamente sobre a existência de parâmetros de carga e descarga do veículos é em relação qual a abordagem mais usual (ou a que se vocês pretendem usar) para incorporar tais incertezas na modelagem?
E novamente, meus parabéns! Vocês fizeram um trabalho muito interessante e com alto potencial para futuras pesquisas. Obrigado também pela disposição para responder as minhas perguntas. Bom congresso!
Danny García Sanchéz
Rafael! Não se preocupe, as perguntas ficaram compreensíveis e a ideia é poder compartilhar conhecimentos na área. Nós realmente apreciamos seu interesse e participação em nosso trabalho.
Em relação à descarga de baterias em veículos elétricos, existem abordagens na literatura considerando a programação estocástica. Um exemplo que podemos encontrar é o artigo apresentado por [Yi e Bauer 2018] com o nome de “Optimal stochastic eco-routing solutions for electric vehicles”, onde é incorporada na modelagem a energia potencial através dos nós, a perda de energia devido ao meio ambiente, o peso dinâmico do veículo e, claramente, restrições de capacidade da bateria (temperatura, vida útil, etc).
Quanto a carga das baterias nas estações de carregamento, podemos encontrar trabalhos como “Enhanced Coordination Strategy for an Aggregator of Distributed Energy Resources Participating in the Day-Ahead Reserve Market” onde os autores propor o controle de carga de veículos elétricos para fornecer reserva para cima/para baixo e reduz seu custo aproveitando a geração distribuída renovável.
Estes são alguns exemplos do que se pode encontrar sobre o assunto de veículos elétricos e seus parâmetros de carga e descarga, além disso, esse é um assunto muito estudado nas últimas décadas.
Por outro lado, nosso esforço com este trabalho de programação inteira mista é integrar no futuro algoritmos de roteamento de veículos elétricos com algoritmos de localização de estações de carregamento, que para isso, fatores da rede de distribuição de energia elétrica devem ser levados em consideração tentando alcançar algum progresso em termos de planejamento e operação.
Mais uma vez agradecemos a disposição e as perguntas apresentadas Bom congresso!