Matheurística com Abordagem Hierárquica Aplicada ao Problema de Roteamento de Veículos Capacitados e ao Problema de Roteamento de Helicópteros

Página do item simplificado
bibo.pageEnd165
dc.contributor.advisor1Mauri, Geraldo Regis
dc.contributor.advisor1IDhttps://orcid.org/0000-0002-8393-7741
dc.contributor.advisor1Latteshttp://lattes.cnpq.br/7870111209439581
dc.contributor.authorMachado, André Manhães
dc.contributor.authorIDhttps://orcid.org/0000-0002-8560-4473
dc.contributor.authorLatteshttp://lattes.cnpq.br/0364675276490227
dc.contributor.referee1Santos, Isaac Pinheiro dos
dc.contributor.referee1IDhttps://orcid.org/0000-0001-8524-0393
dc.contributor.referee1Latteshttp://lattes.cnpq.br/3793156690673506
dc.contributor.referee2Ribeiro, Glaydston Mattos
dc.contributor.referee2IDhttps://orcid.org/0000-0001-8452-057X
dc.contributor.referee2Latteshttp://lattes.cnpq.br/5401369683892150
dc.contributor.referee3Boeres, Maria Claudia Silva
dc.contributor.referee3IDhttps://orcid.org/0000-0001-9801-2410
dc.contributor.referee3Latteshttp://lattes.cnpq.br/0528154281423964
dc.contributor.referee4Amaral, André Renato Sales
dc.contributor.referee4IDhttps://orcid.org/0000-0001-7344-3994
dc.contributor.referee4Latteshttp://lattes.cnpq.br/4695002674556067
dc.contributor.referee5Lorenzoni, Luciano Lessa
dc.contributor.referee5IDhttps://orcid.org/0000-0003-4859-7750
dc.contributor.referee5Latteshttp://lattes.cnpq.br/7959495705859101
dc.date.accessioned2024-05-30T00:50:36Z
dc.date.available2024-05-30T00:50:36Z
dc.date.issued2021-10-27
dc.description.abstractThis work develops a hybrid matheuristic based on the approach Route-First-Cluster-Second (RFCS) by applying Greedy Randomized Adaptive Search Procedure (GRASP), mathematical models and Variable Neighborhood Search (VNS) to tackle two types of vehicle routing problems: the Capacitated Vehicle Routing Problem (CVRP) and the Helicopter Routing Problem (HRP). At rst, in the proposed method, a routing is performed using constructive heuristics and the Set Covering Problem (SCP). SCP employs local optima solutions found in previous iterations of VNS to create a partial tour which is lled by a constructive heuristic if needed. Then, the built solution undergoes a local search phase by VNS. This process is repeated as the main loop of the GRASP. As last step of the method, the Set Partitioning Problem (SPP) provides a new improved solution with regard to solutions found in the GRASP. In relation to the study problems, the CVRP consists of designing a set of routes for a eet of identical vehicles to attend a set of customers at shortest distance travelled, while the HRP aims of serving a set of transportation requests, dened as a pair of boarding and landing locations, using helicopters as the mode of transportation to minimize the cost of meeting the set of transportation requests. Besides, we propose a new HRP model to address unique characteristics of oshore platforms through a novel constraint to solve an issue that remains unnoticed until now: oshore platforms can be visited by helicopters one at a time. We also add the possibility to make multiple trips inside each route and enforce time window to attend passengers. Besides, the model has restrictions regarding to the total time of the ight, the fuel consumption, the total weight during the ight, the number of seats used by passengers. The matheuristic is proposed in two versions. The rst one solves the CVRP, and it is tested in seven benchmarks using other heuristics in the literature as a comparison. The second version is applied in two models of the HRP, where the method is tested in 37 instances with up to 1000 requests. Computational experiments showed that the proposed matheuristic for CVRP is competitive in terms of the quality for solutions reported in recent works. Moreover, in relation to the HRP, the matheuristic achieves results equal to or greater than other heuristics in 36 instances.
dc.description.resumoEsta tese propõe uma matheurística baseada na abordagem Route-First-Cluster-Second (RFCS) usando Greedy Randomized Adaptive Search Procedure (GRASP), modelos matemáticos e Variable Neighborhood Search (VNS) para resolver dois tipos de problemas de roteamento de veículos: o Capacitated Vehicle Routing Problem (CVRP) e o Helicopter Routing Problem (HRP). Inicialmente, no método proposto, o roteamento é realizado usando heurísticas construtivas e um Problema de Cobertura de Conjuntos (PCC). O PCC emprega as soluções localmente ótimas encontradas em iterações prévias do VNS para criar um tour parcial, o qual é completado por heurísticas construtivas se necessário. Em seguida, a solução construída passa por uma busca local pelo VNS. Esse processo é repetido no laço principal do GRASP. Após a nalização deste, um Problema de Particionamento de Conjuntos (PPC) gera a solução nal da matheurística usando as soluções localmente ótimas encontradas no laço principal do GRASP. Em relação aos problemas estudados, o CVRP consiste em gerar um conjunto de rotas para atender um conjunto de requisições de transporte com o apoio de uma frota de veículos idênticos. O objetivo é gerar rotas cuja soma das distâncias seja mínima. Já o HRP visa atender um conjunto de requisições de transporte, denidas como um par de locais de embarque e de desembarque, usando helicópteros como meio de transporte. O objetivo é atender todas as requisições com o menor custo possível. Além disso, esta tese também propõe um novo modelo matemático para o HRP que inclui novas características no atendimento de plataformas marítimas, as quais resolvem um problema até o momento em aberto: plataformas marítimas só possuem capacidade de atender um helicóptero por vez. Nesse novo modelo permite-se, também, que os helicópteros executem várias viagens por dia e que as requisições de transporte possuam janelas de tempo. Além disso, o modelo contém restrições relacionadas ao tempo, ao consumo de combustível, ao peso transportado e ao uso de assentos nas aeronaves. A matheurística é proposta em duas versões. A primeira resolve o CVRP e é avaliada em sete benchmarks do problema usando outras heurísticas da literatura como comparação. A segunda versão é aplicada em dois modelos do HRP, nos quais o método é testado em 37 instâncias com até 1000 requisições. Os experimentos computacionais mostram que o algoritmo proposto para o CVRP é competitivo em qualidade com as soluções publicadas em trabalhos recentes. Além disso, nas aplicações no HRP, a matheurística conseguiu resultados iguais ou superiores para 36 instâncias quando comparada a outros métodos da literatura.
dc.formatText
dc.identifier.urihttp://repositorio.ufes.br/handle/10/15443
dc.languagepor
dc.publisherUniversidade Federal do Espírito Santo
dc.publisher.countryBR
dc.publisher.courseDoutorado em Ciência da Computação
dc.publisher.departmentCentro Tecnológico
dc.publisher.initialsUFES
dc.publisher.programPrograma de Pós-Graduação em Informática
dc.rightsopen access
dc.subjectRoteamento de veículos capacitados
dc.subjectroteamento de helicópteros
dc.subjectGreedy Randomized Adaptive Search Procedure (GRASP)
dc.subjectVariable Neighborhood Search (VNS)
dc.subjectProblema de Cobertura de Conjuntos (PCC)
dc.subjectProblema de Particionamento de Conjuntos (PPC)
dc.subject.br-rjbnsubject.br-rjbn
dc.subject.cnpqCiência da Computação
dc.titleMatheurística com Abordagem Hierárquica Aplicada ao Problema de Roteamento de Veículos Capacitados e ao Problema de Roteamento de Helicópteros
dc.title.alternativetitle.alternative
dc.typedoctoralThesis
Arquivos
Pacote Original
Agora exibindo 1 - 1 de 1
Imagem de Miniatura
Nome:
AndreManhaesMachado-2021-tese.pdf
Tamanho:
1.81 MB
Formato:
Adobe Portable Document Format
Descrição:
Baixar
Coleções
Doutorado em Ciência da Computação