Made available in DSpace on 2017-07-21T14:19:39Z (GMT). No. of bitstreams: 1 Robson Fernando Duda.pdf: 3342961 bytes, checksum: 3f61d3a8f1dcfb461c6860c82d3f54db (MD5) Previous issue date: 2014-02-28 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / This paper presents a solution to the routing problem of vehicles with homogeneous fleet. To do so, heuristic and metaheuristic based algorithms applied towards the development of a decision support system, with georeferenced interface were developed. The algorithms had as base heuristic methods built in two phases, besides a metaheuristic. The interface layer used as visualization component is based in cartographic data that indicates the location of the points to be assisted and the paths that connects them, forming a road system represented using the Google Maps® API. The algorithms were validated using instances from the literature, presenting satisfactory results regarding optimization based in the methods that were used, showing that it is possible the usage of the developed system in the distribution of agricultural products. / Este trabalho apresenta uma solução para o problema de roteamento de veículos com frotas homogêneas. Para tanto, foram desenvolvidos algoritmos baseados em heurísticas e meta-heurísticas aplicadas ao desenvolvimento de um sistema de apoio a decisão, com interface georreferenciada. Os algoritmos tiveram como base métodos heurísticos construtivos e em duas fases, além de uma meta-heurística. A camada de interface utilizada como componente de visualização é baseada em dados cartográficos que indicam a localização dos pontos a serem atendidos e as vias que os interligam, formando a malha viária que é representada utilizando a API do Google Maps®. Os algoritmos foram validados utilizando instâncias da literatura, apresentando resultados satisfatórios em relação a otimização baseada nos métodos utilizados, mostrando ser possível a utilização do sistema desenvolvido para a distribuição de produtos agrícolas.

This study considers a vehicle routing problem with time windows, accessibility restrictions on customers and a fleet that is heterogeneous with regard to capacity, average speed and cost. A vehicle can perform multiple routes per day, all starting and ending at a single depot, and it is assigned to a single driver, whose total work hours are limited. The available fleet is divided into an owned fleet, for which a variable cost is incurred, and a chartered fleet, for which only a fixed cost is incurred for each vehicle used. A column generation algorithm embedded in a branch-and-bound framework is proposed. The column generation pricing subproblem required a specific elementary shortest path problem with resource constraints algorithm to address the possibility for each vehicle performing multiple routes per day and to address the need to determine the workdays start time within the planning horizon. To make the algorithm efficient, a constructive heuristic and a learning metaheuristic algorithm based on tabu search were also developed. Both were used on branch-and-bound tree nodes to generate a good initial solution to the linear restricted master problem; particularly, to find a good initial primal bound to the branch-and-bound tree. / Este estudo aborda um problema de roteirização de veículos com janelas de tempo, restrições de acessibilidade nos clientes e uma frota que é heterogênea em relação à capacidade de carga, velocidade média de deslocamento e custo. Um veículo pode percorrer múltiplas rotas por dia, todas começando e terminando em um mesmo depósito, e está designado a um único motorista, cujo total de horas trabalhadas no dia está limitado a um valor máximo. A frota disponível é dividida em uma frota própria, para a qual um custo variável é incorrido, e uma frota de freteiros, para a qual apenas um custo fixo é incorrido para cada veículo utilizado. Um algoritmo baseado em geração de colunas, integrado a um procedimento de branch-and-bound, é proposto neste estudo. O subproblema de precificação da geração de colunas requereu um algoritmo específico para o problema do caminho mínimo elementar com restrições sobre recursos capaz de lidar com a possibilidade de cada veículo percorrer múltiplas rotas por dia e capaz de lidar com a necessidade de determinar o instante de início do dia de trabalho do motorista dentro do horizonte de planejamento. Para tornar o algoritmo eficiente, uma heurística construtiva e uma heurística de melhoria baseada em busca tabu também foram desenvolvidos. Ambos são utilizados nos nós da árvore de branch-and-bound para gerar boas soluções iniciais para o problema mestre restrito da geração de colunas; particularmente, para encontrar um bom limitante primal inicial para a árvore de branch-and-bound.

