Orientador: Fábio Bertequini Leão / Resumo: Neste trabalho propõe-se um modelo matemático de Programação Não Linear Binária (PNLB) para resolver o problema de alocação ótima de dispositivos indicadores de falta (OPFI – Optimal Placement of Fault Indicator Devices) em redes radiais de distribuição de energia elétrica. O problema é modelado por meio de uma função objetivo que considera dois custos conflitantes: o Custo da Energia Não Suprida (CENS) e o Custo de Investimento em Sensores (CINV). O modelo matemático proposto pode ser resolvido por métodos exatos e para todos os testes simulados foram utilizados os softwares de programação matemática AMPL (A Mathematical Programming Language) e KNITRO versão 9.0.0. Para validação do método proposto, são realizados testes em um sistema de distribuição de 19 barras, e em outros dois sistemas de 34 e 70 barras, sendo que nesses dois sistemas os indicadores de falta foram alocados apenas no tronco principal desses alimentadores. Os resultados obtidos mostram que o modelo matemático é adequado para resolver o problema formulado. Assim, o método proposto traz contribuição à literatura, visto que o problema da alocação ótima desses dispositivos tem sido resolvido principalmente por meio de técnicas meta-heurísticas. / Abstract: This paper proposes a Binary Nonlinear Programming model to solve the problem of Optimal Placement of Fault Indicator Devices (OPFI) in radial distribution networks. The problem is modeled by an objective function that considers two conflicting costs: Cost of Energy Not Supplied and Cost of Investing in Sensors. The proposed mathematical model can be solved by exact methods and for all the simulated tests the mathematical programming software AMPL (A Mathematical Programming Language) and KNITRO version 9.0.0 were used. For validation of the proposed method, tests are performed in a 19-bar distribution system, and in two other systems of 34 and 70 bars, where in these two systems fault indicators were only allocated to the main trunk of these feeders. The results obtained show that the mathematical model is adequate to solve the problem formulated. Thus, the proposed method brings contribution to the literature, since the problem of optimal allocation of these devices has been solved mainly by means of metaheuristic techniques. / Mestre

Afin de pouvoir subvenir aux futurs besoins en matière de transport aérien il est nécessaire d'augmenter la capacité de l'espace aérien. Les contrôleurs aériens, qui occupent une place centrale dans la gestion du trafic, doivent quotidiennement faire face à des situations conflictuelles (conflits) lors desquelles deux vols risquent de violer les normes de séparation en vigueur si aucune modification de trajectoire n'est envisagée. La détection et la résolution des conflits potentiels contribuent à augmenter la charge de travail des contrôleurs et peuvent potentiellement les conduire à diriger les vols vers des zones moins denses de l'espace aérien, induisant a posteriori un retard pour les vols. Le problème de la capacité de l'espace aérien peut donc être abordé en régulant les flux de trafic de façon réduire la quantité de conflits aériens. L'objectif de cette thèse est de mettre au point une méthodologie destinée à minimiser les risques de conflits aériens en modifiant légèrement les vitesses des appareils. Cette approche est principalement motivée par les conclusions du projet ERASMUS portant sur la régulation de vitesse subliminale. Ce type de régulation a été conçu de façon à ne pas perturber les contrôleurs aériens dans leur tâche. En utilisant de faibles modulations de vitesse, imperceptibles par les contrôleurs aériens, les trajectoires des vols peuvent être modifiées pour minimiser la quantité totale de conflits et ainsi faciliter l'écoulement du trafic dans le réseau aérien. La méthode retenue pour mettre en œuvre ce type de régulation est l'optimisation sous contrainte. Dans cette thèse, nous développons un modèle d'optimisation déterministe pour traiter les conflits à deux avions. Ce modèle est par la suite adapté à la résolution de grandes instances de trafic en formulant le modèle comme un Programme Linéaire en Nombres Entiers. Pour reproduire des conditions de trafic réalistes, nous introduisons une perturbation sur la vitesse des vols, destinée à représenter l'impact de l'incertitude en prévision de trajectoire dans la gestion du trafic aérien. Pour valider notre approche, nous utilisons un outil de simulation capable de rejouer des journées entières de trafic au dessus de l'espace aérien européen. Les principaux résultats de ce travail démontrent les performances du modèle de détection et de résolution de conflits et soulignent la robustesse de la formulation face à l'incertitude en prévision de trajectoire. Enfin, l'impact de notre approche est évalué à travers divers indicateurs propres à la gestion du trafic aérien et valide la méthodologie développée. / As global air traffic volume is continuously increasing, it has become a priority to improve air traffic control in order to deal with future air traffic demand. One of the current challenges regarding air traffic management is the airspace capacity problem, which is acknowledged to be correlated to air traffic controllers' workload. Air traffic controllers stand at the core of the traffic monitoring system and one of their main objective is to ensure the separation of aircraft by anticipating potential conflicts. Conflict detection and resolution are likely to increase workload and may lead them to reroute aircrafts to less dense areas, triggering off flight delay. The airspace capacity problem can hence be tackled by regulating air traffic flow in order to reduce the global conflict quantity. The objective of this thesis is to develop a methodology aiming at minimizing potential conflicts quantity by slightly adjusting aircraft speeds in real time. This approach is mainly motivated by conclusions of the ERASMUS project on subliminal speed control, which was designed to keep air traffic controllers unaware of the ongoing regulation process. By focusing on low magnitude speed modulations, aircraft trajectories can be modified to reduce the quantity of conflicts and smoothen air traffic flow in the airspace network. The method used to carry out this type of regulation is constraint optimization. In this thesis, we develop a deterministic optimization model for two-aircraft conflicts which is then adapted to large scale instances using Mixed-Integer Linear Programming. In order to reproduce realistic navigation conditions, uncertainty on aircraft speeds is introduced with the goal of modeling the impact of trajectory prediction uncertainty in air traffic management. To validate our approach, a simulation device capable of simulating real air traffic data over the European airspace is used. Main results of this work reveal a significant conflict quantity reduction and demonstrate the robustness of the developed model to the uncertainty in trajectory prediction. Finally, the impact of our model on air traffic flow is measured through several air traffic management indicators and validates the proposed methodology.

