Busca avançada
Ano de início
Entree

Cobertura de pontos por elipses usando programação não linear

Processo: 10/18980-3
Linha de fomento:Auxílio à Pesquisa - Regular
Vigência: 01 de fevereiro de 2011 - 31 de janeiro de 2013
Área do conhecimento:Ciências Exatas e da Terra - Matemática - Matemática Aplicada
Pesquisador responsável:Marina Andretta
Beneficiário:Marina Andretta
Instituição-sede: Instituto de Ciências Matemáticas e de Computação (ICMC). Universidade de São Paulo (USP). São Carlos , SP, Brasil
Assunto(s):Elipse  Programação não linear 

Resumo

Problemas de cobertura maximal de pontos (MCLP - Maximal Covering Location Problems) surgem quando há recursos insuficientes para cobrir todos os pontos de demanda. Também surgem quando uma empresa busca maximizar o lucro para a cobertura selecionada. Qualquer ponto dentro da distância de cobertura é coberto e os demais pontos não são. O problema envolve implementar diferentes categorias de cobertura que possuem um custo específico associado a elas. O objetivo é cobrir os pontos que maximizam o lucro.Estamos interessados no problema de cobertura de pontos no plano por elipses: temos um conjunto de n pontos no plano (cada um com um peso associado), dispomos de um número m de elipses (cada uma com um custo associado à sua alocação) e desejamos alocar até k destas elipses de forma a cobrir os pontos no plano que tragam o maior lucro. O lucro é medido como a soma do peso dos pontos cobertos, subtraindo-se a soma dos custos das elipses alocadas.Há alguns métodos que podem ser usados para a resolução deste problema, vários dos quais empregam heurísticas e aproximações da solução. Estamos interessados em algoritmos exatos para solução do problema. Neste caso, faremos uma enumeração de subconjuntos das m elipses, com até k elementos. Para cada um destes subconjuntos, analisaremos quais pontos podem ser cobertos por estas elipses e encontraremos a melhor solução. Para descobrir onde posicionar uma elipse no plano de forma a cobrir um dado subconjunto de pontos (e se este posicionamento é possível), usaremos ALGENCAN, um método para resolver problemas de programação não linear.Estamos interessados também em desenvolver um método que considere o caso em que as elipses possuem tamanhos variáveis. Desta forma, o custo de sua alocação seria uma função de sua área. Um método para resolução deste problema mais genérico deve ser essencialmente diferente do método de enumeração mencionado acima. (AU)

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)
ANDRETTA, M.; BIRGIN, E. G. Deterministic and stochastic global optimization techniques for planar covering with ellipses problems. European Journal of Operational Research, v. 224, n. 1, p. 23-40, JAN 1 2013. Citações Web of Science: 0.

Por favor, reporte erros na lista de publicações científicas escrevendo para: cdi@fapesp.br.
Mapa da distribuição dos acessos desta página
Para ver o sumário de acessos desta página, clique aqui.