Uso de algoritmos genéticos em problemas de localização capacitada para alocação de recursos no campo e na cidade.

Problemas de localização. Descrição do algoritmo genético construtivo.

Sistemas de apoio à decisão para problemas de localização e roteamento.

O objetivo deste trabalho é mostrar os sistemas de apoio à decisão desenvolvidos para solucionar problemas de localização e roteamento, composto pelos novos enfoques de algoritmos de localização e roteamento e sistemas de informação geográfica Spring, Map Objects, Transcard e Arc View.

Desenvolvimento de ferramentas de apoio multicritério à decisão em problemas de localização

Tese de doutoramento, Estatística e Investigação Operacional (Análise de Sistemas), Universidade de Lisboa, Faculdade de Ciências, 2014

Um algoritmo de busca tabu para problemas de localização não capacitados

In this work, a tabu search algorithm for solving uncapacitated location problems is presented. The uncapacitated location problem is a classic problem of localization and occurs in many practical situations. The problem consists in determining in a network, at the minimum possible cost, the better localization, in a network, for the installation of facilities in order to attend the customers' associated demands, at the minimum possible cost. One admits that there exists a cost associated with the opening of a facility and a cost of attendance of each customer by any open facilities. In the particular case of the uncapacitated location problem there is no capacity limitation to attend the customers’ demands. There are some parameters in the algorithm that influence the solution’s quality. These parameters were tested and optimal values for them were obtained. The results show that the proposed algorithm is able to find the optimal solution for all small tested problems keeping the compromise between solution’s quality and computational time. However, to solve bigger problems, the structure of the algorithm must be changed in its structure. The implemented algorithm is integrated to a computational platform for solution of logistic problems

Contribuições para a localização e mapeamento em robótica através da identificação visual de lugares

Tese de doutoramento, Informática (Engenharia Informática), Universidade de Lisboa, Faculdade de Ciências, 2015

Determinação da localização, dimensionamento e número ótimo de unidades industriais

O presente trabalho tem como objetivo definir uma sistemática para a abordagem de problemas de localização e dimensionamento de unidades industriais ou serviços, procurando basicamente enfatizar o progresso alcançado na formulação de modelos, bem como destacar as principais técnicas desenvolvidas para a solução desses modelos. Com o intuito de fornecer maiores subsídios ao estudo da localização industrial, desenvolveram-se neste trabalho, através do estudo de um caso, todas as etapas que envolvem a resolução de um problema real como forma de avaliar a viabilidade da utilização dos modelos e técnicas existentes na literatura.

Abordagens complementares para problemas de p-medianas

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Integração de modelos de localização a sistemas de informações geográficas

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

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.

Tecnicas de sensoriamento remoto e geoprocessamento aplicadas ao mapeamento geologico e geotecnico no municipio de Tres Cachoeiras, litoral norte do Rio Grande do Sul