Deposição é um fenômeno indesejável que ocorre na superfície dos trocadores de calor ao longo de sua operação, ocasionando redução na efetividade térmica e aumento da resistência ao escoamento nestes equipamentos. Estes efeitos trazem grandes consequências econômicas e ambientais, devido ao aumento dos custos operacionais (energia adicional é requerida), aumento dos custos de projeto (demanda por equipamentos de maior área de troca térmica), limitações hidráulicas (que pode levar a uma diminuição da carga processada) e aumento das emissões (aumento da queima de combustíveis fósseis para suprir a energia adicional requerida). Neste contexto, o presente trabalho tem por objetivo fornecer ferramentas computacionais robustas que apliquem técnicas de otimização para o gerenciamento da deposição em redes de trocadores de calor, visando minimizar os seus efeitos negativos. Estas ferramentas foram desenvolvidas utilizando programação matemática no ambiente computacional GAMS, e três abordagens distintas para a resolução do problema da deposição foram pesquisadas. Uma delas consiste na identificação do conjunto ótimo de trocadores de calor a serem limpos durante uma parada para manutenção da planta, visando restaurar a carga térmica nesses equipamentos através da remoção dos depósitos existentes. Já as duas outras abordagens consistem em otimizar a distribuição das vazões das correntes ao longo de ramais paralelos, uma de forma estacionária e a outra de forma dinâmica, visando maximizar a recuperação de energia ao longo da rede. O desempenho destas três abordagens é ilustrado através de um conjunto de exemplos de redes de trocadores de calor, onde os ganhos reais obtidos com estas ferramentas de otimização desenvolvidas são demonstrados / Fouling is an undesirable phenomenon that occurs over the surface of heat exchangers during its operation, causing reduction of thermal effectiveness and increase of flow resistance along these equipment. These effects bring large economics and environmental consequences, due to the increase of operational costs (additional energy is required), increase of project costs (demand of equipment with larger thermal exchange areas), hydraulic limitations (that can diminish the process throughput) and increase of emissions (increase of fossil fuel firing to supply the additional energy required). In this context, the objective of this work is to provide robust computational tools that apply optimization techniques for fouling management on heat exchanger networks, aiming to reduce its negative effects. These tools were developed using mathematical programming on GAMS software, and three distinct approaches for the resolution of the fouling problem were investigated. One of them consists in the identification of the optimal set of heat exchangers that have to be cleaned during a plant maintenance shutdown, aiming to restore the thermal load in these equipment through the removal of the existent deposits. The other approaches consist in to optimize the distribution of flow rates of the streams along parallel branches, using stationary and dynamic models, in order to maximize the energy recovery in the network. The performance of these three approaches is illustrated through examples of heat exchanger networks, where the real gains obtained with these optimization tools are demonstrated

