Neste trabalho é proposta uma nova técnica de solução para resolver o problema de planejamento da expansão de sistemas de transmissão estático através da introdução da tomada de decisão fuzzy. Na técnica apresentada neste trabalho, a tomada de decisão fuzzy é aplicada para o desenvolvimento de um algoritmo heurístico construtivo. O sistema fuzzy é utilizado para contornar alguns problemas críticos das heurísticas que utilizam o índice de sensibilidade como guia para inserção de novas linhas. A heurística apresentada nesse trabalho é baseada na técnica dividir para conquistar. Verificou-se que a deficiência das heurísticas construtivas é decorrente da decisão de inserir novas linhas baseada em valores não seguros encontrados através da solução do modelo utilizado. Para contornar tal deficiência, sempre que surgirem valores não seguros divide-se o problema original em dois subproblemas, um que analisa a qualidade da resposta para o caso em que a linha é inserida e outro para verificar a qualidade da resposta para o caso em que a linha não é inserida. A tomada de decisão fuzzy é utilizada para decidir sobre quando dividir o problema em dois novos subproblemas. Utilizou-se o modelo cc com a estratégia de Villasana-Garver-Salon para realizar a modelagem da rede elétrica para os problemas da expansão de sistemas de transmissão aqui propostos. Ao serem realizados testes em sistemas de pequeno, médio e grande portes certificou-se que o método pode encontrar a solução ótima de sistemas de pequeno e médio portes. Porém, a solução ótima dos sistemas de grande porte testados não foi encontrada. Para melhorar a qualidade da solução encontrada utilizou, em uma segunda fase, a metaheurística busca tabu. A busca tabu utiliza o modelo cc. Os resultados se mostraram bastante promissores. Os testes foram realizados em alguns sistemas reais brasileiros e com o sistema real colombiano. / A new solution technique to solve the long-term static transmission expansion planning (TEP) problem based on fuzzy decision making is proposed. The technique applies the concepts of fuzzy decision making in a constructive heuristic algorithm. The fuzzy system is used to circumvent some critical problems of heuristics that use sentivity indices as a guide for insertion and construction of new lines. The heuristic algorithm proposed in this work is based on the divide and conquer technique. It has been verified that the deficiency of the constructive heuristics is due to the decision of inserting new lines based only on information given by the index, which usually is calculated from a relaxed mathematical representation of the problem and can become less accurate during the solution process. In order to be able to deal with such problem, whenever the quality of the index decreases, the original problem is divided into two sub-problems: one examines the quality of the solution when the transmission line indicated by the sensitivity index is inserted and the other subproblem checks the opposite. Fuzzy decision-making is used to decide the moment to divide the problem into two subproblems based on other information. The hybrid linear model is used to model the long-term transmission expansion planning problem and is used in the proposed algorithm. Tests was done with systems of small-term, medium-term and long-term. The optimal solution of small-term and medium-term was foundo using just the construtive heuristic algorithm with fuzzy decision-making. To deal with long-term systems was used the solutions of the construtive heuristic algorithm with fuzzy decision-making to init a tabu search. The tabu search uses the dc model. The results are very promising. The test was done with some real brazilian systems and with the real colombian system.

