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.

Rural engineering infrastructures design and public facility locations

O desenvolvimento das redes de estradas rurais, especialmente em áreas montanhosas, é a intervenção chave para melhorar a acessibilidade às localidades e aos serviços públicos, cobrindo o maior número de localidades e de serviços públicos, otimizando os escassos recursos disponíveis em países em desenvolvimento. Este estudo explora diferentes modelos de organização de redes de estradas rurais considerando a construção de novas ligações ou o melhoramento de estradas existentes. Um método, baseado na cobertura da rede de estradas rurais, é utilizado para identificar os pontos nodais que formam a rede rural base numa específica região, a qual cobrirá um conjunto dos serviços públicos e de localidades. O modelo assenta numa rede rural de estradas típica ("backbone" e "branch") das regiões montanhosas do Nepal. Os modelos propostos fornecem um conjunto de possibilidades de ligações a estabelecer ou a melhorar e oferece soluções para diferentes níveis de orçamento, que otimizam os custos de transporte na rede, considerando diferentes tipos de pavimento (em solo, granular ou asfáltico). Foi realizado separadamente um modelo dedicado a análises multi-objetivo para resolver problemas de melhoramento de ligações dentro da rede considerando dois objectivos, minimizar os custos de operação para o utilizador e maximizar a população coberta pela rede de estradas, considerando ligações pavimentadas e não pavimentadas (em solo, granular ou asfáltico) dentro de um determinado limite orçamental. O modelo dá ao decisor (DM) diferentes alternativas eficientes para que este possa tomar uma decisão final. Estes modelos, desenvolvidos para redes de estradas rurais, são também aplicáveis a outras redes de infraestruturas rurais, tais como, de fornecimento de água, de eletricidade e de telecomunicações. A implementação dos modelos nas redes de estradas rurais dos distritos de Gorkha e Lamjung do Nepal permitiu confirmara sua aplicabilidade. Verifica-se que os modelos propostos são mais práticos e realísticos no estudo de soluções de melhoramento e de desenvolvimento de redes de estradas rurais em regiões montanhosas de países em desenvolvimento.

Advanced optical modulation and format conversion

Over the years, the increased search and exchange of information lead to an increase of traffic intensity in todays optical communication networks. Coherent communications, using the amplitude and phase of the signal, reappears as one of the transmission techniques to increase the spectral efficiency and throughput of optical channels. In this context, this work present a study on format conversion of modulated signals using MZI-SOAs, based exclusively on all- optical techniques through wavelength conversion. This approach, when applied in interconnection nodes between optical networks with different bit rates and modulation formats, allow a better efficiency and scalability of the network. We start with an experimental characterization of the static and dynamic properties of the MZI-SOA. Then, we propose a semi-analytical model to describe the evolution of phase and amplitude at the output of the MZI-SOA. The model’s coefficients are obtained using a multi-objective genetic algorithm. We validate the model experimentally, by exploring the dependency of the optical signal with the operational parameters of the MZI-SOA. We also propose an all-optical technique for the conversion of amplitude modulation signals to a continuous phase modulation format. Finally, we study the potential of MZI-SOAs for the conversion of amplitude signals to QPSK and QAM signals. We show the dependency of the conversion process with the operational parameters deviation from the optimal values. The technique is experimentally validated for QPSK modulation.

Multi-scale dynamics on the Eastern Brazilian margin

Este trabalho combina esforços de simulação numérica e de análise de dados para investigar a dinâmica em diversos compartimentos (oceano aberto, plataforma continental e zona costeira-estuarina) e, em multiplas escalas, na Margem Continental Leste Brasileira (MCLB). A circulação de largo e mesoescala espacial e a propagação da maré barotrópica são investigadas através de uma configuração aninhada do modelo numérico ROMS. O estudo da dinâmica regional da Baía de Camamu (CMB) baseia-se na análise de dados locais. A MCLB, localizada a SW do Atlântico Sul entre 8±S e 20±S, possui plataforma estreita, batimetria complexa, e baixa produtividade primária. A sua dinâmica é influenciada pela divergência da Corrente Sul Equatorial (CSE). As simulações refletem as conexões sazonais e espaciais entre a Corrente do Brasil e a Contra Corrente Norte do Brasil , em conexão com a dinâmica da CSE. As simulações revelam atividades vorticais nas proximidades da costa e interações com a dinâmica costeira, cujos padrões são descritos. A validação do modelo em mesoescala é baseada em cálculos de energia cinética turbulenta e em dados históricos de transporte. A CMB, localizada a 13±400S, abriga uma comunidade piscatória tradicional e extenso de manguezal. Situa-se porém sobre uma bacia sedimentar com grande reservas de óleo e gás, estando em tensão permanente de impacto ambiental. Neste trabalho sumarizamos as condições físicas regionais e investigamos sua dinâmica interna, focando sua variabilidade em amostragens realizadas sob condições de seca (Setembro de 2004) e de chuva (Julho de 2005). Finalmente, o modelo numérico ROMS é forçado com o sinal de maré, empregando-se uma configuração simples (com coeficientes de atrito de fundo constantes e condições hidrográficas homogéneas), com o intuito de avaliar sua resposta e investigar a natureza da propagação da maré barotrópica na MCLB, convergindo na CMB. A análise da resposta do modelo à maré basea-se em séries históricas do nível do mar para a MCLB e dados recentes da CMB.

