Um estudo de heurísticas para o Problema de Roteamento de Veículos

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorSilva, Maise Dantas da-
Autor(es): dc.contributorSilva, André Renato Villela da-
Autor(es): dc.contributorMartins, Carlos Bazilio-
Autor(es): dc.contributorVianna, Dalessandro Soares-
Autor(es): dc.contributorAndrade, Marcos Ribeiro Quinet De-
Autor(es): dc.creatorSilva, Layla de Oliveira Sampaio da-
Autor(es): dc.creatorSilva, Thiago dos Santos-
Data de aceite: dc.date.accessioned2025-01-03T11:35:01Z-
Data de disponibilização: dc.date.available2025-01-03T11:35:01Z-
Data de envio: dc.date.issued2024-07-25-
Data de envio: dc.date.issued2024-07-25-
Fonte completa do material: dc.identifierhttps://app.uff.br/riuff/handle/1/33671-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/918766-
Descrição: dc.descriptionO presente trabalho aborda o Problema de Roteamento de Veículos – PRV (Vehicle Routing Problem – VRP) por meio do estudo de heurísticas. O objetivo é fazer uso das heurísticas para encontrar soluções que serão aproximadas, em virtude de o problema ser NP-difícil, mas que minimizem o número de veículos necessários para realizar uma sequência de entregas e retornar ao depósito. Serão apresentados resultados comparativos em tabelas, que demonstram a eficiência das heurísticas para uma situação ou cenário. Três heurísticas serão apresentadas: o Método da Economia (Saving Algorithm) de Clarke e Wright, o Método da Varredura (Sweep Algorithm) e o Método de Fisher e Jaikumar. Essas heurísticas abrangem duas categorias: as construtivas e as de duas fases. A metodologia utilizada foi a da pesquisa bibliográfica de ordem comparativa e crítica. Visando a alcançar patamares tratáveis para o escopo de um trabalho monográfico de graduação, foi feita uma restrição da abordagem para circunscrever-se sobre o aspecto métrico da PRV, que em alguns casos pode ser identificado como uma generalização PCV (Problema do Caixeiro Viajante, ou TSP - Travelling Salesman Problem). A abordagem crítico-comparativa se estende em direção ao teste de um algoritmo programado, levando-se em conta o melhor perfil de otimização discutido ao longo do trabalho-
Descrição: dc.descriptionAbstract This work addresses the Vehicle Routing Problem – VRP, from the perspective of a study on heuristics. The main goal is to start from a comparative appraisal of selected heu- ristics to indicate how they could yield approximate solutions—since PRV is NP-Hard—for minimizing and optimizing the number of required vehicles deployed to perform the de- livery sequence, then returning to the central depot. The comparative results will be dis- played in tables, grading the relative efficiency of each considered heuristic to selected situational contexts or scenarios. Three heuristics will be presented and discussed: The Saving Algorithm by Clarke and Wright, the Sweep Algorithm, and Fisher and Jaikumar’s method. These heuristics range over two categories: the constructive and the two steps. The applied methodology was bibliographic research from a critical and comparative point of view. A scope restriction was required since the approach should be enclosed within the limits of an undergraduate monography. Only selected metric aspects of PRV (which in some cases could be equated to a generalization of the Travelling Salesman Problema – TSP) were considered. The critical and comparative assessment included the test of a written algorithm, a program built over an accepted optimization level, according to the optimization profile discussed throughout the text-
Descrição: dc.description43 p.-
Formato: dc.formatapplication/pdf-
Idioma: dc.languagept_BR-
Direitos: dc.rightsOpen Access-
Direitos: dc.rightsCC-BY-SA-
Palavras-chave: dc.subjectProblema de Roteamento de Veículos-
Palavras-chave: dc.subjectHeurísticas-
Palavras-chave: dc.subjectMétodo da Economia de Clarke e Wright-
Palavras-chave: dc.subjectMétodo da Varredura-
Palavras-chave: dc.subjectMétodo de Fischer e Jaikumar-
Palavras-chave: dc.subjectHeurística-
Palavras-chave: dc.subjectAbordagens heurísticas-
Palavras-chave: dc.subjectVehicle Routing Problem-
Palavras-chave: dc.subjectHeuristics-
Palavras-chave: dc.subjectClarke’s and Wright’s Saving Method-
Palavras-chave: dc.subjectSweep Method-
Palavras-chave: dc.subjectFisher and Jaikumar’s method-
Título: dc.titleUm estudo de heurísticas para o Problema de Roteamento de Veículos-
Tipo de arquivo: dc.typeTrabalho de conclusão de curso-
Aparece nas coleções:Repositório Institucional da Universidade Federal Fluminense - RiUFF

Não existem arquivos associados a este item.