Le covoiturage se présente comme une solution de transport alternative qui vient soigner l’image environnementale, économique et sociétale de la voiture personnelle. Le problème du covoiturage dynamique consiste à élaborer en temps réel des tournées de véhicules optimisés, afin de répondre au mieux aux demandes instantanées de transport.C’est dans ce cadre que s’inscrivent nos travaux où l’optimisation et le temps réel sont les maître-mots. Étant donné la complexité exponentielle du problème, nous optons pour des méthodes approximatives pour le résoudre. Nous présentons notre première contribution en proposant une métaheuristique basée sur la recherche tabou. L'algorithme utilise un système de mémoire explicite et plusieurs stratégies de recherches développées pour éviter le piégeage par des optimums locaux. Ensuite, nous introduisons notre deuxième contribution qui se présente sous la forme d’une approche évolutionnaire supportée par un codage dynamique et basée sur des opérateurs génétiques contrôlés. La complexité exponentielle du problème nous amène à dévoiler notre troisième méthodologie, en proposant une approche évolutionnaire originale dans laquelle les chromosomes sont définis comme des agents autonomes et intelligents. Grâce à un protocole de négociation puissant, les Agents Chromosomes gèrent les opérateurs génétiques et orientent la recherche afin de trouver des solutions optimales dans un temps de calcul réduit. Dans la perspective d’une meilleure combinaison entre le covoiturage et les autres modes de transport, nous concevons un système baptisé DyCOS, intégrant nos approches et applications dédiées à la résolution du problème du covoiturage dynamique. / Carpooling is presented as an alternative transport solution that comes treat environmental image, economic and societal personal car. The dynamic carpooling problem is to develop real-time optimized touring vehicles to better respond to the instantaneous transport demands.Our work belongs within this context, where optimization and real time are the key words. Given the exponential complexity of the dynamic ridematching problem, we opt for the approximate methods to solve it. We present our first contribution by proposing a metaheuristic based on the multi-criteria tabu search. The proposed algorithm employs an explicit memory system and several searching strategies developed to avoid the entrapment by local solutions. Afterward, we introduce our second contribution which is in the form of an evolutionary approach supported by a dynamic coding and based on controlled genetic operators. However, the exponential complexity of the problem leads us to consider that a simple metaheuristics is not sufficient to solve effectively the problem of dynamic ridematching. It is with this in mind that we are unveiling our third solving methodology by developing an original evolutionary approach in which chromosomes are defined as autonomous and intelligent agents. Thanks to an accurate protocol negotiation, the Chromosomes Agents can control the genetic operators and guide search for finding optimal solutions within a reasonable period of time. With the prospect of a better combination between carpooling and other modes of transport, we design a system called DyCOS, integrating our approaches and applications dedicated to solving the problem of dynamic ridesharing.

Dans le cadre de l'optimisation multiobjectif, les métaheuristiques sont reconnues pour être des méthodes performantes mais elles ne rencontrent qu'un succès modéré dans le monde de l'industrie. Dans un milieu où seule la performance compte, l'aspect stochastique des métaheuristiques semble encore être un obstacle difficile à franchir pour les décisionnaires. Il est donc important que les chercheurs de la communauté portent un effort tout particulier sur la facilité de prise en main des algorithmes. Plus les algorithmes seront faciles d'accès pour les utilisateurs novices, plus l'utilisation de ceux-ci pourra se répandre. Parmi les améliorations possibles, la réduction du nombre de paramètres des algorithmes apparaît comme un enjeu majeur. En effet, les métaheuristiques sont fortement dépendantes de leur jeu de paramètres. Dans ce cadre se situe l'apport majeur de TRIBES, un algorithme mono-objectif d'Optimisation par Essaim Particulaire (OEP) qui fonctionne automatiquement,sans paramètres. Il a été mis au point par Maurice Clerc. En fait, le fonctionnement de l'OEP nécessite la manipulation de plusieurs paramètres. De ce fait, TRIBES évite l'effort de les régler (taille de l'essaim, vitesse maximale, facteur d'inertie, etc.).Nous proposons dans cette thèse une adaptation de TRIBES à l'optimisation multiobjectif. L'objectif est d'obtenir un algorithme d'optimisation par essaim particulaire multiobjectif sans paramètres de contrôle. Nous reprenons les principaux mécanismes de TRIBES auxquels sont ajoutés de nouveaux mécanismes destinés à traiter des problèmes multiobjectif. Après les expérimentations, nous avons constaté, que TRIBES-Multiobjectif est moins compétitif par rapport aux algorithmes de référence dans la littérature. Ceci peut être expliqué par la stagnation prématurée de l'essaim. Pour remédier à ces problèmes, nous avons proposé l'hybridation entre TRIBES-Multiobjectif et un algorithme de recherche locale, à savoir le recuit simulé et la recherche tabou. L'idée était d'améliorer la capacité d'exploitation deTRIBES-Multiobjectif. Nos algorithmes ont été finalement appliqués sur des problèmes de dimensionnement des transistors dans les circuits analogiques / Meta-heuristics are recognized to be successful to deal with multiobjective optimization problems but still with limited success in engineering fields. In an environment where only the performance counts, the stochastic aspect of meta-heuristics again seems to be a difficult obstacle to cross for the decision-makers. It is, thus, important that the researchers of the community concern a quite particular effort to ease the handling of those algorithms. The more the algorithms will be easily accessible for the novices, the more the use of these algorithms can spread. Among the possible improvements, reducing the number of parameters is considered as the most challenging one. In fact, the performance of meta-heuristics is strongly dependent on their parameters values. TRIBES presents an attempt to remedy this problem. In fact, it is a particle swarm optimization (PSO) algorithm that works in an autonomous way. It was proposed by Maurice Clerc. Indeed, like every other meta-heuristic, PSO requires many parameters to be fitted every time a new problem is considered. The major contribution of TRIBES is to avoid the effort of fitting them. We propose, in this thesis, an adaptation of TRIBES to the multiobjective optimization. Our aim is to conceive a competitive PSO algorithm free of parameters. We consider the main mechanisms of TRIBES to which are added new mechanisms intended to handle multiobjective problems. After the experimentations, we noticed that Multiobjective-TRIBESis not competitive compared to other multiobjective algorithms representative of the state of art. It can be explained by the premature stagnation of the swarm. To remedy these problems, we proposed the hybridization between Multiobjective-TRIBES and local search algorithms such as simulated annealing and tabu search. The idea behind the hybridization was to improve the capacity of exploitation of Multiobjective-TRIBES. Our algorithms were finally applied to sizing analogical circuits' problems