Geometric optimization on visibility problems: metaheuristic and exact solutions

Os problemas de visibilidade têm diversas aplicações a situações reais. Entre os mais conhecidos, e exaustivamente estudados, estão os que envolvem os conceitos de vigilância e ocultação em estruturas geométricas (problemas de vigilância e ocultação). Neste trabalho são estudados problemas de visibilidade em estruturas geométricas conhecidas como polígonos, uma vez que estes podem representar, de forma apropriada, muitos dos objectos reais e são de fácil manipulação computacional. O objectivo dos problemas de vigilância é a determinação do número mínimo de posições para a colocação de dispositivos num dado polígono, de modo a que estes dispositivos consigam “ver” a totalidade do polígono. Por outro lado, o objectivo dos problemas de ocultação é a determinação do número máximo de posições num dado polígono, de modo a que quaisquer duas posições não se consigam “ver”. Infelizmente, a maior parte dos problemas de visibilidade em polígonos são NP-difíceis, o que dá origem a duas linhas de investigação: o desenvolvimento de algoritmos que estabelecem soluções aproximadas e a determinação de soluções exactas para classes especiais de polígonos. Atendendo a estas duas linhas de investigação, o trabalho é dividido em duas partes. Na primeira parte são propostos algoritmos aproximados, baseados essencialmente em metaheurísticas e metaheurísticas híbridas, para resolver alguns problemas de visibilidade, tanto em polígonos arbitrários como ortogonais. Os problemas estudados são os seguintes: “Maximum Hidden Vertex Set problem”, “Minimum Vertex Guard Set problem”, “Minimum Vertex Floodlight Set problem” e “Minimum Vertex k-Modem Set problem”. São também desenvolvidos métodos que permitem determinar a razão de aproximação dos algoritmos propostos. Para cada problema são implementados os algoritmos apresentados e é realizado um estudo estatístico para estabelecer qual o algoritmo que obtém as melhores soluções num tempo razoável. Este estudo permite concluir que as metaheurísticas híbridas são, em geral, as melhores estratégias para resolver os problemas de visibilidade estudados. Na segunda parte desta dissertação são abordados os problemas “Minimum Vertex Guard Set”, “Maximum Hidden Set” e “Maximum Hidden Vertex Set”, onde são identificadas e estudadas algumas classes de polígonos para as quais são determinadas soluções exactas e/ou limites combinatórios.

Cooperative communications in multi-rate IEEE 802.11 networks

Esta tese apresenta um estudo sobre alguns dos protocolos de cooperação MAC para redes sem fios utilizando o sistema IEEE 802.11 multi-débito. É proposto um novo modelo de arquitetura para a categorização e análise da cooperação em redes sem fios, tendo este modelo sido aplicado a protocolos cooperativos existentes para camada MAC. É investigado como as características do meio físico, assim como os requisitos de níveis superiores podem ser aplicados ao processo de cooperação, com vista a melhorar as características de funcionamento da rede de comunicações. Para este propósito são exploradas as métricas mais relevantes para o processo de cooperação. São igualmente estudados os limites impostos pelos protocolos da camada MAC e as limitações práticas impostas por protocolos da família de normas que compõem o IEEE 802.11. Neste trabalho foi criada uma métrica multicamada, que permite considerar os requisitos aplicacionais de performance e o tipo de tráfego, assim como a mobilidade dos dispositivos, no funcionamento dos mecanismos de cooperação. Como forma de validação, e para corretamente avaliar o impacto da métrica, um novo protocolo de cooperação foi desenvolvido e implementado. O seu funcionamento é descrito de forma analítica assim como validado através de a um ambiente de simulação. Os resultados obtidos mostram que a utilização de uma métrica multicamada é uma técnica robusta, fornecendo melhorias consistentes no contexto de redes IEEE 802.11. São igualmente demonstradas várias outras características de funcionamento com impacto para as comunicações. Estes dados fornecem uma visão real e encorajadora para a realização de mais pesquisas para a melhoria da performance dos protocolos cooperativos, assim como a sua utilização num variado número de aplicações futuras. No final do documento são apresentados alguns desafios para a continuação da investigação deste tópico.

