Matheurística com Abordagem Hierárquica Aplicada ao Problema de
Roteamento de Veículos Capacitados e ao Problema de Roteamento de Helicópteros
Nome: ANDRÉ MANHÃES MACHADO
Tipo: Tese de doutorado
Data de publicação: 27/10/2021
Orientador:
Nome |
Papel |
|---|---|
| MARIA CLAUDIA SILVA BOERES | Co-orientador |
Banca:
| Nome |
Papel |
|---|---|
| ANDRÉ RENATO SALES AMARAL | Examinador Interno |
| GERALDO REGIS MAURI | Orientador |
| GLAYDSTON MATTOS RIBEIRO | Examinador Externo |
| ISAAC PINHEIRO DOS SANTOS | Examinador Interno |
| LUCIANO LESSA LORENZONI | Examinador Externo |
Páginas
Resumo: Esta 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 finalização deste, um Problema de Particionamento de Conjuntos (PPC) gera a solução final 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, definidas 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.
Palavras-chaves: Roteamento de Veículos Capacitados. Roteamento de Helicópteros. Greedy Randomized Adaptive Search Procedure (GRASP). Variable Neighborhood Search (VNS). Problema de Cobertura de Conjuntos (PCC). Problema de Particionamento de Conjuntos (PPC).