Orientador: Sérgio Azevedo de Oliveira / Banca: José Roberto Sanches Mantovani / Banca: Fujio Sato / Resumo: 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. / Abstract: 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. / Mestre

Submitted by Silvana Teresinha Dornelles Studzinski (sstudzinski) on 2017-02-08T15:41:51Z No. of bitstreams: 1 Wagner Lourenzi Simões_.pdf: 1389162 bytes, checksum: 302aec842d2f4e8b0a7c78ecbae24357 (MD5) / Made available in DSpace on 2017-02-08T15:41:51Z (GMT). No. of bitstreams: 1 Wagner Lourenzi Simões_.pdf: 1389162 bytes, checksum: 302aec842d2f4e8b0a7c78ecbae24357 (MD5) Previous issue date: 2016-12-06 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Neste estudo, foi desenvolvida uma ferramenta computacional baseada em metaheurísticas para a otimização do sequenciamento de produção em Flow Shop permutacionais aplicados à montagem de placas eletrônicas que operam em ambientes High-Mix, Low-Volume. O ambiente High-Mix, Low-Volume exige a realização de um grande número de setups para atender à flexibilidade exigida. Esse elevado número de sucessivos setups para a produção de pequenos lotes impacta negativamente nos custos operacionais da empresa. Uma das formas de se obter vantagem ao lidar com um grande mix de produção é explorando características similares entre os produtos, de forma que, através de um sequenciamento adequado, seja possível reduzir o tempo total de parada para setup e, por consequência, reduzir também o tempo total de processamento (makespan). A literatura apresenta muitos exemplos de sucesso na aplicação de técnicas de otimização para o sequenciamento da produção como forma de ganho de vantagem competitiva. Porém, a complexidade e o grande esforço computacional exigidos na solução deste problema, por muitas vezes, inviabilizam sua aplicação na rotina das indústrias. Neste contexto, as metaheurísticas emergem como uma opção para a viabilização de ferramentas para otimização do sequenciamento de produção. Dentre as abordagens metaheurísticas existentes, destacam-se as abordagens híbridas que combinam estratégias de busca local com algoritmos evolutivos como opções para a geração, de forma rápida, de boas soluções para o problema de sequenciamento, ainda que estes métodos não possam garantir a otimalidade da solução. A ferramenta desenvolvida, baseada no uso combinado das metaheurísticas Busca Tabu e Algoritmo Genético, busca a melhor sequência possível dentro do tempo computacional disponível de forma a reduzir os tempos gastos com operações de tempo de setup, e consequentemente o makespan. O Algoritmo Hibrido foi avaliado utilizando instâncias da literatura e instâncias advindas de um caso real. Os resultados dos testes indicam a superioridade da abordagem híbrida sobre as abordagens canônicas do algoritmo Genético e Busca Tabu. Os resultados obtidos na avaliação de instâncias reais indicam a aplicabilidade da ferramenta em ambientes reais, obtendo bons resultados na otimização dos tempos de setup, mesmo para o sequenciamento de grandes quantidades de produtos diferentes. / This work proposes the development of a metaheuristics based computation tool, to solve the permutation flow shop scheduling problem (PFSSP) in the electronic manufacturing operating in High-mix, Low-volume enviroment. To operate in HMLV enviroment is demanded a large number of setup changes to comply the flexibility required. This elevated number of successive setup changes to produce little batches have negative impacts on the operation costs. One way for to obtain advantages handling a large product mix is to explore the similar features between this products. Through a proper scheduling we can reduce the total downtime to setup changes, and consequently reduces the process time (makespan). The literature brings many success examples in the production scheduling optimization as a way to obtain competitive advantages. But, the complexity and the computational effort demanded to solve this problems, sometimes, turns the practical application unfeasible in the factories routine. In this contexto emerges the metaheuristics as an option to viability this type of application. Among the mataheuristics approaches, outstands the hybrid approaches that combine local search strategies with evolutionary algorithms as a way to obtain good and fast solutions for the scheduling problems, although the optimality is not been guaranted. The tool proposed combine the metaheuristics Genetic Algorithm and Tabu Search to optimize the flow shop scheduling in the shortest possible time to allow the practical application in industry. The tool was evaluate based on quality metrics like makespan and mean setup time. The Hybrid Algorithm has been evaluated using instances of the literature and instances arising from a real case. The results of the tests indicate a superiority of the hybrid approach over canonical approaches of the Genetic algorithm and Tabu Search. The results obtained in the evaluation of real instances indicate an applicability of the tool in real environments, obtaining good results in the optimization of textit setup times, also for the sequencing of large products. The Hybrid Algorithm has been evaluated using instances of the literature and instances arising from a real case. The tests results indicate a superiority of the hybrid approach over canonical approaches of the Genetic algorithm and Tabu Search. The results obtained in the evaluation of real instances indicate an applicability of the tool in real environments, obtaining good results in the setup time optimization, also for the sequencing of large products.