Made available in DSpace on 2015-03-05T13:57:00Z (GMT). No. of bitstreams: 0 Previous issue date: 27 / Nenhuma / Problemas de pessoal, produtividade e contenção de custos afetam todas as áreas de negócio, inclusive os provedores de cuidados de saúde. Porém, nesta área o controle dos custos não pode comprometer a qualidade do atendimento. É neste contexto que uma ferramenta computacional para a elaboração das escalas de trabalho de pessoal de enfermagem torna-se importante. Esta é uma tarefa realizada manualmente na maioria dos hospitais e clínicas, consumindo muito tempo e nem sempre atendendo completamente a legislação e normas vigentes. No Brasil há falta de ferramentas computacionais para a elaboração destas escalas, ou mesmo para a avaliação das escalas desenvolvidas. O objetivo desta pesquisa é encontrar uma solução, computacionalmente viável, para a geração de escalas de trabalho mensais para os técnicos de enfermagem, de acordo com as regras operacionais dos hospitais e as restrições da legislação. Deseja-se ainda obter maior nível de satisfação dos funcionários atendendo preferências de dias de folga e distribui / Problems of personnel, productivity and cost restriction affect all areas of a business, including the health care providers. However, in this area, cost control cannot endanger the quality of service. In this context, a software for creating the schedule of nursing personnel becomes important. This is a hand-made task in the majority of hospitals and clinics. It is time consuming and does not always comply to the legislation and the valid rules. In Brazil, there is a lack of computer tools for the creation of these schedules or even for the evaluation of the ones already developed. This research aims at finding a technologically feasible solution for the generation of monthly schedules for the nursing technicians, according to the operational rules of hospitals and legislation restrictions. It also aims at giving the employees a higher level of satisfaction, concerning their day off preferences and equitable distribution of duties on Saturdays, Sundays and holidays. The proposal is to apply a Tabu Search me

Submitted by Silvana Teresinha Dornelles Studzinski (sstudzinski) on 2015-07-03T17:52:39Z No. of bitstreams: 1 Iris Corrêa das Chagas Linck.pdf: 1456080 bytes, checksum: ea4a6f659a229e845649c58baaf8cb23 (MD5) / Made available in DSpace on 2015-07-03T17:52:39Z (GMT). No. of bitstreams: 1 Iris Corrêa das Chagas Linck.pdf: 1456080 bytes, checksum: ea4a6f659a229e845649c58baaf8cb23 (MD5) Previous issue date: 2012 / FINEP - Financiadora de Estudos e Projetos / Neste trabalho é desenvolvido um algoritmo híbrido que simula o comportamento do Codificador/Decodificador de vídeo H.264/AVC, ou simplesmente CODEC H.264, utilizado no Sistema Brasileiro de Televisão Digital. O algoritmo proposto tem a finalidade de buscar a melhor configuração possível de seis dos principais parâmetros utilizados para a configuração do CODEC H.264. Este problema é abordado como um problema de otimização combinatória conhecido como Problema de Seleção de Partes e que é classificado como NP-Difícil. O algoritmo híbrido proposto, denominado Simulador de Metaheurísticas aplicado a um CODEC (SMC), foi desenvolvido com base em duas metaheurísticas: Busca Tabu e Algoritmo Genético. Os seis parâmetros de configuração a serem otimizados pelo SMC são: o bit rate; o frame rate; os parâmetros de quantização de quadros tipo B, tipo P e tipo I e a quantidade de quadros tipo B em um grupo de imagens (GOP – Group of Pictures). Os dois primeiros parâmetros mencionados atuam basicamente sobre a qualidade da imagem do vídeo enquanto que os demais parâmetros atuam diretamente na compressão do vídeo. Experimentos e testes foram feitos utilizandose o CODEC H.264 desenvolvido no Projeto Plataforma de Convergência Digital IPTV/TV Digital (DigConv). Nos experimentos o CODEC tem seus parâmetros configurados de acordo com os resultados obtidos pelo SMC. Um vídeo é codificado no CODEC H.264 para que se possa analisar a sua qualidade de imagem e o seu grau de compressão após o processo de codificação. É feita uma correlação entre esses resultados e a Função Objetivo do SMC. A qualidade da imagem é medida através da métrica mais utilizada na literatura, o PSNR (Peak Signal to Noise Ratio), que é calculada pelo próprio CODEC ao final da codificação de um vídeo. Verificouse que à medida que a Função Objetivo aumenta, o CODEC H.264 consegue obter uma melhor qualidade de imagem e um maior grau de compressão de vídeo. / In this work is developed a hybrid algorithm that simulates the behavior of the H.264/AVC video encoder/decoder, or simply H.264 video CODEC, used in the Brazilian System of Digital Television. The proposed algorithm intends to seek the best possible configuration of the six main parameters used for configuring the H.264 video CODEC. This problem is treated as a combinatorial optimization problem known as the Parties Selection Problem, which is classified as NP-Hard. The proposed hybrid algorithm, called Simulator Metaheuristcs applied to a CODEC (SMC), was developed based on two metaheuristics: Tabu Search and Genetic Algorithm. The six configuration parameters to be optimized by the SMC are the bit rate, frame rate, the parameters of quantization tables of type B, type I and type P and the amount of frames type B in a group of pictures (GOP - Group of Pictures).The first two parameters mentioned, work primarily on the quality of the video image while the other parameters act directly on the video compression. Experiments and tests were done using the video CODEC H.264 developed in Digital Convergence Platform IPTV/Digital TV Project (DigConv). DigConv Project. In the experiments the CODEC has its parameters set according to the results obtained by the SMC. Then, a video is encoded by the CODEC in order to analyze the video image quality and the video compression degree reached after the encoding process. It is made a correlation between these results and the objective function of the SMC. The picture quality is measured by the metric most often used in literature, the PSNR (Peak Signal to Noise Ratio), which is calculated by the CODEC at the end of a video encoding process. It was found that as the objective function has increased, the CODEC reached a better image quality and a higher video compression.

