Defesa de Mestrado de Ulysses Alessandro Couto Rocha

Título do Trabalho
Heuristic Techniques for Large-Scale Instances of The Cable-Trench Problem
Candidato(a)
Ulysses Alessandro Couto Rocha
Nível
Mestrado
Data
Add to Calender 2018-12-10 00:00:00 2018-12-10 00:00:00 Defesa de Mestrado de Ulysses Alessandro Couto Rocha Heuristic Techniques for Large-Scale Instances of The Cable-Trench Problem Sala 85 IC 2 INSTITUTO DE COMPUTAÇÃO mauroesc@ic.unicamp.br America/Sao_Paulo public
Horário
14:00
Local
Sala 85 IC 2
Orientador(a)
Flávio Keidi Miyazawa
Banca Examinadora

* Titulares

Unidade/Instituição

Flávio Keidi Miyazawa

IC/UNICAMP

Pedro Augusto Munari Junior

UFSCar

Fábio Luiz Usberti

IC/UNICAMP

 

* Suplentes

Unidade/Instituição

Rafael Crivellari Saliba Schouery

IC/UNICAMP

Pedro Henrique Del Bianco Hokama

UNIFEI

Resumo

O problema cabo trincheira foi apresentado em 2002 para modelar redes cabeadas. Esse problema pode ser visto como a união do problema de caminhos mínimos com o problema da árvore geradora mínima. Como entrada do problema temos um grafo $G=(V,E)$ com pesos nas arestas que indicam a distância entre os vértices incidentes na mesma. Há um vértice especial que representa uma instalação e demais vértices representam clientes. Uma solução para o problema é uma árvore geradora enraizada na instalação. O custo da solução é o custo da árvore geradora multiplicado por um fator de custo de trincheira mais os custos de cabos. Para cada cliente, o seu custo de cabo é dado pelo custo do caminho do cliente até a instalação multiplicado pelo custo de cabo. Esse problema modela cenários onde cada cliente deve ser conectado a uma instalação central através de um cabo dedicado. Cada cabo deve estar acomodado em uma trincheira e cada trincheira pode conter um número arbitrário de cabos. Sabendo que o custo dos cabos e trincheiras é proporcional a seu comprimento multiplicado por um fator de custo, o problema é encontrar uma rede com custo mínimo. Trabalhos anteriores utilizaram o problema cabo trincheira para modelar problemas em telecomunicações, distribuição de energia, redes ferroviárias e até vasos sanguíneos em exames de ressonância magnética.

Neste trabalho focamos na resolução do problema considerando instâncias de grande porte (superiores a 10 mil vértices). Desenvolvemos várias heurísticas para o problema. Na busca por simplificações de instâncias, demonstramos regras seguras e heurísticas para a remoção de arestas eliminando aquelas que dificilmente estariam em ``boas soluções" de uma instância. Apresentamos um algoritmo rápido para busca local capaz de ser executado mesmo em instâncias de grande porte. Desenvolvemos também algoritmos baseados em Greedy Randomized Adaptive Search Procedure (GRASP) e formulamos uma heurística que contrai vértices. Com a contração de vértices, criamos uma instância do problema cabo trincheira com demandas nos vértices. Essa versão com demandas tem um número menor de vértices que o problema original, o que viabiliza o uso de algoritmos baseados em programação linear para resolvê-lo. Demonstramos como é possível, ao resolver essa versão reduzida com demandas, remontar uma solução viável para o problema cabo trincheira original.

Atingimos, com essas heurísticas, resultados melhores do que trabalhos anteriores encontrados na literatura do problema. Para além disso, demonstramos como essa técnica de contração de vértices tem o potencial para resolver instâncias de tamanhos arbitrários para o problema cabo trincheira.