Made available in DSpace on 2014-12-17T14:53:06Z (GMT). No. of bitstreams: 1 IsaacFF_DISSERT.pdf: 1166658 bytes, checksum: 2cf318ebd7fdf1f86eeab55fd1fe0aa0 (MD5) Previous issue date: 2010-12-22 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior / The objective in the facility location problem with limited distances is to minimize the sum of distance functions from the facility to the customers, but with a limit on each distance, after which the corresponding function becomes constant. The problem has applications in situations where the service provided by the facility is insensitive after a given threshold distance (eg. fire station location). In this work, we propose a global optimization algorithm for the case in which there are lower and upper limits on the numbers of customers that can be served / O objetivo no problema de localiza??o de uma facilidade com dist?ncias limitadas ? minimizar a soma das dist?ncias da facilidade para seus clientes, por?m com um limite em cada uma das dist?ncias onde, ap?s esse limite, o impacto na fun??o objetivo torna-se constante. O problema tem aplica??es em situa??es onde o servi?o fornecido pela facilidade ? indiferente depois de um limiar maximo (ex. localiza??o de um corpo de bombeiros). Nesta disserta??o, s?o propostos algoritmos de otimiza??o global para o caso em que existem limites inferior e superior no numero de clientes atendidos

A geração de quadros de horários escolares é um problema clássico de otimização que tem sido largamente estudado devido a sua importâncias prática e teórica. O problema consiste em alocar um conjunto de aulas entre professor-turma em períodos de tempo pré-determinados, satisfazendo diferentes tipos de requisitos. Devido a natureza combinatória do problema, a resolução de instâncias médias e grandes torna-se uma tarefa desafiadora. Quando recursos são escassos, mesmo uma solução factível pode ser difícil de ser encontrada. Várias técnicas tem sido propostas na literatura científica para resolver o problema de geração de quadros de horários escolares, no entanto, métodos robustos ainda não existem. Visto que o uso de métodos exatos, como por exemplo, técnicas de programação matemática, não podem ser utilizados na prática, para resolver instâncias grandes da realidade, meta-heurísticas e meta-heurísticas híbridas são usadas com frequência como abordagens de resolução. Nesta pequisa, são desenvolvidas técnicas que combinam programação matemática e heurísticas, denominadas mateheurísticas, para resolver de maneira eficiente e robusta algumas variações de problemas de geração de quadros de horários escolares. Embora neste trabalho sejam abordados problemas encontrados no contexto de instituições brasileiras, os métodos propostos também podem ser aplicados em problemas similares oriundo de outros países. / The school timetabling is a classic optimization problem that has been extensively studied due to its practical and theoretical importance. It consists in scheduling a set of class-teacher meetings in a prefixed period of time, satisfying requirements of different types. Given the combinatorial nature of this problem, solving medium and large instances of timetabling to optimality is a challenging task. When resources are tight, it is often difficult to find even a feasible solution. Several techniques have been developed in the scientific literature to tackle the high school timetabling problem, however, robust solvers do not exist yet. Since the use of exact methods, such as mathematical programming techniques, is considered impracticable to solve large real world instances, metaheuristics and hybrid metaheuristics are the most used solution approaches. In this research we develop techniques that combine mathematical programming and heuristics, so-called matheuristics, to solve efficiently and in a robust way some variants of the high school timetabling problem. Although we pay special attention to problems arising in Brazilian institutions, the proposed methods can also be applied to problems from different countries.