Submitted by Silvana Teresinha Dornelles Studzinski (sstudzinski) on 2016-11-18T11:12:32Z No. of bitstreams: 1 Robermilton Sant´Anna de Oliveira Rodrigues_.pdf: 3942890 bytes, checksum: cd68235e6f58b7b97f966958f932b60d (MD5) / Made available in DSpace on 2016-11-18T11:12:32Z (GMT). No. of bitstreams: 1 Robermilton Sant´Anna de Oliveira Rodrigues_.pdf: 3942890 bytes, checksum: cd68235e6f58b7b97f966958f932b60d (MD5) Previous issue date: 2016-06-10 / IFRR - Instituto Federal de Educação Ciência e Tecnologia de Roraima / Com o advento da Internet, aliado à constante evolução das tecnologias de distribuição de Banda Larga, juntamente com um público cada vez mais exigente, surge o IPTV (Internet Protocol Television). Atualmente, existem várias pesquisas sobre como melhorar sua distribuição de conteúdo, através dos mais diversos dispositivos disponíveis no mercado, tais como: TV Digital, Tablets e Smartphones. Este trabalho apresenta uma ferramenta computacional, baseada em um modelo matemático, para otimização dos parâmetros do módulo IPTV de uma Plataforma de Convergência Digital (DIGICONV). Essa ferramenta computacional é baseada em aplicações das metaheurísticas Busca Tabu e Algoritmo Genético, a fim de obter melhorias em todos os segmentos da transmissão, além de identificar os motivos de uma possível sobrecarga do sistema, quando não há banda disponível suficiente para atender a todos os clientes, através de configurações específicas nos parâmetros de entrada que são: a taxa de transmissão (Tt), a qualidade de vídeo (Qv), a qualidade de áudio (Qa), os tipos de clientes (Tc), a largura de banda do cliente (Lb) e a quantidade de banda disponível (Bd). Os resultados obtidos neste trabalho comprovaram que tanto a Busca Tabu quanto o Algoritmo Genético obtiveram resultados satisfatórios e otimizados, conforme o aumento da Função Objetivo, atestando sua eficiência. / With the advent of the Internet, combined with the constant evolution of the broadband distribution technologies, along with the public increasingly demanding, IPTV (Internet Protocol Television) arises. Currently, there are several studies on how to improve the distribution of content through a variety of devices available in the market, such as Digital TV, Tablets and Smartphones. This paper presents a computational tool based on a mathematical model to optimize IPTV module parameters of a Digital Convergence Platform (DIGICONV). This software tool is based on applications of metaheuristics Tabu Search and Genetic Algorithm in order to achieve improvements in all segments of the transmission, and to identify the reasons for a possible system overload, when there is not enough available bandwidth to meet all customers through specific settings in the input parameters are: the transmission rate (Tt), the video quality (Qv), audio quality (Qa), the types of customers (Tc), the bandwidth of client (Lb) and the amount of available bandwidth (BD). The results of this study showed that both the tabu search and the genetic algorithm achieved satisfactory results and optimized, with increasing Objective Function, attesting to its effectiveness.

