Cutting path as a rural postman problem

The Rural Postman Problem (RPP) is a particular Arc Routing Problem (ARP) which consists of determining a minimum cost circuit on a graph so that a given subset of required edges is traversed. The RPP is an NP-hard problem with significant real-life applications. This paper introduces an original approach based on Memetic Algorithms - the MARP algorithm - to solve the RPP and, also deals with an interesting Industrial Application, which focuses on the path optimization for component cutting operations. Memetic Algorithms are a class of Metaheuristics which may be seen as a population strategy that involves cooperation and competition processes between population elements and integrates “social knowledge”, using a local search procedure. The MARP algorithm is tested with different groups of instances and the results are compared with those gathered from other publications. MARP is also used in the context of various real-life applications.

Estudio de la gestión de la variable ambiental en la generación termoeléctrica

En la actualidad, el cambio climático es uno de los temas de mayor preocupación para la población mundial y los científicos de todo el mundo. Debido al crecimiento de la población de forma exponencial, la demanda de energía aumenta acorde con ello, por lo que las actividades de producción energética aumentan consecuentemente, siendo éstas las principales causantes de la aceleración del cambio climático. Pese a que muchos países previamente habían apostado por la producción energética mediante tecnologías limpias a partir de energías renovables, hoy en día es imposible prescindir de los combustibles fósiles pues, junto a la energía nuclear, suponen el mayor porcentaje dentro del mix energético de los países más grandes del mundo, por lo que el cambio debe ser global y con todos los países implicados al unísono. Por ello, los países desarrollados decidieron acordar una serie de leyes y normas para la regulación y el control de la expansión energética en el mundo, mediante programas de incentivo a las empresas para la producción de energía limpia, libre de emisiones, sustituyendo y mejorando los procesos tecnológicos para que garanticen un desarrollo sostenible. De esta forma, se conseguiría también reducir la dependencia energética de los países productores de los recursos fósiles más importantes y a su vez, ayudar a otros sectores a diversificar su negocio y mejorar así la economía de las áreas colindantes a las centrales de producción térmica. Gracias a estos programas de incentivo o, también llamados mecanismos de flexibilidad, las empresas productoras de energía, al acometer inversiones en tecnologia limpia, dejan de emitir gases de efecto invernadero a la atmósfera. Por tanto, gracias al comercio de emisiones y al mercado voluntario, las empresas pueden vender dichas emisiones aumentando la rentabilidad de sus proyectos, haciendo más atractivo de por sí el hecho de invertir en tecnología limpia. En el proyecto desarrollado, se podrá comprobar de una forma más extensa todo lo anteriormente citado. Para ello, se desarrollará una herramienta de cálculo que nos permitirá analizar los beneficios obtenidos por la sustitución de un combustible fósil, no renovable, por otro renovable y sostenible, como es la biomasa. En esta herramienta se calcularán, de forma estimada, las reducciones de las emisiones de CO2 que supone dicha sustitución y se hallará, en función del valor de las cotizaciones de los bonos de carbono en los diferentes mercados, cuál será el beneficio económico obtenido por la venta de las emisiones no emitidas que supone esta sustitución. Por último, dicho beneficio será insertado en un balance económico de la central donde se tendrán en cuenta otras variables como el precio del combustible o las fluctuaciones del precio de la electricidad, para hallar finalmente la rentabilidad que supondría la inversión de esta adaptación en la central. Con el fin de complementar y aplicar la herramienta de cálculo, se analizarán dos casos prácticos de una central de carbón, en los cuales se decide su suscripción dentro del contexto de los mecanismos de flexibilidad creados en los acuerdos internacionales.

Gestão de Recursos Energéticos para Apoio à Operação dos Virtual Power Players

