A heuristic algorithm for the Multi-Depot Electric Location-Routing Problem with Time Windows, Battery Swap Stations and Partial Recharging

Download
Favorite this paper
How to cite this paper?
Details
  • Presentation type: Trabalho completo (oral)
  • Track: 12. L&T – Logística e Transportes
  • Keywords: Localização e Roteamento; Veículos elétricos; Metaheurísticas;

Authors:

  • 1 Universidade Federal de Viçosa
  • 2 UFV - Universidade Federal de Viçosa

A heuristic algorithm for the Multi-Depot Electric Location-Routing Problem with Time Windows, Battery Swap Stations and Partial Recharging

Victor Hugo Vidigal Corrêa

Universidade Federal de Viçosa

Abstract

Veículos elétricos se tornaram uma tendência nos últimos anos e um rápido avanço em suas tecnologias pode ser visto diariamente. Como toda tecnologia em ascensão, implementar uma infraestrutura boa e confiável é um passo crucial em sua adoção. Técnicas de otimização podem ser usadas para reduzir custos e torná-la mais atraente para empresas de logística aderirem ao uso desse meio de transporte. Neste artigo, apresentamos um algoritmo para o problema de roteamento e localização de veículos elétricos com múltiplos depósitos, janelas de tempo, troca de bateria e recarga parcial. O algoritmo proposto é composto por uma metaheurística Simulated Annealing com a busca local realizada por uma metaheurística GRASP-VNS. Comparamos os resultados deste algoritmo com o modelo matemático resolvido via Gurobi. Enquanto Gurobi foi capaz de resolver apenas instâncias de pequeno porte, o algoritmo apresentado foi capaz de resolver todos os tamanhos de instância e até obter alguns ótimos globais.

Questions (2 topics)

Share your ideas or questions with the authors!

Did you know that the greatest stimulus in scientific and cultural development is curiosity? Leave your questions or suggestions to the author!

Sign in to interact

Have a question or suggestion? Share your feedback with the authors!

Author

Victor Hugo Vidigal Corrêa

Obrigado pela pergunta Danny.

Realmente o ideal seria executar o modelo por um período de tempo maior, principalmente por causa da característica de longo prazo do problema. O planejamento inicial era usar o tempo limite de 8 horas, mas infelizmente não consegui utilizar o cluster da UFV (que ia tornar esse tempo mais praticável) e tive que fazer os experimentos na minha máquina pessoal, assim optamos por duas horas para não ficar com ela ocupada por muitos dias, pois o Gurobi consome quase toda a capacidade do computador.

Em relação a utilizar o modelo com tempos de execução maiores como trabalhos futuros. Creio que isso possa ser feito, mas acompanhando de um estudo de caso de uma região específica, por exemplo.

Obrigado.

Author

Victor Hugo Vidigal Corrêa

Obrigado Rafael. Como utilizamos instâncias para veículos de motor a combustão tivemos que adaptar os parâmetros de veículos elétricos de outras instâncias. Nós tentamos manter os custos mais próximos da realidade, contudo essas informações são difíceis de serem obtidas com exatidão. No nosso caso, por exemplo, não consideramos o custo da bateria pois não temos restrições de inventário dela (sugestão de trabalho futuro). Agora, em relação às restrições que mais pesaram, creio que foi a de múltiplos depósitos, elas aumentam bastante o espaço de soluções do problema.