Banca de DEFESA: PAULO HENRIQUE ASCONAVIETA DA SILVA

Uma banca de DEFESA de DOUTORADO foi cadastrada pelo programa.
DISCENTE: PAULO HENRIQUE ASCONAVIETA DA SILVA
DATA: 19/12/2011
HORA: 08:30
LOCAL: Sala de Reunião do DIMAp
TÍTULO:

O Problema do Caixeiro Viajante com Alugueis de Carros: Um Estudo Algorítmico


PALAVRAS-CHAVES:

O Problema do Caixeiro Viajante com Aluguel de Carros. O Problema do Caixeiro Alugador. Metaheurísticas. GRASP/VNS. Colônia de Formigas. Transgenética Computacional.


PÁGINAS: 250
GRANDE ÁREA: Ciências Exatas e da Terra
ÁREA: Ciência da Computação
SUBÁREA: Teoria da Computação
ESPECIALIDADE: Análise de Algoritmos e Complexidade de Computação
RESUMO:

O Problema do Caixeiro Viajante com Aluguel de Carros – o Caixeiro Alugador (PCA) é uma variante ainda não descrita na literatura do clássico Problema do Caixeiro Viajante onde seu tour de visitas pode ser decomposto em caminhos contíguos e que podem ser realizados em diferentes carros alugados. O problema consiste em determinar o ciclo hamiltoniano que resulte em um custo final mínimo, considerado o custo da rota adicionado ao custo de uma provável penalização paga em cada troca de veículos na rota, penalização devida ao retorno do carro descartado até a sua base. O presente trabalho descreve o problema geral e o exemplifica, caracterizando igualmente algumas variantes associadas. Uma formulação matemática é sugerida para um dos casos descritos. Uma análise geral da complexidade desse problema combinatório também é esboçada, visando justificar sua classificação na classe NP-difícil. Um banco de instâncias para o problema é sugerido, descrevendo-se a metodologia de sua constituição. O problema proposto também é objeto de um estudo algorítmico experimental baseado na aplicação de três metaheurísticas de solução. Com base nessas metáforas, são desenvolvidos três algoritmos associados e apresentados resultados computacionais do teste desses protótipos sobre uma amostra de 40 diferentes instâncias do banco criado. Tendo em vista o experimento, a presente proposta propõe duas linhas de melhoria para os algoritmos desenvolvidos ao longo de um cronograma que cobre dezoito meses de pesquisa. Ao final as conclusões da pesquisa são firmadas de forma a sustentar sua viabilidade tanto em tempo quanto no que diz respeito ao mérito.


MEMBROS DA BANCA:
Presidente - 1149561 - MARCO CESAR GOLDBARG
Interno - 1350250 - ANNE MAGALY DE PAULA CANUTO
Interno - 1201268 - ELIZABETH FERREIRA GOUVEA
Interno - 1345816 - REGIVAN HUGO NUNES SANTIAGO
Externo à Instituição - HENRIQUE PACCA LOUREIRO LUNA - UFAL
Externo à Instituição - MYRIAM REGATTIERI DE BIASE DA SILVA DELGADO - UTFPR
Notícia cadastrada em: 27/01/2012 10:51
SIGAA | Superintendência de Informática - (84) 3215-3148 | Copyright © 2006-2019 - UFRN - sigaa07-producao.info.ufrn.br.sigaa07-producao