As técnicas de sensoriarnento remoto e geoprocessamento são fundamentais para processamento e integração de dados de mapeamento geológico/geotécnico, principalmente estudos de gerenciamento e planejamento. A área estudada compreende o município de Três Cachoeiras. Litoral Norte do Rio Grande do Sul o qual inclui-se na "Reserva da Biosfera da Mata Atlântica". O município tem st: deparado com problemas de localização de sitios adequados à disposição final dos resíduos sólidos. bem como o assentamento de loteamentos residenciais e industriais, localização de jazidas de extração de material para construção, fontes de abastecimento de água e necessidade de criação de áreas de preservação ambiental. O objetivo deste trabalho foi produzir mapeamentos da área em questão, através da pesquisa geológico-geotécnica desenvolvida com emprego de imagens de satélite e fotografias aéreas, em que as informações foram cruzadas no SIG. Baseado nisto, investigaram-se os aspectos acima mencionados. a partir de uma contribuição geológico/geotécnica ao município, incluindo-se levantamento de campo, fotointerpretação, processamento e classificação de imagens do município de Três Cachoeiras, sendo os dados integrados num sistema de geoprocessamento. Utilizando-se cartas planialtimétricas, fotografias aéreas e imagem de satélite LANDSAT TM5. foram criados planos de informação como o limite da área estudada, a estrutura viária municipal, a delimitação de reservas ecológicas baseadas na legislação ambiental vigente e, por meio do modelo numérico do terreno, a carta de declividade. A fotointerpretação gerou planos de rede de drenagem, litológica. morfoestruturas e formações superficiais. Os dados de campo. sobrepostos às litológicas obtidas por fotointerpretação, produziram a carta litológica. No tratamento das imagem, foram gerados produtos com contraste, operações entre bandas, filtragens e análise de componentes principais, os quais contribuíram parira classificação da imagem e resultando nos planos de rochas/solos e cobertura/uso do solo (carta de uso atual do solo). O cruzamento destas informações permitiu a obtenção da carta de formações superficiais, lidrogeológica que, juntamente com as cartas litológica, declividades e uso atual do solo distribuíram os atributos do meio físico em planos elaborados por novos cruzamentos, que satisfazem o objetivo do estudo, sendo estes planos o produto final, ou seja, cartas de recomendação: a extração de materiais para construção civil; a implantação de obras de infraestrutura; a disposição de resíduos sólidos e loteamentos; geotécnica à agricultura; à implantação de áreas destinadas à preservação ambienta1 e recuperação.

Dois testes de imageamento com GPR em problemas de controle ambiental em regiões tropicais: migração de dunas e localização de dutos de óleo enterrados

Because the penetration depth of Ground Penetrating Radar (GPR) signals is very limited in high conductive soils, the usefullness of this method in tropical regions is not yet completly known. The main objective of this researh is to test the usefullness of the method in Brazil. Two typical problems where GPR has been used in Europe and North American were choosed for this test: the first one is to characterize the internal structures of a sand body and the second problem is the localization of old buried pipes lines. The first test was done near the city of São Bento do Norte, in the northern coast of Rio Grande do Norte state, NE Brazil. In this region, there is a sand dune that is migrating very fast in the direction of adjacent settling areas. To characterize the internal structure of the dune and its relationship to the prevailing wind direction, as a preliminary step to understand the dune migration, GPR profiles using the 400 MHz frequency were performed in E-W, N-S, NE-SW, and SE-NW directions over the sand dune intersecting at the top of the dune. The practical resolution of the GPR data is around 30 cm; this was sufficient to distinguish individual foresets inside the dune. After applying the elevation correction to the data, we identified that dips of bedding structures are smallest for the N-S profile, which is perpendicular to the dominant wind direction, largest for the E-W profile, and intermediate for the SW-NE and SE-NW profiles. Foresets in the E-W profile dip with angles varying from 2 to 6 degrees. In the E-W profile, the water table and a horizontal truncation interface separating two generations of dunes were identified, as well as an abrupt directional change in the foreset patterns associated to a lateral contact between two dune generations, the older one extending to the west. The used high frequency of 400 Mhz does not allow a penetration deep enough to map completely these internal contacts. The second test was done near Estreito, a small town near Carnaúbais city, also in Rio Grande do Norte state. In this locality, there are several old pipe lines buried in area covered by plantations where digging should be minimized. Several GPR profiles using the 400 and 200 MHz frequency were performed trying to intercept perpendicularly the possible pipe lines. Because of the high conductivity of the soil, the raw original data can hardly be use to identify the pipe lines. However, after an adequate processing over the 200 MHz profiles, six pipe lines were identified. As a global result of the tests, GPR can be very usefull if the conductivity of the ground is low or, in the case of medium conductivities of the soils, if adequate processing is performed

Determinação de uma fonte de contaminantes no estuário do Rio Macaé através da técnica de problemas inversos

