Tese (doutorado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós-Graduação em Engenharia de Produção. / Made available in DSpace on 2012-10-20T07:06:50Z (GMT). No. of bitstreams: 1 189148.pdf: 1079005 bytes, checksum: 1e3e85ccfa99df884bf10a139290c0f9 (MD5) / Muitos sistemas que oferecem serviços de atendimento, distribuição ou coleta, são constituídos por diferentes tipos de instalações, apresentando algum relacionamento hierárquico entre as mesmas. Assim, o objetivo deste trabalho é discutir e resolver de forma aproximada, uma classe de problemas de localização de instalações com dois níveis de hierarquias, incluindo problemas de grande escala. Dentre os problemas práticos que podem ser resolvidos com a técnica proposta, estão sistemas para tratamento de saúde, compostos por hospitais e postos de saúde. Nestes sistemas os clientes devem buscar tratamento em um posto de saúde ou diretamente em um hospital, sendo que uma fração q dos clientes atendidos inicialmente em um posto de saúde são transferidos para um hospital para complementar o tratamento. Também podem ser resolvidos os problemas que envolvem produção/distribuição de mercadorias, como aqueles compostos por fábricas e armazéns. Neste caso, mercadorias são transportadas das fábricas para os clientes, passando ou não por armazéns intermediários. Os problemas são modelados de forma que os custos com transporte, entre as instalações do primeiro e segundo nível, podem diferir dos custos com transporte entre os clientes e as instalações. Além disto, não são consideradas as capacidades das instalações e cada cliente tem sua localização e demanda bem definidos, sendo atendido por exatamente uma instalação do primeiro ou segundo nível. Em qualquer caso, busca-se minimizar os custos com transporte ou transporte e abertura das instalações, caso as quantidades destas não estejam impostas pelo problema. Em linhas gerais a técnica proposta utiliza um algoritmo conhecido por Forward p-Median para gerar uma solução inicial para o problema. Neste algoritmo utiliza-se uma versão modificada do algoritmo de Teitz e Bart, para o problema das p-medianas. Sobre esta solução inicial, são então efetuadas melhorias que incluem procedimentos de troca. A avaliação da qualidade das soluções obtidas é feita com o uso de limites inferiores, obtidos através de relaxação Lagrangeana.

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós-graduação em Engenharia de Produção / Made available in DSpace on 2012-10-24T18:46:13Z (GMT). No. of bitstreams: 1 264414.pdf: 1891457 bytes, checksum: 127160c37f20ea0b01f38df656a3d580 (MD5) / Neste trabalho são implementadas e analisadas as heurísticas de Teitz e Bart, Busca Tabu e Algoritmo Genético aplicadas ao problema das p-medianas. O objetivo foi avaliar o desempenho dos algoritmos em redes pequenas, médias e grandes levando-se em consideração o valor da solução e o tempo de resolução. Para isso foram realizados testes em 115 problemas gerados aleatoriamente. Os resultados demonstraram bom desempenho dos algoritmos de Busca Tabu e Algoritmo Genético em redes pequenas e médias. Já em problemas de grande porte, o algoritmo de Teitz e Bart modificado forneceu melhores respostas em menor tempo.

Tese de mestrado integrado. Engenharia Industrial e Gestão. Faculdade de Engenharia. Universidade do Porto. 2011

Tese (doutorado) - Universidade Federal de Santa Catarina. Centro Tecnológico. Programa de Pós-Graduação em Engenharia de Produção / Made available in DSpace on 2012-10-21T10:13:22Z (GMT). No. of bitstreams: 1 203794.pdf: 1456519 bytes, checksum: b373b1757509e2b213390cfd4962afd8 (MD5) / Nos problemas de roteamento o objetivo é determinar um circuito de custo mínimo que cobre um dado conjunto de arcos ou nós de um grafo, sujeito a algumas restrições. Existem duas classes bem conhecidas de tais problemas, denominadas como o Problema de Caixeiro Viajante (PCV), e o Problema do Carteiro Chinês (PCC). Com raras exceções, todos os problemas já formulados nessas duas classes são NP-completos. Portanto, para os problemas de maior porte existem apenas soluções aproximadas. Nessa Tese foi considerado o problema de determinar um circuito de custo mínimo que cobre um dado subconjunto de arcos, de arestas e de nós de um grafo misto, sujeito a algumas restrições nos vértices (restrições que proíbem conversões indesejáveis nos cruzamentos de malhas urbanas). Obviamente, o PCV, PCC e a maior parte de suas variações, como: o Problema do Carteiro Chinês Misto e o Problema do Carteiro Rural são casos particulares deste problema geral. A solução proposta é baseada numa transformação polinomial do grafo que possibilita a solução do problema resultante como um PCV padrão. Resultados computacionais confirmam a eficiência do método na obtenção de soluções próxima a ótimas para problemas razoavelmente grandes.

La delincuencia es uno de los mayores problemas que hay en el Perú, especialmente, en Lima. En nuestra capital, el aumento de robos y delitos genera una gran preocupación ya que los policías no actúan rápido y no llegan a tiempo para impedir un robo o capturar ladrones. La situación actual es que las comisarías vigilan con sus patrullas los distritos sin considerar las zonas con mayor índice de criminalidad. Este criterio es de suma importancia pues puede ayudar a que los vehículos policiales velen por la seguridad de los ciudadanos de manera más estratégica. El presente proyecto contribuye ante esta problemática es desarrollar un sistema integral que permita la recepción de denuncias informales por medio de los ciudadanos y que genere, mediante un algoritmo que se retroalimente con los delitos registrados, una propuesta de distribución cercana a la óptima de vehículos policiales. La solución brindada por el sistema tiene como variables los datos propios de la comisaría, cantidad de vehículos, horarios y las frecuencias de los delitos con el fin de convertir la labor policial de manera proactiva. / Tesis

Orientador: Cid Carvalho de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-19T00:16:31Z (GMT). No. of bitstreams: 1 Zilli_PetersonKatagiri_M.pdf: 1307926 bytes, checksum: 5fe0ddfca7cce84d9e26b66106d61e8b (MD5) Previous issue date: 2011 / Resumo: O Problema de Roteamento de Veículos (VRP, em inglês) foi proposto por Dantzig e Ramser em 1959 e, desde então, um grande número de artigos foi dedicado à solução de suas variantes. O problema original consiste em determinar rotas otimais que serão usadas por veículos de capacidade limitada para servirem a um conjunto de clientes. Neste trabalho focamos o estudo e a implementação dos modelos chamados de "ricos" na literatura, os quais englobam variantes complexas do VRP e conseguem representar situações mais próximas dos problemas logísticos encontrados em sistemas de distribuição reais. A principal motivação para esta pesquisa é uma aplicação prática referente ao problema de roteamento dos ônibus fretados pela UNICAMP para o transporte de seus funcionários, que se caracteriza como um modelo rico. O objetivo final é a otimização de tal processo através da minimização da distância total percorrida ou do número de veículos empregados, com a consequente redução dos gastos incorridos pela Universidade. Portanto, além do seu aspecto científico, esta dissertação produz resultados com chances reais de trazer benefícios à administração de uma instituição pública de ensino. Para que isto venha a ocorrer, as heurísticas desenvolvidas foram inseridas em um sistema de informações geográficas, que será usado pela universidade no processo de criação e otimização das rotas a serem licitadas publicamente / Abstract: The Vehicle Routing Problem (VRP) was first proposed by Dantzig and Ramser in 1959 and, since then, a large number of papers has been devoted to the solution of its variants. The original problem consists in determining an optimal set of routes to be used by vehicles of limited capacity that serve a set of customers. In this paper we focus on the study and implementation of models called "rich" in the literature, which include complex variants of the VRP that represent situations closer to the logistical problems encountered in real distribution systems. The main motivation for this research is a practical problem concerning the routing of buses chartered by UNICAMP for transporting a part of its employees, which is characterized as a rich model. The goal is to optimize this process by minimizing the total travel distance or the number of vehicles used, with a consequent reduction of the expenses incurred by the University. Therefore, in addition to its scientific aspect, this dissertation gives results with real chances to benefit the administration of a public university. For this to happen, the heuristics developed were entered into a geographic information system, which will be used by the university in the process of creation and optimization of routes to be publicly auctioned / Mestrado / Pesquisa Operacional / Mestre em Ciência da Computação

El presente proyecto de fin de carrera propone implementar un algoritmo metaheurístico, cuckoo search, en el proceso de obtención de recompensas de juegos Gacha. El foco y objetivo de este estudio es el poder encontrar un equilibrio entre la satisfacción del usuario y el beneficio de la empresa, por lo cual se utilizaron dos tipos de usuario quienes abarcan las características de tiempo empleado en el juego y cuánto monto han invertido en éste. Para ello, se propuso una función objetivo en la cual abarca las variables relacionadas al usuario y la empresa, luego se adaptó el algoritmo propuesto al contexto planteado. Finalmente se implementó y aplicó en un prototipo de juego donde se compara el funcionamiento y desempeño de éste junto a un simulador; además de poder visualizar y simular el contexto de estar utilizando/jugando un juego Gacha. De los resultados, se pudo verificar un desempeño del algoritmo elegido frente al simulador. Con ello se logra cumplir con el objetivo inicial de poder equilibrar los valores representativos del usuario y el beneficio de la empresa. La meta propuesta es poder demostrar que el uso del cuckoo search en estos juegos es posible y en un futuro poder mejorarlo para su uso en estos tipos de juegos.

Esse trabalho de investigação visa a realização de uma análise sistemática, integrada e iterativa da utilização de algoritmos heurísticos aplicados aos problemas de estimativa de parâmetros e detecção multiusuário, sob o ponto de vista do compromisso desempenho × complexidade. O sistema considera topologias do tipo CDMA com exploração de diversidade multidimensional, ou seja, que utilizam uma ou mais técnicas de diversidade, considerando a diversidade de código, tempo, frequência e espaço, entre outras, sujeitos a desvanecimentos multipercurso. A solução integrada para os problemas de estimativa de parâmetros e detecção multiusuário consiste no uso recorrente de técnicas heurísticas. Além disso, estabelece-se uma análise comparada e sistêmica de convergência e de complexidade computacional da técnica de detecção proposta com alguns outros métodos, heurísticos ou determinísticos, relatados na literatura, considerando como métrica de desempenho o número de operações computacionais que cada estratégia requer para a detecção simultânea da informação de todos os usuários ativos no sistema. Por fim, e mais importante, considera-se como a principal contribuição deste trabalho a sistematização da utilização dos algoritmos heurísticos no processo de otimização dos problemas já citados, caracterização de limiares de desempenho e análise de complexidade destas técnicas, trazendo à comunidade científica parâmetros suficientes que devem ser respeitados na configuração dos algoritmos para garantia de resultados satisfatórios quando da utilização destes métodos em problemas de detecção multiusuário com diversidade multidimensional e estimativa de parâmetros. / This work will perform a systematic, integrated and iterative research of heuristic algorithms applied to parameter estimation and multiuser detection problems, considering the performance × complexity tradeoff. The CDMA systems with multidimensional diversity exploitation, i.e., with one or more diversity techniques, code diversity, frequency, time and space, among other, in multipath fading channel scenarios are considered. The integrated solution for parameter estimation and multiuser detection problem uses heuristic techniques in recurrent form. In addition, we intend to establish a systemic and comparative analysis of convergence and computational complexity of the proposal detection technique with some other methods, heuristic or deterministic, reported in the literature, considering the number of computational operations that each strategy requires for simultaneous detection from all active users as a performance metrics. Finally, and most importantly, this work systematizes the heuristic algorithms approach in the optimization problems process already mentioned, considering the thresholds for performance and complexity of these techniques, bringing the scientific community enough configuration parameters that must be respected in the setup algorithms step to guarantee satisfactory results when using these methods to multiuser detection with multidimensional diversity and parameter estimation problems.

Esse trabalho de investigação visa a realização de uma análise sistemática, integrada e iterativa da utilização de algoritmos heurísticos aplicados aos problemas de estimativa de parâmetros e detecção multiusuário, sob o ponto de vista do compromisso desempenho × complexidade. O sistema considera topologias do tipo CDMA com exploração de diversidade multidimensional, ou seja, que utilizam uma ou mais técnicas de diversidade, considerando a diversidade de código, tempo, frequência e espaço, entre outras, sujeitos a desvanecimentos multipercurso. A solução integrada para os problemas de estimativa de parâmetros e detecção multiusuário consiste no uso recorrente de técnicas heurísticas. Além disso, estabelece-se uma análise comparada e sistêmica de convergência e de complexidade computacional da técnica de detecção proposta com alguns outros métodos, heurísticos ou determinísticos, relatados na literatura, considerando como métrica de desempenho o número de operações computacionais que cada estratégia requer para a detecção simultânea da informação de todos os usuários ativos no sistema. Por fim, e mais importante, considera-se como a principal contribuição deste trabalho a sistematização da utilização dos algoritmos heurísticos no processo de otimização dos problemas já citados, caracterização de limiares de desempenho e análise de complexidade destas técnicas, trazendo à comunidade científica parâmetros suficientes que devem ser respeitados na configuração dos algoritmos para garantia de resultados satisfatórios quando da utilização destes métodos em problemas de detecção multiusuário com diversidade multidimensional e estimativa de parâmetros. / This work will perform a systematic, integrated and iterative research of heuristic algorithms applied to parameter estimation and multiuser detection problems, considering the performance × complexity tradeoff. The CDMA systems with multidimensional diversity exploitation, i.e., with one or more diversity techniques, code diversity, frequency, time and space, among other, in multipath fading channel scenarios are considered. The integrated solution for parameter estimation and multiuser detection problem uses heuristic techniques in recurrent form. In addition, we intend to establish a systemic and comparative analysis of convergence and computational complexity of the proposal detection technique with some other methods, heuristic or deterministic, reported in the literature, considering the number of computational operations that each strategy requires for simultaneous detection from all active users as a performance metrics. Finally, and most importantly, this work systematizes the heuristic algorithms approach in the optimization problems process already mentioned, considering the thresholds for performance and complexity of these techniques, bringing the scientific community enough configuration parameters that must be respected in the setup algorithms step to guarantee satisfactory results when using these methods to multiuser detection with multidimensional diversity and parameter estimation problems.

Orientador: Alice Maria Bastos Hubinger Tokarnia / Dissertação (mestrado) - Universidade Estadual de Campinas,Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-21T13:10:12Z (GMT). No. of bitstreams: 1 Pepe_PedroCarlosFazolino_M.pdf: 4573450 bytes, checksum: d2aa117fafd3213b052c1164eaabed1f (MD5) Previous issue date: 2012 / Resumo: Este trabalho apresenta quatro algoritmos de escalonamento dinâmico de Tensão e Frequência (DVFS) em sistemas multiprocessador baseado em caminhos de execução. Nossos alvos são aplicações multimídia executadas em sistemas embarcados, com especificação de qualidade por taxa mínima de entradas (QoS) processadas. Uma fração mínima de entradas, geralmente quadros de dados, precisa ser completamente processada no tempo máximo de resposta especificado. O objetivo dos algoritmos é atuar em quatro cenários que correspondem a sistemas com diferentes possibilidades de escalonamento dinâmico de tensão e frequência e diferentes capacidades de monitoramento da qualidade de serviço. No primeiro cenário, todos os pacotes de dados de entrada recebidos devem ser processados dentro do tempo máximo especificado e o nível de tensão/frequência pode ser ajustado no início da execução da aplicação, sendo o mesmo para todos os processadores. Este cenário é referência para comparação de resultados para os outros cenários. Para o segundo cenário, o nível de tensão/frequência pode ser definido individualmente para um processador, no início da execução de cada tarefa, e dados de entrada de classes específicas podem ser descartados. O terceiro cenário possibilita, além do descarte de classes específicas de dados de entrada, o ajuste do nível de tensão/frequência de cada tarefa de acordo com a classe de dados de entrada a ser processada. O algoritmo desenvolvido para o quarto cenário trata dinamicamente de alterações na distribuição probabilística das classes de entrada, calculando novos níveis de tensão/frequência para as tarefas e classes de entrada de modo que a especificação de qualidade continue a ser satisfeita, de forma eficiente. Para uma aplicação de cancelamento de eco acústico, executada em 4 processadores, com taxa mínima de processamento igual a 50%, o algoritmo de escalonamento de tensão e frequência, no cenário 3, conseguiu reduzir o consumo de energia em cerca de 71%, comparado ao cenário 1. No cenário 4, simulamos para esta aplicação uma modificação simultânea de 10 pontos percentuais na distribuição das classes de entrada em 3 tarefas causando aumentos do número de descartes. O algoritmo proposto para o cenário 4 manteve a qualidade mínima com um aumento de apenas 6% no consumo de energia, quando comparado ao consumo de energia da configuração inicial definida para o cenário 3 / Abstract: This work presents four execution-path based Dynamic Voltage/Frequency Scaling (DVFS) algorithms for multiprocessor systems. The targets are embedded systems multimedia applications, with minimum input data completion rate specification (QoS). A minimum fraction of input data, usually data frames, should be processed within the specified deadline. These algorithms aim to operate in four scenarios corresponding to systems with different possibilities of dynamic voltage and frequency scheduling and different QoS monitoring capabilities. In the first scenario, all received data frames should be treated within the deadline and the voltage/frequency operational level can be adjusted at the beginning of the application execution, and must be the same for all processors. This scenario is a reference for comparison of results obtained for the other scenarios. For the second scenario, the voltage/frequency operational level can be set individually for each processor at the beginning of each task execution, and input data frames of specific input classes can be discarded. The third scenario allows, besides discarding specific classes of input data, it is possible to adjust the operation level for each task, according to the class of the input data to be treated. The algorithm for the fourth scenario operates online, computing new voltage/frequency levels and making new decisions about class discarding to cope with changes in probability distribution of input classes. Its goal is to maintain the specified quality with low energy consumption. In an application of acoustic echo cancellation running on a system with 4 processors, with a rate of inputs completely processed specified as 50%, the algorithm for scenario 3 achieved a reduction in consumption close to 71%, comparing to the results for scenario 1. During simulation, this application has been subjected to simultaneous changes of 10% in the input class distributions of three discarding tasks, reducing system quality. The algorithm for scenario 4, maintained the minimum quality with just 6% increase in power consumption, when compared to the consumption of the initial configuration for scenario 3 / Mestrado / Engenharia de Computação / Mestre em Engenharia Elétrica