Busca avançada
Ano de início
Entree

Algoritmos de aproximação para problemas de localização e alocação de terminais

Processo: 16/12006-1
Modalidade de apoio:Bolsas no Brasil - Mestrado
Vigência (Início): 01 de setembro de 2016
Vigência (Término): 28 de fevereiro de 2018
Área do conhecimento:Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
Pesquisador responsável:Lehilton Lelis Chaves Pedrosa
Beneficiário:Marcelo Pinheiro Leite Benedito
Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
Assunto(s):Algoritmos de aproximação   Otimização combinatória   Problemas de localização de facilidades
Palavra(s)-Chave do Pesquisador:Algoritmos de Aproximação | hub location problems | Algoritmos de Aproximação

Resumo

Algoritmos de aproximação são aplicados em problemas de otimização combinatória com o intuito de obter soluções garantidamente boas de maneira eficiente. O estudo desses algoritmos leva a resultados teóricos que permitem compreender as estruturas e dificuldades computacionais dos problemas tratados. Neste projeto, iremos investigar a classe de problemas de localização e alocação de terminais (hub-location problems, HLP), sobretudo sob a ótica de algoritmos de aproximação. Dado um conjunto de demandas entre pares origem-destino, o objetivo é identificar locais onde instalar terminais e associar a cada demanda um caminho passando por um ou mais terminais. Esses problemas ocorrem em situações em que é mais econômico rotear demandas através de terminais, a exemplo do que ocorre em malhas aeroportuárias. O objetivo desse trabalho é explorar técnicas de aproximação consolidadas para problemas localização tradicionais, como o Problema de Localização de Instalações, e aplicá-las aos HLPs, que ainda foram pouco explorados do ponto de vista de aproximação. Não se descarta a possibilidade de implementação de algoritmos ou heurísticas interessantes, seja para comparação de resultados ou melhor entendimento do problema. Especificamente, iremos considerar casos particulares, como o Problema de Média dos p-Terminais, com o objetivo de obter resultados de aproximação. (AU)

Matéria(s) publicada(s) na Agência FAPESP sobre a bolsa:
Mais itensMenos itens
Matéria(s) publicada(s) em Outras Mídias ( ):
Mais itensMenos itens
VEICULO: TITULO (DATA)
VEICULO: TITULO (DATA)

Publicações científicas
(Referências obtidas automaticamente do Web of Science e do SciELO, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores)
BENEDITO, MARCELO P. L.; PEDROSA, LEHILTON L. C.. Approximation algorithms for Median Hub Location Problems. JOURNAL OF COMBINATORIAL OPTIMIZATION, v. 38, n. 2, p. 375-401, . (16/12006-1, 15/11937-9)
Publicações acadêmicas
(Referências obtidas automaticamente das Instituições de Ensino e Pesquisa do Estado de São Paulo)
BENEDITO, Marcelo Pinheiro Leite. Approximation algorithms for hub location problems. 2018. Dissertação de Mestrado - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação Campinas, SP.

Por favor, reporte erros na lista de publicações científicas utilizando este formulário.