Development of numerical methodologies for parameter identification and shape optimization in metal forming simulations

Por parte da indústria de estampagem tem-se verificado um interesse crescente em simulações numéricas de processos de conformação de chapa, incluindo também métodos de engenharia inversa. Este facto ocorre principalmente porque as técnicas de tentativa-erro, muito usadas no passado, não são mais competitivas a nível económico. O uso de códigos de simulação é, atualmente, uma prática corrente em ambiente industrial, pois os resultados tipicamente obtidos através de códigos com base no Método dos Elementos Finitos (MEF) são bem aceites pelas comunidades industriais e científicas Na tentativa de obter campos de tensão e de deformação precisos, uma análise eficiente com o MEF necessita de dados de entrada corretos, como geometrias, malhas, leis de comportamento não-lineares, carregamentos, leis de atrito, etc.. Com o objetivo de ultrapassar estas dificuldades podem ser considerados os problemas inversos. No trabalho apresentado, os seguintes problemas inversos, em Mecânica computacional, são apresentados e analisados: (i) problemas de identificação de parâmetros, que se referem à determinação de parâmetros de entrada que serão posteriormente usados em modelos constitutivos nas simulações numéricas e (ii) problemas de definição geométrica inicial de chapas e ferramentas, nos quais o objetivo é determinar a forma inicial de uma chapa ou de uma ferramenta tendo em vista a obtenção de uma determinada geometria após um processo de conformação. São introduzidas e implementadas novas estratégias de otimização, as quais conduzem a parâmetros de modelos constitutivos mais precisos. O objetivo destas estratégias é tirar vantagem das potencialidades de cada algoritmo e melhorar a eficiência geral dos métodos clássicos de otimização, os quais são baseados em processos de apenas um estágio. Algoritmos determinísticos, algoritmos inspirados em processos evolucionários ou mesmo a combinação destes dois são usados nas estratégias propostas. Estratégias de cascata, paralelas e híbridas são apresentadas em detalhe, sendo que as estratégias híbridas consistem na combinação de estratégias em cascata e paralelas. São apresentados e analisados dois métodos distintos para a avaliação da função objetivo em processos de identificação de parâmetros. Os métodos considerados são uma análise com um ponto único ou uma análise com elementos finitos. A avaliação com base num único ponto caracteriza uma quantidade infinitesimal de material sujeito a uma determinada história de deformação. Por outro lado, na análise através de elementos finitos, o modelo constitutivo é implementado e considerado para cada ponto de integração. Problemas inversos são apresentados e descritos, como por exemplo, a definição geométrica de chapas e ferramentas. Considerando o caso da otimização da forma inicial de uma chapa metálica a definição da forma inicial de uma chapa para a conformação de um elemento de cárter é considerado como problema em estudo. Ainda neste âmbito, um estudo sobre a influência da definição geométrica inicial da chapa no processo de otimização é efetuado. Este estudo é realizado considerando a formulação de NURBS na definição da face superior da chapa metálica, face cuja geometria será alterada durante o processo de conformação plástica. No caso dos processos de otimização de ferramentas, um processo de forjamento a dois estágios é apresentado. Com o objetivo de obter um cilindro perfeito após o forjamento, dois métodos distintos são considerados. No primeiro, a forma inicial do cilindro é otimizada e no outro a forma da ferramenta do primeiro estágio de conformação é otimizada. Para parametrizar a superfície livre do cilindro são utilizados diferentes métodos. Para a definição da ferramenta são também utilizados diferentes parametrizações. As estratégias de otimização propostas neste trabalho resolvem eficientemente problemas de otimização para a indústria de conformação metálica.

Economic optimization of wind farms in function of the cost of energy produced

