27 abr 2022
17:00 Defesa de Mestrado Integralmente a distância
Tema
Formulações e Desigualdades Válidas para o Problema das P-Medianas Hamiltonianas
Aluno
Davi Rodrigues
Orientador / Docente
Orientador: Fábio Luiz Usberti / Coorientador: Celso Cavellucci
Breve resumo
"O problema do caixeiro viajante (travelling salesman problem - TSP) tem por objetivo encontrar um ciclo Hamiltoniano de custo mínimo em um grafo não direcionado completo G = (V, E). Uma generalização do TSP é o problema das p-medianas Hamiltonianas, cujo objetivo é encontrar em G um subgrafo Hamiltoniano de custo mínimo composto por p ciclos disjuntos. Este trabalho propõe uma nova formulação, desigualdades válidas e metodologias de solução exata para o problema das p-medianas Hamiltonianas. Métodos heurísticos e meta-heurísticos também são explorados em alternativa aos metodos exatos. Experimentos computacionais avaliam o desempenho dos métodos propostos para um conjunto de instâncias da literatura. Uma variação do TSP, o problema do caixeiro viajante com cobertura (Covering Salesman Problem - CSP), visa obter um ciclo de custo mínimo que cobre todos os nós do grafo G, onde a cada vértice v é associado um conjunto de cobertura. Este trabalho também apresenta uma generalização do CSP, o problema das p-medianas Hamiltonianas com cobertura (Covering Hamiltonian p-Medians Problem - CHpMP), cujo objetivo é encontrar em G um subgrafo de custo mínimo composto por p ciclos Hamiltonianos disjuntos que cubram todos os nós de G. Uma formulação para este novo problema é apresentada, assim como ensaios computacionais para avaliar a solução exata do CHpMP."
Banca examinadora
Titulares:
Fábio Luiz Usberti IC/UNICAMP
Pedro Henrique Del Bianco Hokama IMC/UNIFEI
Eduardo Candido Xavier IC/UNICAMP
Suplentes:
Rafael Crivellari Saliba Schouery IC/UNICAMP
Mário César San Felice CCET/Ufscar