Um grande desafio da atualidade é a preservação dos recursos hídricos, bem como o correto manejo dos mesmos, frente à expansão das cidades e às atividades humanas. A qualidade de um corpo hídrico é usualmente avaliada através da análise de parâmetros biológicos, físicos e químicos. O comportamento de tais parâmetros pode convenientemente ser simulado através de modelos matemáticos e computacionais, que surgem assim como uma ferramenta bastante útil, por sua capacidade de geração de cenários que possam embasar, por exemplo, tomadas de decisão. Nesta tese são discutidas técnicas de estimação da localização e intensidade de uma fonte de contaminante conservativo, hipoteticamente lançado na região predominantemente fluvial de um estuário. O lançamento aqui considerado se dá de forma pontual e contínua e a região enfocada compreendeu o estuário do Rio Macaé, localizado na costa norte do Rio de Janeiro. O trabalho compreende a solução de um problema direto, que consiste no transporte bidimensional (integrado na vertical) desse contaminante hipotético, bem como a aplicação de técnicas de problemas inversos. Para a solução do transporte do contaminante, aqui modelada pela versão 2D horizontal da equação de advecção-difusão, foram utilizados como métodos de discretização o Método de Elementos Finitos e o Método de Diferenças Finitas. Para o problema hidrodinâmico foram utilizados dados de uma solução já desenvolvida para estuário do Rio Macaé. Analisada a malha de acordo com o método de discretização, foram definidas a geometria do estuário e os parâmetros hidrodinâmicos e de transporte. Para a estimação dos parâmetros propostos foi utilizada a técnica de problemas inversos, com o uso dos métodos Luus-Jaakola, Algoritmo de Colisão de Partículas e Otimização por Colônia de Formigas para a estimação da localização e do método Seção Áurea para a estimação do parâmetro de intensidade da fonte. Para a definição de uma fonte, com o objetivo de propor um cenário experimental idealizado e de coleta de dados de amostragem, foi realizada a análise de sensibilidade quanto aos parâmetros a serem estimados. Como os dados de amostragem de concentração foram sintéticos, o problema inverso foi resolvido utilizando-os com e sem ruído, esse introduzido de forma artificial e aleatória. Sem o uso de ruído, os três métodos mostraram-se igualmente eficientes, com uma estimação precisa em 95% das execuções. Já com o uso de dados de amostragem com ruídos de 5%, o método Luus-Jaakola mostrou-se mais eficiente em esforço e custo computacional, embora todos tenham estimado precisamente a fonte em 80% das execuções. Considerando os resultados alcançados neste trabalho tem-se que é possível estimar uma fonte de constituintes, quanto à sua localização e intensidade, através da técnica de problemas inversos. Além disso, os métodos aplicados mostraram-se eficientes na estimação de tais parâmetros, com estimações precisas para a maioria de suas execuções. Sendo assim, o estudo do comportamento de contaminantes, e principalmente da identificação de fontes externas, torna-se uma importante ferramenta para a gestão dos recursos hídricos, possibilitando, inclusive, a identificação de possíveis responsáveis por passivos ambientais.

Localização colaborativa em robótica de enxame.