A liberalização dos mercados de energia elétrica e a crescente integração dos recursos energéticos distribuídos nas redes de distribuição, nomeadamente as unidades de produção distribuída, os sistemas de controlo de cargas através dos programas de demand response, os sistemas de armazenamento e os veículos elétricos, representaram uma evolução no paradigma de operação e gestão dos sistemas elétricos. Este novo paradigma de operação impõe o desenvolvimento de novas metodologias de gestão e controlo que permitam a integração de todas as novas tecnologias de forma eficiente e sustentável. O principal contributo deste trabalho reside no desenvolvimento de metodologias para a gestão de recursos energéticos no contexto de redes inteligentes, que contemplam três horizontes temporais distintos (24 horas, 1 hora e 5 minutos). As metodologias consideram os escalonamentos anteriores assim como as previsões atualizadas de forma a melhorar o desempenho total do sistema e consequentemente aumentar a rentabilidade dos agentes agregadores. As metodologias propostas foram integradas numa ferramenta de simulação, que servirá de apoio à decisão de uma entidade agregadora designada por virtual power player. Ao nível das metodologias desenvolvidas são propostos três algoritmos de gestão distintos, nomeadamente para a segunda (1 hora) e terceira fase (5 minutos) da ferramenta de gestão, diferenciados pela influência que os períodos antecedentes e seguintes têm no período em escalonamento. Outro aspeto relevante apresentado neste documento é o teste e a validação dos modelos propostos numa plataforma de simulação comercial. Para além das metodologias propostas, a aplicação permitiu validar os modelos dos equipamentos considerados, nomeadamente, ao nível das redes de distribuição e dos recursos energéticos distribuidos. Nesta dissertação são apresentados três casos de estudos, cada um com diferentes cenários referentes a cenários de operação futuros. Estes casos de estudos são importantes para verificar a viabilidade da implementação das metodologias e algoritmos propostos. Adicionalmente são apresentadas comparações das metodologias propostas relativamente aos resultados obtidos, complexidade de gestão em ambiente de simulação para as diferentes fases da ferramenta proposta e os benefícios e inconvenientes no uso da ferramenta proposta.

An Open Source BI Approach: Concept Proof Tracking Fleet

É possível assistir nos dias de hoje, a um processo tecnológico evolutivo acentuado por toda a parte do globo. No caso das empresas, quer as pequenas, médias ou de grandes dimensões, estão cada vez mais dependentes dos sistemas informatizados para realizar os seus processos de negócio, e consequentemente à geração de informação referente aos negócios e onde, muitas das vezes, os dados não têm qualquer relacionamento entre si. A maioria dos sistemas convencionais informáticos não são projetados para gerir e armazenar informações estratégicas, impossibilitando assim que esta sirva de apoio como recurso estratégico. Portanto, as decisões são tomadas com base na experiência dos administradores, quando poderiam serem baseadas em factos históricos armazenados pelos diversos sistemas. Genericamente, as organizações possuem muitos dados, mas na maioria dos casos extraem pouca informação, o que é um problema em termos de mercados competitivos. Como as organizações procuram evoluir e superar a concorrência nas tomadas de decisão, surge neste contexto o termo Business Intelligence(BI). A GisGeo Information Systems é uma empresa que desenvolve software baseado em SIG (sistemas de informação geográfica) recorrendo a uma filosofia de ferramentas open-source. O seu principal produto baseia-se na localização geográfica dos vários tipos de viaturas, na recolha de dados, e consequentemente a sua análise (quilómetros percorridos, duração de uma viagem entre dois pontos definidos, consumo de combustível, etc.). Neste âmbito surge o tema deste projeto que tem objetivo de dar uma perspetiva diferente aos dados existentes, cruzando os conceitos BI com o sistema implementado na empresa de acordo com a sua filosofia. Neste projeto são abordados alguns dos conceitos mais importantes adjacentes a BI como, por exemplo, modelo dimensional, data Warehouse, o processo ETL e OLAP, seguindo a metodologia de Ralph Kimball. São também estudadas algumas das principais ferramentas open-source existentes no mercado, assim como quais as suas vantagens/desvantagens relativamente entre elas. Em conclusão, é então apresentada a solução desenvolvida de acordo com os critérios enumerados pela empresa como prova de conceito da aplicabilidade da área Business Intelligence ao ramo de Sistemas de informação Geográfica (SIG), recorrendo a uma ferramenta open-source que suporte visualização dos dados através de dashboards.

Real-time Task-Splitting scheduling algorithms framework

