A variable neighborhood search algorithm for a class of electric vehicle routing problems.

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorPenna, Puca Huachi Vaz-
Autor(es): dc.contributorSouza, Marcone Jamilson Freitas-
Autor(es): dc.contributorPenna, Puca Huachi Vaz-
Autor(es): dc.contributorSouza, Marcone Jamilson Freitas-
Autor(es): dc.contributorCarvalho, Marco Antonio Moreira de-
Autor(es): dc.contributorSilva, Rodrigo César Pedrosa-
Autor(es): dc.contributorSá, Elisangela Martins de-
Autor(es): dc.contributorCoelho, Igor Machado-
Autor(es): dc.creatorSouza, André Luyde da Silva-
Data de aceite: dc.date.accessioned2025-08-21T15:22:27Z-
Data de disponibilização: dc.date.available2025-08-21T15:22:27Z-
Data de envio: dc.date.issued2024-11-07-
Data de envio: dc.date.issued2024-11-07-
Data de envio: dc.date.issued2023-
Fonte completa do material: dc.identifierhttps://www.repositorio.ufop.br/handle/123456789/18939-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/1012328-
Descrição: dc.descriptionPrograma de Pós-Graduação em Ciência da Computação. Departamento de Ciência da Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto.-
Descrição: dc.descriptionThis thesis presents a flexible General Variable Neighborhood Search based al- gorithm, named Flexi-VNS, to address three problems in electric vehicle routing: the classical Electric Vehicle Routing Problem (EVRP), the Battery Swap Sta- tion Location-routing Problem with Capacitated Electric Vehicles (BSS-EV-LRP), and the Electric Vehicle Routing Problem with Time Windows (E-VRPTW). The Flexi-VNS algorithm incorporates a Randomized Variable Neighborhood Descent (RVND) method as its local search procedure, featuring an intra-RVND mechanism applied exclusively to modified routes upon each solution update. We evaluated the performance of Flexi-VNS on benchmark instances of the EVRP, BSS-EV-LRP, and E-VRPTW, comparing its results with existing algorithms from the literature. Computational results demonstrated the efficiency of Flexi-VNS. It improved sev- eral best-known solutions and reduced the number of battery swap stations required. Flexi-VNS also equaled or improved the BKS values for 47 out of 52 EVRP instances, 18 out of 30 BSS-EV-LRP instances, and 65 out of 92 E-VRPTW instances. These results correspond to success rates of 90.38% for EVRP instances, 60% for BSS- EV-LRP instances, and 70.65% for E-VRPTW instances. Additionally, Flexi-VNS provided the first solutions for several BSS-EV-LRP instances.-
Descrição: dc.descriptionEsta tese apresenta um algoritmo flexível baseado no algoritmo General Variable Neighborhood Search, denominado Flexi-VNS, para tratar de três problemas de roteamento de veículos elétricos: o Problema de Roteamento de Veículos Elétricos clássico (EVRP), o Problema de Roteamento de Localização de Estação de Troca de Bateria com Veículos Elétricos Capacitados (BSS-EV-LRP) e o Problema de Roteamento de Veículos Elétricos com Janelas de Tempo (E-VRPTW). O algoritmo Flexi-VNS incorpora um método Randomized Variable Neighborhood Descent (RVND) como seu procedimento de busca local, apresentando um mecanismo intra-RVND aplicado exclusivamente a rotas modificadas em cada atualização de solução. Avaliamos o desempenho do Flexi-VNS em instâncias de referência do EVRP, BSS-EV-LRP e E-VRPTW, comparando seus resultados com os algoritmos existentes na literatura. Os resultados computacionais demonstraram a eficiência do Flexi-VNS. Ele aprimorou várias soluções mais conhecidas e reduziu o número de estações de troca de bateria necessárias. O Flexi-VNS também igualou ou melhorou os valores de BKS para 47 das 52 instâncias de EVRP, 18 das 30 instâncias de BSS-EV-LRP e 65 das 92 instâncias de E-VRPTW. Esses resultados correspondem a taxas de sucesso de 90,38% para instâncias EVRP, 60% para instâncias BSS-EV-LRP e 70,65% para instâncias E-VRPTW. Além disso, o Flexi-VNS forneceu as primeiras soluções para várias instâncias de BSS-EV-LRP.-
Formato: dc.formatapplication/pdf-
Idioma: dc.languagept_BR-
Direitos: dc.rightsaberto-
Direitos: dc.rightsAttribution-ShareAlike 3.0 United States-
Direitos: dc.rightshttp://creativecommons.org/licenses/by-sa/3.0/us/-
Direitos: dc.rightsAutorização concedida ao Repositório Institucional da UFOP pelo(a) autor(a) em 28/10/2024 com as seguintes condições: disponível sob Licença Creative Commons 4.0 que permite copiar, distribuir e transmitir o trabalho, desde que sejam citados o autor e o licenciante.-
Palavras-chave: dc.subjectVariable neighborhood search-
Palavras-chave: dc.subjectElectric vehicles-
Palavras-chave: dc.subjectRouting problems-
Palavras-chave: dc.subjectBattery stations-
Palavras-chave: dc.subjectTime windows-
Título: dc.titleA variable neighborhood search algorithm for a class of electric vehicle routing problems.-
Tipo de arquivo: dc.typelivro digital-
Aparece nas coleções:Repositório Institucional - UFOP

Não existem arquivos associados a este item.