This thesis examines the problem of the automated re-assembly of jigsaw puzzles. The objectives of this research are as follows: to provide a clear statement of the jigsaw puzzle re-assembly problem; to find out which solution technique is best suited to this problem; to determine the level of sensitivity of the proposed solution technique when solving different variations of this problem; and to explore solution methods for solving incomplete jigsaw puzzles (puzzles with missing pieces). The jigsaw puzzle re-assembly problem has been investigated only intermittently in the research literature. This work presents an extensive examination of the suitability and efficiency of the standard solution techniques that can be applied to this problem. A detailed comparison between different solution methods including Genetic Algorithms, Simulated Annealing, Tabu Search and Constraint Satisfaction Programming, shows that a constraint-based approach is the most efficient method of generating solutions to the jigsaw puzzle problem. The proposed re-assembly algorithm is successful. Consequently, it can be used in development of automated solution generators for other problems in the same domain, thus creating new theoretical and applied directions in this field of research. One potential theoretical line of research concerns jigsaw puzzles that do not have a complete set of puzzle pieces. These incomplete puzzles represent a difficult aspect of this problem that is outlined but can not be resolved in the current research. The computational experiments conducted in this thesis demonstrate that the proposed algorithm being optimised to re-assemble the jigsaw puzzles is not efficient when applied to the puzzles with missing pieces. Further work was undertaken to modify the proposed algorithm to enable efficient re-assembly of incomplete jigsaw puzzles. Consequently, an original heuristic strategy, termed Empty Slot Prediction, was developed to support the proposed algorithm, and proved successful when applied to certain sub-classes of this problem. The results obtained indicate that no one algorithm can be used to solve the multitude of possible scenarios involved in the re-assembly of incomplete jigsaw puzzles. Other variations of the jigsaw puzzle problem that still remain unsolved are presented as avenues for future research. The solution of this problem involves a number of procedures with significant applications in other computer-related areas such as pattern recognition, feature and shape description, boundary-matching, and heuristic modelling. It also has more practical applications in robotic vision and reconstruction of broken artefacts in archaeology.