A presente pesquisa aborda um problema de roteirização e programação de veículos incorporando uma nova restrição operacional: a requisição simultânea de múltiplos veículos para atendimento da demanda. Trata-se de uma característica encontrada em operações de apoio à exploração de petróleo \"offshore\", em que mais de uma embarcação é requerida para executar tarefas de reboque e lançamento de linhas de ancoragem. Esta imposição, somada às restrições de janela de tempo, precedência entre tarefas, autonomia das embarcações e atendimento integral da demanda, configuram este problema. A programação é orientada pela minimização dos custos variáveis da operação e dos custos associados ao nível de serviço no atendimento. Este problema é uma variação do problema clássico de roteirização e programação de veículos com janela de tempo, de classe NP-Difícil. Nesta pesquisa, propõe-se modelar e resolver o problema em escala real por meio do algoritmo \"branch and cut\" acoplado às heurísticas de busca em vizinhança \"local branching\" e \"variable neighborhood search\". Para gerar as soluções iniciais será empregado o método \"feasibility pump\" e uma heurística construtiva. / This research focuses a fleet scheduling problem with new operational constraints: each task requiring multiple types of vehicles simultaneously. This kind of operation occurs in offshore exploitation and production sites, when more than one vessel is needed to accomplish the tugging and mooring of oil platforms. Other constraints are maintained such as time windows, precedence between tasks, route duration and the demand attendance. The solution schedules are cost oriented, which encompasses the routing variable costs and the customer service costs. This is a variation of the classical fleet routing and scheduling, which is an NP-Hard problem. This research aims to solve the real scale problem through a combined use of branch and cut strategy with local search algorithms such as local branching and variable neighborhood search. An efficient heuristic rule will be used in order to generate initial solutions using the feasibility pump method.

Orientadores: Akebo Yamakami, Luiza Amalia Pinto Cantão / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-05T00:06:55Z (GMT). No. of bitstreams: 1 Silva_RicardoCoelho_M.pdf: 524540 bytes, checksum: f7f63ffea96b8bbf8897b3c3f27fc427 (MD5) Previous issue date: 2005 / Resumo: Neste trabalho foram desenvolvidos alguns métodos iterativos e algoritmos meta-heurísticos, adaptados de modelos clássicos, que solucionam problemas de programação não-linear com parâmetros fuzzy na função objetivo e no conjunto de restrições. Apresentamos aqui uma relação entre alguns destes métodos iterativos e uma abordagem diferenciada das restrições de igualdade com parâmetros fuzzy. Comprovamos a eficiência dos algoritmos propostos comparando os seus resultados com os encontrados na literatura / Abstract: In this work we develop some iterative methods and meta-heuristic algorithms that solve the nonlinear programming problems with uncertainties in the objective function and in the set of constraints. We derive a relation among some of this iterative methods and introduce a novel approach to the equality constraints with uncertainties. Selected examples from the literature are presented to validate the efficiency of the methods and algorithms addressed. / Mestrado / Telecomunicações e Telemática / Mestre em Engenharia Elétrica

Orientadores: Akebo Yamakami, Jose Luis Verdegay Galdeano / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-14T06:44:19Z (GMT). No. of bitstreams: 1 Silva_RicardoCoelho_D.pdf: 1144878 bytes, checksum: 38379443fb6892fd6eda74c55c3b99dc (MD5) Previous issue date: 2009 / Resumo: O objetivo deste trabalho é buscar, estudar e estabelecer as condições de otimali-dade para resolver problemas de programação multi-objetivo irrestritos e restritos em um ambiente impreciso. Essas imprecisões estão presentes nos problemas da vida real e existem muitas formas de tratá-las, mas nesse trabalho será usado a teoria de conjuntos nebulosos. Utilizando como base a otimização nebulosa, foram desenvolvidas duas abordagens para resolver problemas multi-objetivo nebulosos. A primeira abordagem transforma um problema nebuloso em um problema clássico paramétrico com um número maior de funções objetivo, a qual é chamada de paramétrica. A segunda abordagem, chamada de possibilística, usa a teoria de possibilidade como um índice de comparação entre números nebulosos com a finalidade de garantir condições de otimalidade em um ambiente nebuloso. Alguns exemplos numéricos são resolvidos usando um algoritmo genético chamado NSGA-II elitista, com algumas modificações para a comparação de números nebulosos, e depois feita uma análise dos resultados encontrados por ambos os enfoques. / Abstract: The main goal of this work is to search, study and present the optimality conditions to solve the unconstraint and constraint multiobjetive programming problems in imprecise environment. These imprécisions can be found in the real-world optimization problems and there are utmost ways for dealing with them, but in this work will be used the theory of fuzzy sets. Using as a basis the fuzzy optimization, two approaches were developed to solve fuzzy multiobjective problems. The first approach transforms a fuzzy problem into a parametric classic multiobjective programming problem with many more objective functions, which is called parametric approach. The second one, called possibilistic, uses the possibility theory as a comparison index between two fuzzy numbers in order to ensure optimality conditions in a fuzzy environment. Some numerical examples are solved by using a genetic algorithm called elitist NSGA-II with some modifications to compare fuzzy numbers, and then the results obtained with both approaches are analysed. / Doutorado / Automação / Doutor em Engenharia Elétrica

