Limited range coverage problems

Tal como o título indica, esta tese estuda problemas de cobertura com alcance limitado. Dado um conjunto de antenas (ou qualquer outro dispositivo sem fios capaz de receber ou transmitir sinais), o objectivo deste trabalho é calcular o alcance mínimo das antenas de modo a que estas cubram completamente um caminho entre dois pontos numa região. Um caminho que apresente estas características é um itinerário seguro. A definição de cobertura é variável e depende da aplicação a que se destina. No caso de situações críticas como o controlo de fogos ou cenários militares, a definição de cobertura recorre à utilização de mais do que uma antena para aumentar a eficácia deste tipo de vigilância. No entanto, o alcance das antenas deverá ser minimizado de modo a manter a vigilância activa o maior tempo possível. Consequentemente, esta tese está centrada na resolução deste problema de optimização e na obtenção de uma solução particular para cada caso. Embora este problema de optimização tenha sido investigado como um problema de cobertura, é possível estabelecer um paralelismo entre problemas de cobertura e problemas de iluminação e vigilância, que são habitualmente designados como problemas da Galeria de Arte. Para converter um problema de cobertura num de iluminação basta considerar um conjunto de luzes em vez de um conjunto de antenas e submetê-lo a restrições idênticas. O principal tema do conjunto de problemas da Galeria de Arte abordado nesta tese é a 1-boa iluminação. Diz-se que um objecto está 1-bem iluminado por um conjunto de luzes se o invólucro convexo destas contém o objecto, tornando assim este conceito num tipo de iluminação de qualidade. O objectivo desta parte do trabalho é então minimizar o alcance das luzes de modo a manter uma iluminação de qualidade. São também apresentadas duas variantes da 1-boa iluminação: a iluminação ortogonal e a boa !-iluminação. Esta última tem aplicações em problemas de profundidade e visualização de dados, temas que são frequentemente abordados em estatística. A resolução destes problemas usando o diagrama de Voronoi Envolvente (uma variante do diagrama de Voronoi adaptada a problemas de boa iluminação) é também proposta nesta tese.

Location-routing problems of semi-obnoxious facilities: approaches and decision support

A presente tese resulta de um trabalho de investigação cujo objectivo se centrou no problema de localização-distribuição (PLD) que pretende abordar, de forma integrada, duas actividades logísticas intimamente relacionadas: a localização de equipamentos e a distribuição de produtos. O PLD, nomeadamente a sua modelação matemática, tem sido estudado na literatura, dando origem a diversas aproximações que resultam de diferentes cenários reais. Importa portanto agrupar as diferentes variantes por forma a facilitar e potenciar a sua investigação. Após fazer uma revisão e propor uma taxonomia dos modelos de localização-distribuição, este trabalho foca-se na resolução de alguns modelos considerados como mais representativos. É feita assim a análise de dois dos PLDs mais básicos (os problema capacitados com procura nos nós e nos arcos), sendo apresentadas, para ambos, propostas de resolução. Posteriormente, é abordada a localização-distribuição de serviços semiobnóxios. Este tipo de serviços, ainda que seja necessário e indispensável para o público em geral, dada a sua natureza, exerce um efeito desagradável sobre as comunidades contíguas. Assim, aos critérios tipicamente utilizados na tomada de decisão sobre a localização destes serviços (habitualmente a minimização de custo) é necessário adicionar preocupações que reflectem a manutenção da qualidade de vida das regiões que sofrem o impacto do resultado da referida decisão. A abordagem da localização-distribuição de serviços semiobnóxios requer portanto uma análise multi-objectivo. Esta análise pode ser feita com recurso a dois métodos distintos: não interactivos e interactivos. Ambos são abordados nesta tese, com novas propostas, sendo o método interactivo proposto aplicável a outros problemas de programação inteira mista multi-objectivo. Por último, é desenvolvida uma ferramenta de apoio à decisão para os problemas abordados nesta tese, sendo apresentada a metodologia adoptada e as suas principais funcionalidades. A ferramenta desenvolvida tem grandes preocupações com a interface de utilizador, visto ser direccionada para decisores que tipicamente não têm conhecimentos sobre os modelos matemáticos subjacentes a este tipo de problemas.