Esta tese apresenta um estudo sobre otimização económica de parques eólicos, com o objetivo de obter um algoritmo para otimização económica de parques eólicos através do custo da energia produzida. No estudo utilizou-se uma abordagem multidisciplinar. Inicialmente, apresentam-se as principais tecnologias e diferentes arquiteturas utilizadas nos parques eólicos. Bem como esquemas de funcionamento e gestão dos parques. São identificadas variáveis necessárias e apresenta-se um modelo dimensionamento para cálculo dos custos da energia produzida, tendo-se dado ênfase às instalações onshore e ligados a rede elétrica de distribuição. É feita uma análise rigorosa das características das topologias dos aerogeradores disponíveis no mercado, e simula-se o funcionamento de um parque eólico para testar a validade dos modelos desenvolvidos. Também é implementado um algoritmo para a obtenção de uma resposta otimizada para o ciclo de vida económico do parque eólico em estudo. A abordagem proposta envolve algoritmos para otimização do custo de produção com multiplas funções objetivas com base na descrição matemática da produção de eletricidade. Foram desenvolvidos modelos de otimização linear, que estabelece a ligação entre o custo económico e a produção de eletricidade, tendo em conta ainda as emissões de CO2 em instrumentos de política energética para energia eólica. São propostas expressões para o cálculo do custo de energia com variáveis não convencionais, nomeadamente, para a produção variável do parque eólico, fator de funcionamento e coeficiente de eficiência geral do sistema. Para as duas últimas, também é analisado o impacto da distribuição do vento predominante no sistema de conversão de energia eólica. Verifica-se que os resultados obtidos pelos algoritmos propostos são similares às obtidas por demais métodos numéricos já publicados na comunidade científica, e que o algoritmo de otimização económica sofre influência significativa dos valores obtidos dos coeficientes em questão. Finalmente, é demonstrado que o algoritmo proposto (LCOEwso) é útil para o dimensionamento e cálculo dos custos de capital e O&M dos parques eólicos com informação incompleta ou em fase de projeto. Nesse sentido, o contributo desta tese vem ser desenvolver uma ferramenta de apoio à tomada de decisão de um gestor, investidor ou ainda agente público em fomentar a implantação de um parque eólico.

Injection moulding process optimization for microstructured parts production

Ao longo das últimas décadas, a micromoldação (u-moldação) por injeção de termoplásticos ganhou um lugar de destaque no mercado de equipamentos eletrónicos e de uma ampla gama de componentes mecânicos. No entanto, quando o tamanho do componente diminui, os pressupostos geralmente aceites na moldação por injeção convencional deixam de ser válidos para descrever o comportamento reológico e termomecânico do polímero na microimpressão. Por isso, a compreensão do comportamento dinâmico do polímero à escala micro bem como da sua caraterização, análise e previsão das propriedades mecânicas exige uma investigação mais alargada. O objetivo principal deste programa doutoral passa por uma melhor compreensão do fenómeno físico intrínseco ao processo da μ-moldação por injeção. Para cumprir com o objetivo estabelecido, foi efetuado um estudo paramétrico do processo de μ-moldação por injeção, cujos resultados foram comparados com os resultados obtidos por simulação numérica. A caracterização dinâmica mecânica das μ-peças foi efetuada com o objetivo de recolher os dados necessários para a previsão do desempenho mecânico das mesmas, a longo prazo. Finalmente, depois da calibração do modelo matemático do polímero, foram realizadas análises estruturais com o intuito de prever o desempenho mecânico das μ-peças no longo prazo. Verificou-se que o desempenho mecânico das μ-peças pode ser significativamente afetado pelas tensões residuais de origem mecânica e térmica. Estas últimas, resultantes do processo de fabrico e das condições de processamento, por isso, devem ser consideradas na previsão do desempenho mecânico e do tempo de serviço das u-moldações.

Analysis, modeling, design and optimization of future communications systems: from theory to practice