Šiame darbe nagrinėjamas patobulintas tabu paieškos metodas, žinomas kaip iteratyvioji tabu paieška (ITP). Pasiūlytos kai kurios ITP metodo modifikacijos, besiremiančios tam tikromis sprendinių mutavimo (pertvarkymo) procedūromis (inversijos, įterpimai ir kt.), kurios įgalina pagerinti gaunamų sprendinių kokybę. Atlikti išsamūs sudaryto ITP algoritmo ir kitų pasiūlytų modifikacijų eksperimentiniai tyrimai, panaudojant testinius KU pavyzdžius iš KU testinių pavyzdžių bibliotekos TSPLIB. Gauti rezultatai patvirtina pasiūlytų modifikacijų pranašumą kitų ITP variantų atžvilgiu. / In this work, one of the heuristic algorithm – the iterated tabu search and its modifications are discussed. The work is organized as follows. Firstly, some basic definitions and preliminaries are given. Then, the iterated tabu search algoritm and its variants based on special type mutations are considered in more details. The ITS algorithms modifications were tested on the TSP instances from the TSP library TSPLIB. The results of this tests (experiments) are presented as well. The work is completed with the conclusions.

Plati tvarkaraščių sudarymo uždavinio sritis yra industrinių, taip vadinamų gamybinių, tvarkarščių sudarymas. Yra trys gaminių tvarkaraščių klasės: darbų fabrikas, atvirasis fabrikas ir srautinis fabrikas. Bendra uždavinio specifikacija gali būti apibrėžta tokiu būdu: yra darbų aibė ir mašinų aibė, kurios tarpusavyje turi sąveikauti tam tikru specifiniu būdu. Paprastai šios problemos yra sunkiai išsprendžiamos tradiciniais (tiksliaisias) metodais. Metaeuristiniai algoritmai dažniausiai pateikia tiktai artimus optimumui sprendinius, tačiau per apibrėžtą laiką. Šiame darbe įgyvendinta keletas metaeuristikų: genetiniai algoritmai (besiskiriantys jų parametrų reikšmėmis) ir tabu paieškos algoritmai (besiskiriantys sprendinio aplinka). Kai kurios genetinio algoritmo strategijos pasiūlytos kaip genetinio algoritmo parametrų tyrimo išvada. Aštuoni algoritmai yra tiriami atsitiktinėms gamybinių tvarkaraščių sudarymo problemoms, lyginant pradinius sprendinius ir minimumus, pasiektus sprendinius ir minimumus, skaičiavimo trukmes ir skirtumą tarp pradinių bei pasiektų sprendinių. Pabaigoje pateikiama išvada apie tai, kad vieno tipo genetiniai parametrai (kryžminimo ir mutacijos lygiai) yra ypač reikalingi algoritmo konvergavimo, diversifikacijos ir intensifikacijos prasme, kito tipo (iteracijų skaičius ir populiacijos dydis) turi priklausyti nuo resursų, trečio tipo (elitizmas) yra geri “buferiai”. Galiausiai, kuomet paprasčiausios formos tabu paieška yra silpnesis konkurentas... [toliau žr. visą tekstą] / A wide area of scheduling problem is industrial so called shop scheduling. There are three classes of shop scheduling: Job Shop, Open Shop and Flow Shop. General problem specification could be specified as follows: there is set of jobs and set of machines, which should interact with each other in some specific way. Typically these problems are hard to solve in traditional (exact) methods. Metaheuristics algorithms mostly produce only nearby-optima, but in proper time. We implemented several metaheuristics: genetic algorithms (separated by values of their parameters) and several Tabu search algorithms (separated by neighborhood of solution). Some strategies of genetic algorithms are suggested as conclusion of genetic algorithm parameter research. Eight algorithms are examined for random shop scheduling problems in terms of initial solutions and minimum, gained solutions and minimum, processing time and difference between initial and gained solutions. In the end, author concludes, that one kind of genetic parameters (crossover and mutation rates) are especially demanding in sense of algorithm convergence, diversification and intensification aspects, other (number of iterations and population size) should depend on resources, third (elitism) is good “buffers”. Finally, while with its simplest form, Tabu search seems to be less competitive in algorithm effectiveness research, its dynamic modification outperforms all proposed genetic algorithms, but both – tabu search with... [to full text]

