A reactive GRASP algorithm for the multi-depot vehicle routing problem with time windows

Página do item simplificado
dc.contributor.advisor1Boeres, Maria Claudia Silva
dc.contributor.advisor1IDhttps://orcid.org/0000-0001-9801-2410
dc.contributor.advisor1Latteshttp://lattes.cnpq.br/0528154281423964
dc.contributor.authorSouza, Israel Pereira de
dc.contributor.referee1Ochi, Luiz Satoru
dc.contributor.referee2Amaral, Andre Renato Sales
dc.contributor.referee2Latteshttp://lattes.cnpq.br/4695002674556067
dc.date.accessioned2024-05-30T00:53:40Z
dc.date.available2024-05-30T00:53:40Z
dc.date.issued2022-07-19
dc.description.abstractThe vehicle routing problem (VRP) is a well know hard to solve problem in literature. In this work, we describe a reactive greedy randomized adaptive search procedures algorithm, for short, reactive GRASP, using a variable neighborhood descent (VND) algorithm as local search procedure to solve the multi-depot vehicle routing problem (MDVRP) and multi depot vehicle routing problem with time windows (MDVRPTW). This algorithm, called RGRASP+VND, combines four distinct local search procedures and a clustering technique. The Cordeau et al. dataset, a widely well known MDVRP benchmark, is considered for the experimental tests. RGRASP+VND achieves better results on most small instances and a lower average solution cost for all instances on the experimental tests when compared to the earlier GRASP approaches in the MDVRP literature. RGRASP+VND results are also compared with the state-of-the-art of MDVRP and MDVRPTW.
dc.description.resumoO problema de roteamento de veículos (PRV) é um problema conhecido na literatura, pela sua elevada complexidade computacional. Neste trabalho descrevemos o algoritmo Reactive greed randomized adaptive search procedures (Reactive GRASP), usando descendência de vizinhança variável, em inglês VND, como procedimento de busca local para resolver o problema de roteamento de veículos com múltiplos depósitos (PRVMD) e o problema de roteamento de veículos com múltiplos depósitos e janelas de tempo (PRVMDJT). Este algoritmo, denominado RGRASP+VND, combina quatro estratégias de busca local e uma técnica de clusterização. O conjunto de instâncias de Cordeau et al., um bench mark conhecido para o PRVMD e PRVMDJT, foi utilizado nos testes experimentais. O RGRASP+VND obtém melhores resultados na maioria das instâncias pequenas e a menor média de custo das soluções para todas as instâncias nos testes experimentais comparando com as aplicações anteriores do GRASP na literatura do MDVRP. Os resultados também são comparados com o estado da arte do MDVRP e MDVRPTW.
dc.formatText
dc.identifier.urihttp://repositorio.ufes.br/handle/10/16079
dc.languagepor
dc.publisherUniversidade Federal do Espírito Santo
dc.publisher.countryBR
dc.publisher.courseMestrado em Informática
dc.publisher.departmentCentro Tecnológico
dc.publisher.initialsUFES
dc.publisher.programPrograma de Pós-Graduação em Informática
dc.rightsopen access
dc.subjectReactive greed randomized adaptive search procedures
dc.subjectProblema de roteamento de veículos com múltiplos depósitos e janelas de tempo
dc.subjectLogísticas de cidades
dc.subject.br-rjbnsubject.br-rjbn
dc.subject.cnpqCiência da Computação
dc.titleA reactive GRASP algorithm for the multi-depot vehicle routing problem with time windows
dc.typemasterThesis
Arquivos
Pacote Original
Agora exibindo 1 - 1 de 1
Imagem de Miniatura
Nome:
IsraelPereiradeSouza-2022-dissertacao.pdf.pdf
Tamanho:
893.18 KB
Formato:
Adobe Portable Document Format
Descrição:
Baixar
Coleções
Mestrado em Informática