Orientadores: Akebo Yamakami, Ricardo Coelho Silva / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-25T08:18:04Z (GMT). No. of bitstreams: 1 Verga_Juliana_D.pdf: 1085866 bytes, checksum: 6325aac2b413dfa3fc773ecc3791388c (MD5) Previous issue date: 2014 / Resumo: A teoria de grafos é comumente utilizada na área da engenharia para resolver problemas que podem ser representados na forma de redes. Dentre diversos problemas abordados, o problema de transporte multimodal é um dos que podem ser modelados por grafos. Este trabalho apresenta três algoritmos para redes de transporte multimodal aplicados ao tráfego urbano. O primeiro algoritmo é de carregamento incremental de fluxo e aborda incertezas nos custos e nas capacidades dos arcos utilizando a teoria dos conjuntos fuzzy. Neste caso, o problema foi modelado através de subgrafos, onde cada modo de transporte considerado é representado por um subgrafo e o grafo total é a união de todos os subgrafos. O segundo é um algoritmo de caminho mínimo para grafos coloridos com custos crisp e é baseado no algoritmo clássico de caminho mínimo de Ford-Moore-Bellman. O terceiro algoritmo é de carregamento incremental de fluxo e utiliza o segundo algoritmo para encontrar os caminhos mínimos multimodais. Neste caso os custos e capacidades são crisp e assim como no primeiro algoritmo, os custos dependem do fluxo. A modelagem com relação ao segundo e ao terceiro algoritmo, foi feita utilizando grafos coloridos, onde cada modo de transporte é representado por uma cor / Abstract: The graph theory is commonly used in the area of engineering to solve problems that can be represented in the form of networks. Among several problems, the multimodal transport problem is one that can be modeled by graphs. This work presents three algorithms for multimodal transport networks applied to urban traffic. The first algorithm is of incremental loading flow and deals uncertainties in costs and in capacities of arcs using the fuzzy sets theory. In this case the problem was modeled by subgraphs, where each mode of transport considered is represented by a subgraph and the total graph is the union of all subgraphs. The second, is an algorithm of shortest path for colored graphs with crisp costs and is based in the classical shortest path algorithm of Ford-Moore-Bellman. The third algorithm is of incremental loading flow and uses the second algorithm to find the multimodal shortest paths. In this case the costs and the capacities are crisp and thus in the first algorithm, the costs depend on the flow. The modeling with respect to the second and third algorithm was done using colored graphs, where each transport mode is represented by a color / Doutorado / Automação / Doutora em Engenharia Elétrica

The consumer market of today is characterized by emphasis on superior customer satisfaction and personalization of services. This entails higher customer expectations on organizations, which also includes the workforce scheduling processes in which the consumers expect more decision-power to dictate what they want, when and where they want services to be delivered. For organizations that deliver on-site services, the routing aspect becomes an important part of the scheduling process. Literature on Workforce Scheduling and Routing Problems (WSRP) seldom relate to characteristics of the more dynamic consumer market. As the markets and consumer needs become more flexible, the relevance for research concerning these characteristics increases. This study addresses this by reviewing current literature and present common solution methodologies applied to WSRP, as well as the effects of the online scheduling characteristics. With this as a foundation, a discussion is provided of how WSRP and online scheduling can be combined in order to improve resource utilization and minimize travel time for an on-site service provider. The overall aim of the study is to investigate how an online WSRP with exact time windows can be formulated and solved. The result is a four-stage hybrid method including linear integer programming and constructive heuristics with the objective to minimize travel time, idle time, and the makespan in the schedules. A case study has been conducted on an on-site service provider, and by applying the proposed hybrid methodology on the case company’s scheduling process, results have been obtained that demonstrates improvements of travel time and resource utilization. The study also demonstrate that the appliance of flexible travel times and product dependent service times have positive impact on the quality of the generated schedules. A key insight is that organizations working with exact time windows have to be aware of the trade-off between customer preferences and operational efficiency in day-to-day operations. Thus, organizations have to decide what holds most importance to the organization’s long-term success.