O Repositório será lançado oficialmente no dia 9 de abril de 2025 às 14h30min no miniauditório do Campus Nova Suiça.
 

Um estudo com abordagem heurística para problemas de roteamento de veículos com janelas de tempo e múltiplos depósitos

Página do item simplificado
dc.contributor.advisorSouza, Marcone Jamilson Freitas
dc.contributor.advisor-coSouza, Sérgio Ricardo de
dc.contributor.authorBezerra, Sinaide Nunes
dc.contributor.authorLatteshttp://lattes.cnpq.br/5654731681042767
dc.contributor.refereeSouza, Marcone Jamilson Freitas
dc.contributor.refereeSouza, Sérgio Ricardo de
dc.contributor.refereeOchi, Luiz Satoru
dc.contributor.refereePenna, Puca Huachi Vaz
dc.contributor.refereeSá, Elisângela Martins de
dc.contributor.refereeWanner, Elizabeth Fialho
dc.date.accessioned2025-03-26T13:36:58Z
dc.date.available2025-03-26T13:36:58Z
dc.date.issued2023-02-27
dc.description.abstractEste trabalho trata de alguns problemas de roteamento de veículos com janelas de tempo e múltiplos depósitos. Nesse conjunto estão problemas com roteamento fechado e aberto que objetivam a redução na distância ou na quantidade de veículos. Esse conjunto de problemas é NP-difícil, pois eles têm como subproblema, o Problema de Roteamento de Veículos (PRV), onde os clientes são atendidos por uma frota de veículos de mesma capacidade homogênea, em que os custos são dados pela distância total percorrida ou quantidade total de veículos utilizados no atendimento aos clientes. Para resolver esses problemas, o Smart General Variable Neighborhood Search com Busca Local Adaptativa (SGVNSBLA) é apresentado. O algoritmo alterna o mecanismo de busca local entre duas estratégias diferentes. Na primeira estratégia, o método Randomized Variable Neighborhood Descent (RVND) realiza a busca local e, ao aplicar essa estratégia, as vizinhanças com os melhores vizinhos recebem uma pontuação maior. Na segunda estratégia, o método de busca local é aplicado apenas em uma única vizinhança, escolhida pelo método da roleta. Assim, a aplicação da primeira estratégia de busca local serve como método de aprendizagem para aplicação da segunda estratégia. Para testar esses algoritmos, usamos instâncias de benchmark do MDVRPTW envolvendo até 960 clientes, 12 depósitos e 120 veículos, num total de 48 instâncias teste. Para fins de comparação, outros algoritmos baseados em vizinhança também foram implementados. Os resultados encontrados permitiram avaliar a contribuição das estruturas de vizinhanças utilizadas nas soluções que buscam a redução na quantidade de veículos. Os resultados mostram que o desempenho do SGVNSBLA superou o dos outros algoritmos implementados visando a redução da frota. Houve uma redução da frota de veículos em 91,18% das instâncias avaliadas e o tamanho da frota alcançou uma redução média de até 23,32% em problemas com janelas de tempo e múltiplos depósitos. Ao se avaliar essas instâncias com roteamento aberto, houve redução na quantidade de veículos em 100% das instâncias, com baixa variabilidade.
dc.description.abstractotherThis work deals with vehicle routing problems with time windows and multiple depots. In this set, closed and open routing problems aim to reduce the distance or the number of vehicles. This set of problems is N P-hard because they have as subproblem, the Vehicle Routing Problem (VRP), where customers are served by a fleet of vehicles with the same homogeneous capacity, where the total distance gives the cost traveled or the total number of vehicles used to serve customers. To solve these problems, Smart General Variable Neighborhood Search with adaptive local search (SGVNSBLA) is introduced. The algorithm switches the local search engine between two different strategies. In the first strategy, the Randomized Variable Neighborhood Descent (RVND) method performs the local search. When this strategy is used, the neighborhoods with the best neighbors receive a higher score. In the second strategy, the local search method is applied only in a single neighborhood, which is selected using the roulette wheel method. Thus, applying the first local search strategy serves as a learning method for applying the second strategy. We used MDVRPTW benchmark instances with up to 960 customers, 12 depots, and 120 vehicles in 48 test instances to test these algorithms. Other neighborhood-based algorithms were also implemented for comparison purposes. Based on the results found, it was possible to evaluate the contribution of neighborhood structures in solutions to reduce the number of vehicles. The results show that the performance of SGVNSBLA outperformed other fleet reduction algorithms. Vehicle fleet reduction occurred in 91.18% of the evaluated instances, and fleet size achieved an average reduction of up to 23.32% for problems with time windows and multiple deposits. In assessing these instances with open routing, a reduction in the number of vehicles occurred in 100% of the cases, with low variability
dc.identifier.urihttps://repositorio.cefetmg.br//handle/123456789/953
dc.language.isopt
dc.publisherCentro Federal de Educação Tecnológica de Minas Gerais
dc.publisher.countryBrasil
dc.publisher.initialsCEFET-MG
dc.publisher.programPrograma de Pós-Graduação em Modelagem Matemática e Computacional
dc.subjectProgramação heurística
dc.subjectOtimização combinatória
dc.subjectVeículos
dc.subjectAlgoritmos
dc.subjectSoftwares
dc.titleUm estudo com abordagem heurística para problemas de roteamento de veículos com janelas de tempo e múltiplos depósitos
dc.typeTese

Arquivos

Pacote Original
Agora exibindo 1 - 1 de 1
Imagem de Miniatura
Nome:
Um estudo com abordagem heurística para problemas de roteamento de veículos.pdf
Tamanho:
2.23 MB
Formato:
Adobe Portable Document Format
Baixar
Licença do Pacote
Agora exibindo 1 - 1 de 1
Nenhuma Miniatura disponível
Nome:
license.txt
Tamanho:
1.39 KB
Formato:
Item-specific license agreed to upon submission
Descrição:
Baixar

Coleções

Doutorado em Modelagem Matemática e Computacional