Branch-cut-and-price algorithms for the clustered and generalized vehicle routing problems

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorBarboza, Eduardo Uchoa-
Autor(es): dc.contributorRoboredo, Marcos Costa-
Autor(es): dc.contributorPinto, Rafael Martinelli-
Autor(es): dc.creatorAntunes, Matheus Freitas Soares-
Data de aceite: dc.date.accessioned2024-07-11T18:22:08Z-
Data de disponibilização: dc.date.available2024-07-11T18:22:08Z-
Data de envio: dc.date.issued2023-08-15-
Data de envio: dc.date.issued2023-08-15-
Fonte completa do material: dc.identifierhttp://app.uff.br/riuff/handle/1/29968-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/769168-
Descrição: dc.description[EN] The Clustered Vehicle Routing Problem (CluVRP) and the Generalized Vehicle Routing Problem (GVRP) are variants of the classic Capacitated Vehicle Routing Problem (CVRP) where customers are partitioned into clusters. In the first problem, all customers in the same cluster must be visited in sequence by a single route. In the second problem, all customers in a cluster are served by visiting a single customer in it. This work proposes a model for GVRP, together with new reduction tests. Then, three different models for CluVRP are proposed and discussed. GVRP’s model had superior performance compared to other exact methods in the literature. The best performing CluVRP model is actually a reduction of the problem to a GVRP. All models are implemented and solved by the branch-cut-and-price algorithm in the VRPSolver package. The computational results show that the new approach can solve instances with up to 1,200 customers and 240 clusters, much larger than those that could be solved by previous exact algorithms-
Descrição: dc.descriptionO Problema de Roteamento de Veículos Clusterizado (CluVRP) e o Problema de Roteamento de Veículos Generalizado (GVRP) são variantes do clássico Problema de Roteamento de Veículos Capacitados (CVRP) em que os clientes são particionados em clusters. No primeiro problema, todos os clientes no mesmo cluster têm que ser visitados em sequência na mesma rota. No segundo, todos os clientes em um cluster são atendidos através da visita em um único cliente do mesmo. Este trabalho propõe um modelo para o GVRP com novos testes de redução de grafo. E então, três modelos diferentes para o CluVRP são apresentados e discutidos. O modelo para o GVRP apresentou performance superior comparado a outros métodos exatos da literatura. O modelo com melhor performance para o CluVRP é uma redução do problema para um GVRP. Todos os modelos são implementados e resolvidos através do algoritmo de Branch-cut-and-price no pacote VRPSolver. Os resultados computacionais mostram que a nova abordagem pode resolver instâncias com até 1200 clientes e 240 clusters, muito maiores que as que poderiam ser resolvidas por algoritmos exatos anteriores-
Descrição: dc.description92 p.-
Formato: dc.formatapplication/pdf-
Idioma: dc.languageen-
Direitos: dc.rightsOpen Access-
Direitos: dc.rightsCC-BY-SA-
Palavras-chave: dc.subjectVehicle routing-
Palavras-chave: dc.subjectColumn generation-
Palavras-chave: dc.subjectBranch-cut-and-price-
Palavras-chave: dc.subjectModeling-
Palavras-chave: dc.subjectCVRP-
Palavras-chave: dc.subjectCluVRP-
Palavras-chave: dc.subjectGVRP-
Palavras-chave: dc.subjectClustered routes-
Palavras-chave: dc.subjectRoteamento-
Palavras-chave: dc.subjectModelagem-
Palavras-chave: dc.subjectVeículo automotivo-
Palavras-chave: dc.subjectGrafo-
Palavras-chave: dc.subjectRoteamento de veículos-
Palavras-chave: dc.subjectGeração de colunas-
Palavras-chave: dc.subjectRotas clusterizadas-
Título: dc.titleBranch-cut-and-price algorithms for the clustered and generalized vehicle routing problems-
Título: dc.titleBranch-cut-and-price algorithms for the clustered and generalized vehicle routing problems-
Tipo de arquivo: dc.typeDissertação-
Aparece nas coleções:Repositório Institucional da Universidade Federal Fluminense - RiUFF

Não existem arquivos associados a este item.