Esta tese descreve uma framework de trabalho assente no paradigma multi-camada para analisar, modelar, projectar e optimizar sistemas de comunicação. Nela se explora uma nova perspectiva acerca da camada física que nasce das relações entre a teoria de informação, estimação, métodos probabilísticos, teoria da comunicação e codificação. Esta framework conduz a métodos de projecto para a próxima geração de sistemas de comunicação de alto débito. Além disso, a tese explora várias técnicas de camada de acesso com base na relação entre atraso e débito para o projeto de redes sem fio tolerantes a atrasos. Alguns resultados fundamentais sobre a interação entre a teoria da informação e teoria da estimação conduzem a propostas de um paradigma alternativo para a análise, projecto e optimização de sistemas de comunicação. Com base em estudos sobre a relação entre a informação recíproca e MMSE, a abordagem descrita na tese permite ultrapassar, de forma inovadora, as dificuldades inerentes à optimização das taxas de transmissão de informação confiáveis em sistemas de comunicação, e permite a exploração da atribuição óptima de potência e estruturas óptimas de pre-codificação para diferentes modelos de canal: com fios, sem fios e ópticos. A tese aborda também o problema do atraso, numa tentativa de responder a questões levantadas pela enorme procura de débitos elevados em sistemas de comunicação. Isso é feito através da proposta de novos modelos para sistemas com codificação de rede (network coding) em camadas acima da sua camada física. Em particular, aborda-se a utilização de sistemas de codificação em rede para canais que variam no tempo e são sensíveis a atrasos. Isso foi demonstrado através da proposta de um novo modelo e esquema adaptativo, cujos algoritmos foram aplicados a sistemas sem fios com desvanecimento (fading) complexo, de que são exemplos os sistemas de comunicação via satélite. A tese aborda ainda o uso de sistemas de codificação de rede em cenários de transferência (handover) exigentes. Isso é feito através da proposta de novos modelos de transmissão WiFi IEEE 801.11 MAC, que são comparados com codificação de rede, e que se demonstram possibilitar transferência sem descontinuidades. Pode assim dizer-se que esta tese, através de trabalho de análise e de propostas suportadas por simulações, defende que na concepção de sistemas de comunicação se devem considerar estratégias de transmissão e codificação que sejam não só próximas da capacidade dos canais, mas também tolerantes a atrasos, e que tais estratégias têm de ser concebidas tendo em vista características do canal e a camada física.

Optimization models for a short sea fuel oil distribution problem

O transporte marítimo e o principal meio de transporte de mercadorias em todo o mundo. Combustíveis e produtos petrolíferos representam grande parte das mercadorias transportadas por via marítima. Sendo Cabo Verde um arquipelago o transporte por mar desempenha um papel de grande relevância na economia do país. Consideramos o problema da distribuicao de combustíveis em Cabo Verde, onde uma companhia e responsavel por coordenar a distribuicao de produtos petrolíferos com a gestão dos respetivos níveis armazenados em cada porto, de modo a satisfazer a procura dos varios produtos. O objetivo consiste em determinar políticas de distribuicão de combustíveis que minimizam o custo total de distribuiçao (transporte e operacões) enquanto os n íveis de armazenamento sao mantidos nos n íveis desejados. Por conveniencia, de acordo com o planeamento temporal, o prob¬lema e divido em dois sub-problemas interligados. Um de curto prazo e outro de medio prazo. Para o problema de curto prazo sao discutidos modelos matemáticos de programacao inteira mista, que consideram simultaneamente uma medicao temporal cont ínua e uma discreta de modo a modelar multiplas janelas temporais e taxas de consumo que variam diariamente. Os modelos sao fortalecidos com a inclusão de desigualdades validas. O problema e então resolvido usando um "software" comercial. Para o problema de medio prazo sao inicialmente discutidos e comparados varios modelos de programacao inteira mista para um horizonte temporal curto assumindo agora uma taxa de consumo constante, e sao introduzidas novas desigualdades validas. Com base no modelo escolhido sao compara¬das estrategias heurísticas que combinam três heur ísticas bem conhecidas: "Rolling Horizon", "Feasibility Pump" e "Local Branching", de modo a gerar boas soluçoes admissíveis para planeamentos com horizontes temporais de varios meses. Finalmente, de modo a lidar com situaçoes imprevistas, mas impor¬tantes no transporte marítimo, como as mas condicões meteorológicas e congestionamento dos portos, apresentamos um modelo estocastico para um problema de curto prazo, onde os tempos de viagens e os tempos de espera nos portos sao aleatórios. O problema e formulado como um modelo em duas etapas, onde na primeira etapa sao tomadas as decisões relativas as rotas do navio e quantidades a carregar e descarregar e na segunda etapa (designada por sub-problema) sao consideradas as decisoes (com recurso) relativas ao escalonamento das operacões. O problema e resolvido por um metodo de decomposto que usa um algoritmo eficiente para separar as desigualdades violadas no sub-problema.