Made available in DSpace on 2014-06-11T19:22:32Z (GMT). No. of bitstreams: 0 Previous issue date: 2009-11-20Bitstream added on 2014-06-13T20:49:12Z : No. of bitstreams: 1 romero_mev_me_ilha.pdf: 1382824 bytes, checksum: b46118201c032210f988939bf442defe (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / A restauração do sistema de energia elétrica consiste na busca da melhor topologia com o maior número de cargas restauradas e o menor número possível de chaveamentos. Os limites de operação devem ser respeitados, ou seja, a rede deve manter a estrutura radial, os limites de tensão e das capacidades de cargas dos alimentadores e de subestações não devem ser violados. Desta forma, um dos objetivos do procedimento da restauração do serviço em sistemas de energia elétrica é reenergizar a maioria de cargas fora de serviço no menor tempo possível, pela transferência dessas áreas para outros sistemas energizados, sem violar restrições de operações e de projeto. Isso é uma busca constante das empresas concessionárias em atender a satisfação dos clientes e da adequação aos índices de continuidade de serviços impostos pelas agências reguladoras, no caso brasileiro a ANEEL (Agência Nacional de Energia Elétrica). Neste trabalho propõe-se uma técnica para melhorar a confiabilidade de sistemas de distribuição, através da alocação de chaves automáticas para restauração desses sistemas. O problema de alocação de chaves é modelado como um problema de programação não linear restrito, com uma função multiobjetivo. A técnica de solução proposta para resolver tanto o problema de alocação de chaves como o de restauração de sistemas radiais de distribuição é um algoritmo de busca tabu reativa (BTR). Para introduzir a metodologia proposta para solução dos problemas de alocação de chaves e restauração de sistemas de distribuição, são apresentados os aspectos teóricos destes problemas, o sistema de codificação que representa soluções potenciais para o problema, e permite que o mesmo seja resolvido através de meta-heurísticas e o desenvolvimento do trabalho de pesquisa para o planejamento da operação e controle on line de um sistema real / The restoration of electric power system is the search for the best topology with the largest number of loads and restored fewest switching. The operating limits must be respected, in other words, the network must maintain the radial structure, voltage limits and capacity loads of feeders and substations should not be violated. Thus one aim of the procedure of restoration of service in electric power systems is re-energized the most charges out of service in the shortest time possible, and the transfer of these areas to other systems energized, without violating restrictions on operations and constructions. This is a constant search for businesses to meet customer satisfaction and the suitability indices of continuity of services imposed by regulatory agencies, in Brazil, ANEEL (National Agency of Electrical Energy). This paper proposes a technique to improve the reliability of distribution systems, through the allocation of keys for automatic restoration of such systems. The problem of allocation of keys is modeled as a problem of constrained nonlinear programming with a multi-objective function. The technical solution proposed to solve both the problem of assigning keys to the restoration of radial distribution systems is an algorithm of reactive tabu search (RTS). To introduce the proposed methodology for solving problems of allocation of keys and restoration of distribution systems, be present the theoretical aspects of these problems, the coding system that represents potential solutions to the problem, and allows it to be resolved by metaheuristics and development of research work for the planning of the operation and control an online real system

Made available in DSpace on 2014-06-11T19:22:35Z (GMT). No. of bitstreams: 0 Previous issue date: 2008-02-20Bitstream added on 2014-06-13T19:48:57Z : No. of bitstreams: 1 mansano_em_me_ilha.pdf: 1079424 bytes, checksum: 900c3e74964f43e940cd65196fc6d58b (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / A metaheurística Busca Tabu, é uma técnica baseada em parâmetros de controle, a estrutura de vizinhança e seu próprio algoritmo com poderosas estratégias de busca. Nesta técnica, dada uma configuração, deseja-se passar ao melhor vizinho através da entrada e saída de ramos, obtendo assim a configuração incumbente. Com essa configuração que é considerada como a melhor configuração encontrada até o momento, e mesmo sendo um bom valor o sistema continua a busca procurando mais configurações até encontrar uma que seja melhor que as já encontradas até o momento. As versões paralelas dos algoritmos foram desenvolvidas a partir de um algoritmo BT serial avançado, sob o paradigma de programacão SPMD (“Single Program, Multiple Data”), e as mesmas foram testadas para sistemas testes de pequeno porte (Garver - 6 barras/15 ramos), médio porte (Sul brasileiro - 46 barras/79 ramos) e grande porte (Norte-Nordeste brasileiro - 87 barras/179 ramos) e seus resultados comparados com o resultado do algoritmo BT serial. Esta comparacão mostrou que os algoritmos propostos obtiveram um melhor desempenho, com alta eficiência. / This paper deals with the use of Tabu Search metaheurístic applied to solving the problem of transmission system expansion planning (TSEP), analyzed on the static point of view, with the development of parallel algorithms in the environment MPI (?Message Passing Interface ”). Tabu Search metaheurístic is a technique based on the control parameters, the structure of the neighborhood and its own algorithm with powerful search strategies. In this technique, given a configuration we want to progress to the best neighbor across the entrance and exit of branches, so getting the configuration incumbent. With this configuration which is regarded as the best configuration found so far, and this is a very good value, the system continuously seeking more settings to find a better than those found throughout the search. The parallel versions of the algorithms were developed from an advanced TS series algorithm on the paradigm of programming SPMD (Single Program Multiple Data), and they were tested for test systems small scale (Garver - bars 6/15 branches), medium scale (South Brazilian - 46 bars/79 branches) and large scale (North-Northeast Brazilian - 87 bars/179 branches), and their results compared with the result of the series algorithm TS. This comparison showed that the proposed algorithms obtained best performance and high efficiency.

Made available in DSpace on 2016-06-02T19:52:13Z (GMT). No. of bitstreams: 1 DissJMRB.pdf: 944400 bytes, checksum: b37a0f175baab577681e6785f305edee (MD5) Previous issue date: 2005-06-23 / This project consists in the refinement of the tabu search adaptive approach HTSA (PUREZA, 1996) and the analysis of its performance when applied to the classical Vehicle Routing Problem and to the Vehicle Routing Problem with Time Windows. HTSA promotes the integration of intensification and diversification strategies through the systematic variation of the values of selected tabu parameters, mostly based on the analysis of search trajectory patterns. The development of new implementations based on tabu search (GLOVER, 1989; GLOVER & LAGUNA, 1997) is an interesting avenue of research since tabu search has offered new marks on solution quality in routing problems, usually outperforming other methods. The results obtained with the application of HTSA approach to a set of classical routing instances and to a set of routing with times windows instances indicate quality solutions within reasonable computational times when compared to the results provided by competitive methods in the literature. / O corrente projeto tem como objetivo o refinamento da abordagem adaptativa de busca tabu HTSA (PUREZA, 1996) e a verificação de seu desempenho quando aplicada ao Problema de Roteirização de Veículos clássico e ao Problema de Roteirização com Janelas de Tempo. A abordagem HTSA tem como objetivo a integração de estratégias de intensificação e diversificação, consistindo na variação sistemática de valores de parâmetros tabu selecionados e apoiada principalmente na análise de padrões da trajetória da busca. O desenvolvimento de novas abordagens baseadas na meta-heurística busca tabu (GLOVER, 1989; GLOVER & LAGUNA, 1997) é uma linha de pesquisa interessante uma vez que a busca tabu tem oferecido novas marcas em qualidade da solução em problemas de Roteirização de veículos e suas variantes, geralmente superando outros métodos. Os resultados obtidos com a aplicação da abordagem HTSA a instâncias de roteirização de veículos clássicas e com janela de tempo indicam soluções de qualidade em tempos computacionais razoáveis quando comparadas aos resultados de métodos competitivos da literatura.