Nos dias de hoje, os sistemas de tempo real crescem em importância e complexidade. Mediante a passagem do ambiente uniprocessador para multiprocessador, o trabalho realizado no primeiro não é completamente aplicável no segundo, dado que o nível de complexidade difere, principalmente devido à existência de múltiplos processadores no sistema. Cedo percebeu-se, que a complexidade do problema não cresce linearmente com a adição destes. Na verdade, esta complexidade apresenta-se como uma barreira ao avanço científico nesta área que, para já, se mantém desconhecida, e isto testemunha-se, essencialmente no caso de escalonamento de tarefas. A passagem para este novo ambiente, quer se trate de sistemas de tempo real ou não, promete gerar a oportunidade de realizar trabalho que no primeiro caso nunca seria possível, criando assim, novas garantias de desempenho, menos gastos monetários e menores consumos de energia. Este último fator, apresentou-se desde cedo, como, talvez, a maior barreira de desenvolvimento de novos processadores na área uniprocessador, dado que, à medida que novos eram lançados para o mercado, ao mesmo tempo que ofereciam maior performance, foram levando ao conhecimento de um limite de geração de calor que obrigou ao surgimento da área multiprocessador. No futuro, espera-se que o número de processadores num determinado chip venha a aumentar, e como é óbvio, novas técnicas de exploração das suas inerentes vantagens têm de ser desenvolvidas, e a área relacionada com os algoritmos de escalonamento não é exceção. Ao longo dos anos, diferentes categorias de algoritmos multiprocessador para dar resposta a este problema têm vindo a ser desenvolvidos, destacando-se principalmente estes: globais, particionados e semi-particionados. A perspectiva global, supõe a existência de uma fila global que é acessível por todos os processadores disponíveis. Este fato torna disponível a migração de tarefas, isto é, é possível parar a execução de uma tarefa e resumir a sua execução num processador distinto. Num dado instante, num grupo de tarefas, m, as tarefas de maior prioridade são selecionadas para execução. Este tipo promete limites de utilização altos, a custo elevado de preempções/migrações de tarefas. Em contraste, os algoritmos particionados, colocam as tarefas em partições, e estas, são atribuídas a um dos processadores disponíveis, isto é, para cada processador, é atribuída uma partição. Por essa razão, a migração de tarefas não é possível, acabando por fazer com que o limite de utilização não seja tão alto quando comparado com o caso anterior, mas o número de preempções de tarefas decresce significativamente. O esquema semi-particionado, é uma resposta de caráter hibrido entre os casos anteriores, pois existem tarefas que são particionadas, para serem executadas exclusivamente por um grupo de processadores, e outras que são atribuídas a apenas um processador. Com isto, resulta uma solução que é capaz de distribuir o trabalho a ser realizado de uma forma mais eficiente e balanceada. Infelizmente, para todos estes casos, existe uma discrepância entre a teoria e a prática, pois acaba-se por se assumir conceitos que não são aplicáveis na vida real. Para dar resposta a este problema, é necessário implementar estes algoritmos de escalonamento em sistemas operativos reais e averiguar a sua aplicabilidade, para caso isso não aconteça, as alterações necessárias sejam feitas, quer a nível teórico quer a nível prá

A framework for real time MMO game content generation

Com o aumento de plataformas móveis disponíveis no mercado e com o constante incremento na sua capacidade computacional, a possibilidade de executar aplicações e em especial jogos com elevados requisitos de desempenho aumentou consideravelmente. O mercado dos videojogos tem assim um cada vez maior número de potenciais clientes. Em especial, o mercado de jogos massive multiplayer online (MMO) tem-se tornado muito atractivo para as empresas de desenvolvimento de jogos. Estes jogos suportam uma elevada quantidade de jogadores em simultâneo que podem estar a executar o jogo em diferentes plataformas e distribuídos por um "mundo" de jogo extenso. Para incentivar a exploração desse "mundo", distribuem-se de forma inteligente pontos de interesse que podem ser explorados pelo jogador. Esta abordagem leva a um esforço substancial no planeamento e construção desses mundos, gastando tempo e recursos durante a fase de desenvolvimento. Isto representa um problema para as empresas de desenvolvimento de jogos, e em alguns casos, e impraticável suportar tais custos para equipas indie. Nesta tese e apresentada uma abordagem para a criação de mundos para jogos MMO. Estudam-se vários jogos MMO que são casos de sucesso de modo a identificar propriedades comuns nos seus mundos. O objectivo e criar uma framework flexível capaz de gerar mundos com estruturas que respeitam conjuntos de regras definidas por game designers. Para que seja possível usar a abordagem aqui apresentada em v arias aplicações diferentes, foram desenvolvidos dois módulos principais. O primeiro, chamado rule-based-map-generator, contem a lógica e operações necessárias para a criação de mundos. O segundo, chamado blocker, e um wrapper à volta do módulo rule-based-map-generator que gere as comunicações entre servidor e clientes. De uma forma resumida, o objectivo geral e disponibilizar uma framework para facilitar a geração de mundos para jogos MMO, o que normalmente e um processo bastante demorado e aumenta significativamente o custo de produção, através de uma abordagem semi-automática combinando os benefícios de procedural content generation (PCG) com conteúdo gráfico gerado manualmente.