<p>The transportation cost of logs from forest to customers is a large part of the overall cost for the Swedish forestry industry. Finding good routes from harvesting points to saw and pulp mills is a complex task, where the total number of feasible routes is extremely high. In this thesis we present two methods for log truck scheduling. </p><p>The first is to, from a given set of routes, find the most valuable subset that fulfils the customers demand. We use a model that is similar to the set partitioning problem and a method that is referred to as a composite pricing coupled with Branch and Bound. The composite pricing based method prices the routes (columns) and chooses the most valuable ones that are then added to the LP relaxation. Once an LP optimum is found, the Branch and Bound method is used to find an integer optimum solution. We have tested this on a case of realistic size. </p><p>The second method is a tabu search heuristic. Here, the purpose is to create efficient and qualitative routes from a given number of trips (referred to as predefined trips). From a start solution tabu search systematically generates new solutions. This method was tested on a small problem and on a five times larger problem to study how the size of the problem affected the result. It was also tested and compared on two cases in which the backhauling possibilities (i.e. instead of traveling empty the truck picks up another load on the return trip) had and had not been studied. The composite pricing based method and the tabu search method proved to be very useful for this kind of scheduling.</p>

There is a growing interest in investigating the high order contingency events that may result in large blackouts, which have been a great concern for power grid secure operation. The actual number of high order contingency is too huge for operators and planner to apply a brute-force enumerative analysis. This thesis presents a heuristic searching method based on particle swarm optimization (PSO) and tabu search to select severe high order contingencies. The original PSO algorithm gives an intelligent strategy to search the feasible solution space, but tends to find the best solution only. The proposed method combines the original PSO with tabu search such that a number of top candidates will be identified. This fits the need of high order contingency screening, which can be eventually the input to many other more complicate security analyses. Reordering of branches of test system based on severity of N-1 contingencies is applied as a pre-processing to increase the convergence properties and efficiency of the algorithm. With this reordering approach, many critical high order contingencies are located in a small area in the whole searching space. Therefore, the proposed algorithm tends to concentrate in searching this area such that the number of critical branch combinations searched will increase. Therefore, the speedup ratio is found to increase significantly. The proposed algorithm is tested for N-2 and N-3 contingencies using two test systems modified from the IEEE 118-bus and 30-bus systems. Variation of inertia weight, learning factors, and number of particles is tested and the range of values more suitable for this specific algorithm is suggested. Although illustrated and tested with N-2 and N-3 contingency analysis, the proposed algorithm can be extended to even higher order contingencies but visualization will be difficult because of the increase in the problem dimensions corresponding to the order of contingencies.

The transportation cost of logs from forest to customers is a large part of the overall cost for the Swedish forestry industry. Finding good routes from harvesting points to saw and pulp mills is a complex task, where the total number of feasible routes is extremely high. In this thesis we present two methods for log truck scheduling. The first is to, from a given set of routes, find the most valuable subset that fulfils the customers demand. We use a model that is similar to the set partitioning problem and a method that is referred to as a composite pricing coupled with Branch and Bound. The composite pricing based method prices the routes (columns) and chooses the most valuable ones that are then added to the LP relaxation. Once an LP optimum is found, the Branch and Bound method is used to find an integer optimum solution. We have tested this on a case of realistic size. The second method is a tabu search heuristic. Here, the purpose is to create efficient and qualitative routes from a given number of trips (referred to as predefined trips). From a start solution tabu search systematically generates new solutions. This method was tested on a small problem and on a five times larger problem to study how the size of the problem affected the result. It was also tested and compared on two cases in which the backhauling possibilities (i.e. instead of traveling empty the truck picks up another load on the return trip) had and had not been studied. The composite pricing based method and the tabu search method proved to be very useful for this kind of scheduling.

Abstract This dissertation presents a new algorithm by integrating evolutionary programming (EP), tabu search (TS) and quadratic programming (QP), named the evolutionary-tabu quadratic programming (ETQ) method, to solve the nonconvex economic dispatch problem (NED). This problem involves the economic dispatch with valve-point effects (EDVP), economic dispatch with piecewise quadratic cost function (EDPQ), and economic dispatch with prohibited operating zones (EDPO). EDPV, EDPQ and EDPO are similar problems when ETQ was employed. The problem was solved in two phases, the cost-curve-selection subproblem, and the typical ED solving subproblem. The first phase was resolved by using a hybrid EP and TS, and the second phase by QP. In the solving process, EP with repairing strategy was used to generate feasible solutions, TS was used to prevent prematurity, and QP was used to enhance the performance. Numerical results show that the proposed method is more effective than other previously developed evolutionary computation algorithms.