Português English
Contato
Publicado em: 29/11/2013

Proposta de Tese em Fundamentos da Co

UNIVERSIDADE FEDERAL DO RIO GRANDE DO SUL
INSTITUTO DE INFORMÁTICA
PROGRAMA DE PÓS-GRADUAÇÃO EM COMPUTAÇÃO
———————————————-
DEFESA DE PROPOSTA DE TESE
Aluno: Fernando Stefanello
Orientadora: Profa. Dra. Luciana Salete Buriol
Coorientador: Dr. Mauricio Guilherme Carvalho Resende
Título: Otimização Combinatória
Linha de Pesquisa: Fundamentos da Computação
Data: 06/12/2013
Horário: 13h
Local: Sala 220 (conselhos). Prédio 43412 – Instituto de Informática
Banca Examinadora:
Profa. Dra. Ana Lúcia Cetertich Bazzan (UFRGS)
Prof. Dr. Carlos Hoppen (UFRGS)
Prof. Dr. Geraldo Robson Mateus (UFMG)
Profa. Dra. Márcia Helena Costa Fampa (UFRJ)
Presidente da Banca: Profa. Dra. Luciana Salete Buriol
Resumo:
Problemas de fluxo em redes despertam muito interesse na comunidade científica e possuem inúmeras aplicações nas mais diferentes áreas de pesquisa, incluindo redes de transporte, telecomunicações e cadeias de suprimentos. Uma maneira de controlar o fluxo  envolve alterar os  pesos dos arcos da rede, podendo resultar em problemas de otimização que muitas vezes são difíceis de serem tratados computacionalmente.
Neste trabalho, estudamos propostas de soluções a determinados problemas que envolvem o controle do fluxo através da alteração de pesos nos arcos da rede de modo a redirecionar o fluxo para atingir determinados objetivos. Abordaremos dois problemas de controle de fluxo fazendo uso de instalação de pesos (pedágios) nos arcos.
Tais problemas são conhecidos como tollbooth problem e Stackelberg network pricing. No primeiro problema, dada uma rede de tráfego, o objetivo é instalar um número fixo K de postos de pedágio e definir suas tarifas de modo a reduzir o tempo médio de deslocamento dos usuários. No segundo problema, os arcos pedagiados são previamente conhecidos e o objetivo é definir os valores das tarifas de modo a maximizar o rendimento coletado nos postos de pedágios. Em ambos os casos supõe-se que o fluxo segue sempre pelo caminho mínimo, mesmo que este seja definido de diferentes modos. Assim, o objetivo deste trabalho é desenvolver métodos para obtenção de solução ótimas ou sub-ótimas para os problemas descritos fazendo uso de técnicas que hibridizem métodos exatos com heurísticos e proporcionem soluções de boa qualidade de modo eficiente.
Palavras-chave: Stackelberg network pricing, Matheurísticas, Otimização combinatória.

UNIVERSIDADE FEDERAL DO RIO GRANDE DO SUL
INSTITUTO DE INFORMÁTICA
PROGRAMA DE PÓS-GRADUAÇÃO EM COMPUTAÇÃO
———————————————-
DEFESA DE PROPOSTA DE TESE

Aluno: Fernando Stefanello
Orientadora: Profa. Dra. Luciana Salete Buriol
Coorientador: Dr. Mauricio Guilherme Carvalho Resende

Título: Otimização Combinatória 

Linha de Pesquisa: Fundamentos da Computação

Data: 06/12/2013
Horário: 13h
Local: Sala 220 (conselhos). Prédio 43412 – Instituto de Informática

Banca Examinadora:
Profa. Dra. Ana Lúcia Cetertich Bazzan (UFRGS)
Prof. Dr. Carlos Hoppen (UFRGS)
Prof. Dr. Geraldo Robson Mateus (UFMG)Profa. Dra. Márcia Helena Costa Fampa (UFRJ) 

Presidente da Banca: Profa. Dra. Luciana Salete Buriol

Resumo:
Problemas de fluxo em redes despertam muito interesse na comunidade científica e possuem inúmeras aplicações nas mais diferentes áreas de pesquisa, incluindo redes de transporte, telecomunicações e cadeias de suprimentos. Uma maneira de controlar o fluxo  envolve alterar os  pesos dos arcos da rede, podendo resultar em problemas de otimização que muitas vezes são difíceis de serem tratados computacionalmente. 

Neste trabalho, estudamos propostas de soluções a determinados problemas que envolvem o controle do fluxo através da alteração de pesos nos arcos da rede de modo a redirecionar o fluxo para atingir determinados objetivos. Abordaremos dois problemas de controle de fluxo fazendo uso de instalação de pesos (pedágios) nos arcos. 

Tais problemas são conhecidos como tollbooth problem e Stackelberg network pricing. No primeiro problema, dada uma rede de tráfego, o objetivo é instalar um número fixo K de postos de pedágio e definir suas tarifas de modo a reduzir o tempo médio de deslocamento dos usuários. No segundo problema, os arcos pedagiados são previamente conhecidos e o objetivo é definir os valores das tarifas de modo a maximizar o rendimento coletado nos postos de pedágios. Em ambos os casos supõe-se que o fluxo segue sempre pelo caminho mínimo, mesmo que este seja definido de diferentes modos. Assim, o objetivo deste trabalho é desenvolver métodos para obtenção de solução ótimas ou sub-ótimas para os problemas descritos fazendo uso de técnicas que hibridizem métodos exatos com heurísticos e proporcionem soluções de boa qualidade de modo eficiente. 

Palavras-chave: Stackelberg network pricing, Matheurísticas, Otimização combinatória.