Diversas das possíveis aplicações da robótica de enxame demandam que cada robô seja capaz de estimar a sua posição. A informação de localização dos robôs é necessária, por exemplo, para que cada elemento do enxame possa se posicionar dentro de uma formatura de robôs pré-definida. Da mesma forma, quando os robôs atuam como sensores móveis, a informação de posição é necessária para que seja possível identificar o local dos eventos medidos. Em virtude do tamanho, custo e energia dos dispositivos, bem como limitações impostas pelo ambiente de operação, a solução mais evidente, i.e. utilizar um Sistema de Posicionamento Global (GPS), torna-se muitas vezes inviável. O método proposto neste trabalho permite que as posições absolutas de um conjunto de nós desconhecidos sejam estimadas, com base nas coordenadas de um conjunto de nós de referência e nas medidas de distância tomadas entre os nós da rede. A solução é obtida por meio de uma estratégia de processamento distribuído, onde cada nó desconhecido estima sua própria posição e ajuda os seus vizinhos a calcular as suas respectivas coordenadas. A solução conta com um novo método denominado Multi-hop Collaborative Min-Max Localization (MCMM), ora proposto com o objetivo de melhorar a qualidade da posição inicial dos nós desconhecidos em caso de falhas durante o reconhecimento dos nós de referência. O refinamento das posições é feito com base nos algoritmos de busca por retrocesso (BSA) e de otimização por enxame de partículas (PSO), cujos desempenhos são comparados. Para compor a função objetivo, é introduzido um novo método para o cálculo do fator de confiança dos nós da rede, o Fator de Confiança pela Área Min-Max (MMA-CF), o qual é comparado com o Fator de Confiança por Saltos às Referências (HTA-CF), previamente existente. Com base no método de localização proposto, foram desenvolvidos quatro algoritmos, os quais são avaliados por meio de simulações realizadas no MATLABr e experimentos conduzidos em enxames de robôs do tipo Kilobot. O desempenho dos algoritmos é avaliado em problemas com diferentes topologias, quantidades de nós e proporção de nós de referência. O desempenho dos algoritmos é também comparado com o de outros algoritmos de localização, tendo apresentado resultados 40% a 51% melhores. Os resultados das simulações e dos experimentos demonstram a eficácia do método proposto.

Análise de desempenho de um protocolo BitTorrent ciente de localização em redes corporativas.

Hoje em dia, distribuições de grandes volumes de dados por redes TCP/IP corporativas trazem problemas como a alta utilização da rede e de servidores, longos períodos para conclusão e maior sensibilidade a falhas na infraestrutura de rede. Estes problemas podem ser reduzidos com utilização de redes par-a-par (P2P). O objetivo desta dissertação é analisar o desempenho do protocolo BitTorrent padrão em redes corporativas e também realizar a análise após uma modificação no comportamento padrão do protocolo BitTorrent. Nesta modificação, o rastreador identifica o endereço IP do par que está solicitando a lista de endereços IP do enxame e envia somente aqueles pertencentes à mesma rede local e ao semeador original, com o objetivo de reduzir o tráfego em redes de longa distância. Em cenários corporativos típicos, as simulações mostraram que a alteração é capaz de reduzir o consumo médio de banda e o tempo médio dos downloads, quando comparados ao BitTorrent padrão, além de conferir maior robustez à distribuição em casos de falhas em enlaces de longa distância. As simulações mostraram também que em ambientes mais complexos, com muitos clientes, e onde a restrição de banda em enlaces de longa distância provoca congestionamento e descartes, o desempenho do protocolo BitTorrent padrão pode ser semelhante a uma distribuição em arquitetura cliente-servidor. Neste último caso, a modificação proposta mostrou resultados consistentes de melhoria do desempenho da distribuição.

Otimização do problema de localização de instalações aplicado ao comércio e distribuição de combustíveis

Um dos problemas mais relevantes em organizações de grande porte é a escolha de locais para instalação de plantas industriais, centros de distribuição ou mesmo pontos comerciais. Esse problema logístico é uma decisão estratégica que pode causar um impacto significativo no custo total do produto comercializado. Existem na literatura diversos trabalhos que abordam esse problema. Assim, o objetivo desse trabalho é analisar o problema da localização de instalações proposto por diferentes autores e definir um modelo que seja o mais adequado possível ao mercado de distribuição de combustíveis no Brasil. Para isso, foi realizada uma análise do fluxo de refino e distribuição praticado neste segmento e da formação do respectivo custo de transporte. Foram consideradas restrições como capacidade de estoque, gama de produtos ofertados e níveis da hierarquia de distribuição. A partir dessa análise, foi definido um modelo matemático aplicado à redução dos custos de frete considerando-se a carga tributária. O modelo matemático foi implementado, em linguagem C, e permite simular o problema. Foram aplicadas técnicas de computação paralela visando reduzir o tempo de execução do algoritmo. Os resultados obtidos com o modelo Single Uncapacited Facility Location Problem (SUFLP) simulado nas duas versões do programa, sequencial e paralela, demonstram ganhos de até 5% em economia de custos e redução do tempo de execução em mais de 50%.