Thesis (M.A.)--University of North Carolina at Wilmington, 2005. / Includes appendixes. Includes bibliographical references (leaves: [86]-94)

The current scenario of the Brazilian electricity sector, through the constant and recent regulatory changes imposed by ANEEL in recent years, aims to ensure continuous improvement in quality standards in the provision of electricity, significantly increased surveillance on the power quality delivered to consumers. Following this guideline, ANEEL established X Factor, which set the minimum volume of investments required to electricity distribution companies. In 2010, through the PRORET ANEEL established a new methodology for the calculation of the X Factor, including the Q component, relating to quality of service, setting a milestone in the recent regulatory history of the Brazilian electricity sector, as it allows for the first time gains the annual tariff adjustment or loss according to the performance measured in the year. In this context of regulatory innovations and increasing demands with performance standards and levels of investment made on the electrical system, the correct and efficient use of increasingly scarce resources to improve and expand the electrical system are presented as a vital challenge to financial health of companies. This paper presents a methodology for prioritizing investments in primary networks of electricity distribution, involving two consolidated methodologies aid to decision-making high complexity (AHP and PROMETHEE) and operations research methods to optimize the planning of improvement works to be held in short-term horizon, with direct reflection on regulatory issues, seeking still accommodate regional characteristics of the company and the ability to execute works of each region. / O atual cenário do setor elétrico brasileiro, através das constantes e recentes alterações regulatórias impostas pela ANEEL nos últimos anos, tem como objetivo garantir a melhoria contínua nos padrões de qualidade no fornecimento de energia elétrica, aumentado significativamente a fiscalização sobre a qualidade da energia entregue aos consumidores. Seguindo esta diretriz, a ANEEL instituiu o Fator X, que define o volume de investimentos mínimos exigidos às empresas de distribuição de energia elétrica. Em 2010, através do PRORET a ANEEL estabeleceu uma nova metodologia para o cálculo do Fator X, incluindo o componente Q, referente à qualidade do serviço prestado, configurando como um marco no recente histórico regulatório do setor elétrico brasileiro, pois permite pela primeira vez ganhos no reajuste tarifário anual ou perdas de acordo com o desempenho medido no ano. Neste contexto de inovações regulatórias e exigências cada vez maiores com os padrões de desempenho e níveis de investimentos realizados no sistema elétrico, a aplicação correta e eficiente dos cada vez mais escassos recursos disponíveis para melhoria e ampliação do sistema elétrico se apresentam como um desafio vital à saúde financeira das empresas do setor elétrico. Este trabalho apresenta uma metodologia para priorização de investimentos em redes primárias de distribuição de energia elétrica, associando duas consolidadas metodologias de auxílio à tomada de decisões de elevada complexidade (AHP e PROMETHEE) e métodos de pesquisa operacional para otimização no planejamento de obras de melhoria a serem realizadas no horizonte de curto prazo, com reflexo direto nas questões regulatórias, buscando ainda contemplar características regionais da empresa e a capacidade de execução de obras de cada região.

[pt] A indústria de transporte marítimo é essencial para o comércio internacional. No entanto, no despertar da crise financeira de 2008, essa indústria foi severamente atingida. Nessas ocasiões, empresas de transporte só são capazes de obter lucro se suas frotas forem roteadas de forma eficaz. Neste trabalho, nós estudamos uma classe de problemas de roteamento de navios relacionados ao Pickup and Delivery Problem with Time Windows. Para resolver esses problemas, nós introduzimos um método heurístico e um exato. O método heurístico é uma meta-heurística híbrida com uma vizinhança larga baseada em set partitioning, enquanto o método exato é um algoritmo de branch-and-price. Nós conduzimos experimentos em um conjunto de instâncias baseadas em rotas de navios reais. Os resultados obtidos mostram que nossos algoritmos superam as metodologias estado da arte. Em seguida, nós adaptamos o conjunto de instâncias para modelar um problema de roteamento de navios no qual a velocidade em cada segmento de rota é uma variável de decisão, e o consumo de combustível por unidade de tempo é uma função convexa da velocidade e carga do navio. A fim de resolver esse novo problema de roteamento de navios com otimização de velocidade, nós estendemos nossa meta-heurística para encontrar decisões de velocidade ótimas em toda avaliação de solução vizinha de uma busca local. Nossos experimentos demonstram que essa abordagem pode ser altamente rentável, e que requer apenas um aumento moderado de recursos computacionais. / [en] The shipping industry is essential for international trade. However, in the wake of the 2008 financial crisis, this industry was severely hit. In these times, transportation companies can only obtain profit if their fleet is routed effectively. In this work, we study a class of ship routing problems related to the Pickup and Delivery Problem with Time Windows. To solve these problems, we introduce a heuristic and an exact method. The heuristic method is a hybrid metaheuristic with a set-partitioning-based large neighborhood, while the exact method is a branch-and-price algorithm. We conduct experiments on a benchmark suite based on real-life shipping segments. The results obtained show that our algorithms largely outperform the state-of-the-art methodologies. Next, we adapt the benchmark suite to model a ship routing problem where the speed on each sailing leg is a decision variable, and fuel consumption per time unit is a convex function of the ship speed and payload. To solve this new ship routing problem with speed optimization, we extend our metaheuristic to find optimal speed decisions on every local search move evaluation. Our computational experiments demonstrate that such approach can be highly profitable, with only a moderate increase in computational effort.

Submitted by Lara Oliveira (lara@ufersa.edu.br) on 2018-03-15T21:26:01Z No. of bitstreams: 1 JonathanLS_DISSERT.pdf: 6143092 bytes, checksum: 68ad13bf204320bdcea5907ddb8d2102 (MD5) / Approved for entry into archive by Vanessa Christiane (referencia@ufersa.edu.br) on 2018-06-18T16:59:44Z (GMT) No. of bitstreams: 1 JonathanLS_DISSERT.pdf: 6143092 bytes, checksum: 68ad13bf204320bdcea5907ddb8d2102 (MD5) / Approved for entry into archive by Vanessa Christiane (referencia@ufersa.edu.br) on 2018-06-18T16:59:51Z (GMT) No. of bitstreams: 1 JonathanLS_DISSERT.pdf: 6143092 bytes, checksum: 68ad13bf204320bdcea5907ddb8d2102 (MD5) / Made available in DSpace on 2018-06-18T16:59:58Z (GMT). No. of bitstreams: 1 JonathanLS_DISSERT.pdf: 6143092 bytes, checksum: 68ad13bf204320bdcea5907ddb8d2102 (MD5) Previous issue date: 2017-08-23 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / 2018-03-15 / Os problemas de corte de materiais são recorrentes no cotidiano da indústria, sendo encontrados nas mais diferentes formas.Oproblema de corte bidimensional guilhotinado é uma dessas formas. Ele surge pelas restrições da ferramenta de corte, tipicamente a guilhotina. Este trabalho apresenta três abordagens para solucionar o problema em questão: uma abordagem matemática, uma abordagem exata computacional e uma abordagem heurística. A abordagem matemática consiste em um modelo de programação linear baseado em listas de itens e montagem do arranjo de corte partindo dos itens, unindo-os dois a dois, tentando maximizar o número de uniões sem ultrapassar as dimensões da placa. A abordagem exata computacional tratá-se de um algoritmo Branch-and-Bound modificado para permitir que estados mais promissores possam ser analisados antes, comportando-se como um algoritmo de busca em profundidade com uma pequena etapa em largura, na qual ordena os filhos na árvore de decisão pelo desperdício gerado. Por fim, a abordagem heurística é composta das metaheurísticas GRASP, Busca Tabu, Algoritmo Genético, BRKGA e Religação de Caminhos combinados com uma heurística de montagem baseada nos algoritmos propostos por Nascimento, Longo e Aloise (1999). Essas metaheurísticas foram combinadas em um time assíncrono para alcançar melhores resultados que os já encontrados na literatura. Além de melhorar os resultados conhecidos, a pesquisa também tinha como objetivo apresentar um modelo viável, em número de variáveis, e resultados ótimos para instâncias comumente utilizadas para o problema supracitado e novas opções de obtê-los em instâncias que venham a surgir no futuro. Testes mostraram a competividade dos algoritmos propostos frente aos melhores resultados encontrados, reduzindo inclusive o número total de placas, bem como a capacidade dos métodos exatos propostos de encontrar as soluções ótimas para as instâncias testadas. Cerca de de 25% dos resultados ótimos foram encontrados, passando esse número para 75%, quando considerados os resultados dos algoritmos metaheurísticos que atingiram o limite inferior das instâncias

ALVES, Alexsandro de Oliveira. Integração de heurísticas lagrangeanas com algoritmos exatos para a otimização de particionamento de conjuntos. 2007. 49 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Departamento de Computação, Fortaleza-CE, 2007. / Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-05-20T18:05:04Z No. of bitstreams: 1 2007_dis_aoalves.pdf: 434539 bytes, checksum: d7550e0ddf22c4c083e44734e59375f7 (MD5) / Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-05-20T18:08:40Z (GMT) No. of bitstreams: 1 2007_dis_aoalves.pdf: 434539 bytes, checksum: d7550e0ddf22c4c083e44734e59375f7 (MD5) / Made available in DSpace on 2016-05-20T18:08:40Z (GMT). No. of bitstreams: 1 2007_dis_aoalves.pdf: 434539 bytes, checksum: d7550e0ddf22c4c083e44734e59375f7 (MD5) Previous issue date: 2007 / In this work we evaluate both exact and heuristic methods for the set partitioning problem (SPP). These heuristics are based on greedy algorithms, tabu search and subgradient optimization. Computational experiments performed on benchmark instances of the problem indicate that our heuristics are competitive with existing ones from the literature in obtaining both lower and upper bounds of good quality in reasonable execution time. We use a Branch and Bound algorithm that allows to prove optimality of solutions obtained by our heuristics for a large set of benchmark instances of the SPP. Thus, we show that our heuristics are efficient in obtaining feasible solutions of good quality for this problem. / Neste trabalho avaliamos métodos heurísticos e exatos para o Problema de Particionamento de Conjuntos (PPC). Realizamos testes computacionais com heurísticas lagrangeanas baseadas em algoritmos gulosos, busca tabu e método de otimização pelo subgradiente. Os resultados obtidos, comparados com os da literatura, comprovam a eficiência de nossas heurísticas na obtenção de limites inferiores e superiores de boa qualidade, em tempo computacional razoável, para instâncias da literatura. Utilizamos um esquema de Branch and Bound para tentar resolver instâncias do PPC à otimalidade e para comprovar a qualidade dos resultados alcançados por nossas heurísticas.

Cette thèse s'intéresse au problème de conception optimale des routes de départ et d'arrivée dans une zone terminale autour d'un aéroport. Cette conception prend en compte la configuration et l'environnement autour des aéroports, et les différentes contraintes sous-jacentes, notamment l'évitement des obstacles et la séparation des routes. Nous proposons une formulation mathématique conduisant à un problème d'optimisation combinatoire, ainsi que des méthodes de résolution ad hoc efficaces pour le problème. Pour la résolution du problème, nous procédons en deux étapes. Nous considérons d'abord la conception d'une route de longueur minimale évitant les obstacles, en utilisant la méthode de Branch and Bound (B&B). Ensuite, nous nous intéressons à la conception de plusieurs routes en assurant en plus la séparation des routes. Deux approches différentes sont appliquées : une méthode basée sur la méthode B&B pour construire les routes séquentiellement suivant un ordre fixé à l'avance, et une méthode de recuit simulé pour construire les routes simultanément. Les résultats sur un ensemble de problèmes tests (artificiels et réels) montrent l'efficacité de notre approche. / This thesis proposes a methodology for the optimization of departure and arrival routes in the Terminal Maneuvering Area (TMA). The design of these routes takes into account the configuration and environment around airports, and the related constraints, in particular the avoidance of obstacles and the separation between routes. We propose a mathematical formulation leading to a combinatorial optimization problem, as well as efficient ad hoc resolution methods for the problem. The problem is solved in two steps. First, we design an individual route avoiding obstacles with respect to minimum route length by using a Branch and Bound (B&B) method. Afterwards, the design of multiple routes is solved by two different approaches: a B&B-based approach (where routes are generated sequentially in a given order) and a Simulated Annealing approach (where routes are generated simultaneously). The simulation results of a set of (artificial and real) test problems show the efficiency of our approach.

Made available in DSpace on 2016-12-23T13:51:53Z (GMT). No. of bitstreams: 1 Cristiane Coutinho Meneguzzi.pdf: 2106158 bytes, checksum: 65c537220893be6e9c9d64b3001fef07 (MD5) Previous issue date: 2011-10-04 / Na área florestal, ainda é dada maior ênfase ao desenvolvimento de estudos envolvendo as etapas de colheita e transporte florestal, por serem diretamente responsáveis pelo custo final da madeira. Entretanto, diversas outras etapas possuem grande potencial para estudos, como é o caso do inventário florestal. Informações fornecidas pelo inventário florestal são importantes no planejamento de todo empreendimento florestal, pois subsidiam qualquer tomada de decisão envolvendo recursos florestais. Nesta pesquisa, utilizou-se o modelo de roteamento de veículos (PRV) no planejamento dessa atividade. O PRV e suas variantes vêm sendo amplamente estudados nos últimos anos, principalmente pela sua aplicabilidade e eficiência em gerar soluções apresentando redução de custo e/ou distâncias. O objetivo geral foi otimizar o planejamento da atividade de inventário florestal a partir de um modelo PRV e avaliar a importância do uso desta técnica no rendimento das atividades. Dentre os fatores que influenciam neste rendimento, a dispersão espacial, característica básica dos povoamentos florestais, é um fator controlável a partir do uso de técnicas que possibilitem associá-lo ao planejamento. Estudos mostram que essa associação traz resultados significativos / On Forest field, studies in development of forest harvesting and transport still being the most emphasized subject, for being directly responsible for the final cost of wood. However, other different phases are a big potential for studies, as Forest Inventory. Information provided by the Forest Inventory are important for all planning of Forest Enterprise, as it bases any decision making involving forest resources. On this present research, was based on vehicle routing problem for planning this task. The vehicle routing problem and its variants has being largely studied on the last years, mainly for its applicability and efficiency for given solutions resulting in cost and distance reduction. The general objective of the present study is optimize the Inventory Forest planning from a vehicle routing problem and evaluate the importance of this technique on its productivity. Among the factors that influence this productivity, the spatial dispersion , basic feature of forest stands, it is one controllable factor from the use of technique that makes possible matches with planning. Studies shows that this match brings out significant results

Made available in DSpace on 2016-06-02T19:50:17Z (GMT). No. of bitstreams: 1 TeseLKO.pdf: 834201 bytes, checksum: 994d7b70c6b1001f9dec962fafc8b72e (MD5) Previous issue date: 2004-12-13 / Universidade Federal de Sao Carlos / The purpose of this work is to develop exact methods, based on Lagrangean and Surrogate relaxation, with good performance to solve the manufacturer s pallet loading problem. This problem consists of orthogonally arranging the maximum number of rectangles of sizes (l,w) and (w,l) into a larger rectangle (L,W) without overlapping. Such methods involve a tree search procedure of branch and bound type and they use, in each node of the branch and bound tree, bounds derived from Lagrangean and/or Surrogate relaxations of a 0-1 linear programming formulation. Subgradient optimization algorithms are used to optimize such bounds. Problem reduction tests and Lagrangean and Surrogate heuristics are also applied in the subgradient optimization to obtain good feasible solution. Computational experiments were performed with instances from the literature and also real instances obtained from a carrier. The results show that the methods are able to solve these instances, on average, more quickly than other exact methods, including the software GAMS/CPLEX. / O objetivo deste trabalho é desenvolver métodos exatos, baseados em relaxação Lagrangiana e Surrogate, com bom desempenho para resolver o problema de carregamento de paletes do produtor. Tal problema consiste em arranjar ortogonalmente e sem sobreposição o máximo número de retângulos de dimensões ( , ) l w ou ( , ) w l sobre um retângulo maior ( , ) L W . Tais métodos exatos são procedimentos de busca em árvore do tipo branch and bound que, em cada nó, utilizam limitantes derivados de relaxações Lagrangiana e/ou Surrogate de uma formulação de programação linear 0 1 − . Algoritmos de otimização do subgradiente são usados para otimizar estes limitantes. São aplicados ainda testes de redução do problema e heurísticas Lagrangiana e Surrogate na otimização do subgradiente para obter boas soluções factíveis. Testes computacionais foram realizados utilizando exemplos da literatura e exemplos reais, obtidos de uma transportadora. Os resultados mostram que os métodos são capazes de resolvê-los, em média, mais rapidamente do que outros métodos exatos, incluindo o software GAMS/CPLEX.

Made available in DSpace on 2015-05-08T14:53:38Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 7900350 bytes, checksum: fbca2db827307d8c3ed2a1c15067d0da (MD5) Previous issue date: 2014-02-13 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / This research deals with the Close-Enough Traveling Salesman Problem, a variant of the Traveling Salesman Problem wich has several applicatios in logistics. In the Close-Enough Traveling Salesman Problem, rather than visiting the vertex (customer) itself, the salesman must visit a specific region containing such vertex. To solve this problem, we propose a simple yet effective exact algorithm, based on Branch-and-Bound and Second Order Cone Programming. The proposed algorithm was tested in 824 instances suggested in the literature. Optimal solutions are obtained for open problems with up to a thousand vertices. We consider both instances in the two- and three-dimensional space. / Esta pesquisa trata do Problema do Caixeiro Viajante Suficientemente Próximo, uma variante do Problema do Caixeiro Viajante que possui diversas aplicações em logística. No Problema do Caixeiro Viajante Suficientemente Próximo, ao invés de visitar o próprio vértice (cliente), o caixeiro deve visitar uma região especifica contendo este vértice. Para resolver este problema, é proposto um algoritmo exato, simples e efetivo, baseado em branch-and-bound e Programação Cônica de Segunda Ordem. O algoritmo proposto foi testado em 824 instâncias sugeridas na literatura. Soluções ótimas foram obtidas para instâncias com até mil vértices. Foram consideradas instâncias nos espaços bi e tridimensional.

En bioinformatique structurale, une partie des méthodes computationnelles qui calculent les structures de protéines à l'aide de données expérimentales, effectuent une optimisation de la position des atomes sous les contraintes expérimentales mesurées sur le système étudié, ainsi que sous des contraintes provenant de la connaissance générique de la stéréochimie organique. Ces méthodes d'optimisation présentent l'inconvénient de ne pas garantir la détermination de la meilleure solution. De plus, la validation de l'optimisation se fait en comparant les résultats obtenus pour des calculs répétés, et le résultat d'un calcul est accepté dans la mesure où le même résultat est obtenu plusieurs fois. Par cette approche, on rend plus difficile la détection de conformations alternatives de protéines, qui sont pourtant le sujet d'un vif intérêt dans la littérature. En effet, le développement de la sensibilité des techniques de résonance magnétique nucléaire (RMN) a permis de mettre en évidence plusieurs cas d'échange conformationnel reliés à la fonction des protéines. Dans ce projet de thèse, nous avons étudié une nouvelle approche pour le calcul de structures des protéines et l'exploration de leurs espaces conformationnels, basée sur la résolution du problème de Géométrie de Distance associé aux contraintes de distances dans une protéine par l'algorithme "interval Branch and Prune". Le logiciel implémentant cette méthode est appelée iBPprot, il incarne l'une des premières tentatives d'échantillonnage exhaustive des espaces conformationnels des protéines. Dans un premier temps, on s'est intéressé à l'application de la méthode en utilisant exclusivement des constraintes de distances exactes. Les résultats ont démontré que iBPprot était capable de reconstruire des structures références en s'appuyant seulement sur quelques contraintes à courte portée. De plus, la reconstruction a été d'une précision telle que la conformation générée présentait un RMSD de 1 Angstrom maximum avec la structure référence. L'exploration exhaustive de l'espace conformationnel a été possible pour une bonne partie des protéines cibles. Les temps de calcul pour l'exploration des espaces conformationnels ont été très variables allant de quelques secondes pour quelques protéines jusqu'à des semaines pour d'autres. L'évaluation de la qualité des structures obtenues a démontré qu'au moins 68% des valeurs de phi et psi sont localisées dans la zone 'core' du diagramme de Ramachandran. Cependant, des clash stériques ont été détectées dans plusieurs conformations mettant en jeu jusqu'à 7% d'atomes dans quelques unes de ces conformations. Dans un deuxième temps, on s'est intéressé à l'application de la méthode en incluant des intervalles de distances comme contraintes dans les calculs. Dans ce cas de figure, la méthode a réussi a reconstruire des structures références avec un RMSD inférieur à 5 Angstrom pour plus de la moitié des protéines cibles. En contre partie, le parcours complet de l'espace conformationnel n'a été possible que pour la plus petite protéine de l'ensemble des protéines étudiées. Pour la moitié des autres protéines, plus de 70% des atomes ont vu leurs positions échantillonnées. La qualité des structures obtenues a regressé en comparaison avec les simulations faites avec des distances exactes. En effet, seulement 53% des valeurs de phi et psi étaient localisées dans la zone 'core' du diagramme de Ramachandran, et le pourcentage d'atomes impliqués dans un clash stérique s'élevait jusqu'à 22% pour quelques protéines. Concernant le temps de calcul, le taux de génération de conformations a été déterminé pour chaque protéine cible, et il s'est avéré que globalement sa valeur etait compétitive par rapport aux valeurs des taux observables dans la littérature... / Structural biology has allowed us expand our knowledge of living organisms. It is defined as the investigation of the structure and function of biological systems at the molecular level. Studying a biomolecule's structure offers insight into its geometry, as angles and distances between the biomolecule's atoms are measured in order to determine the biomolecular structure. The values of these geometrical parameters may be obtained from biophysical techniques, such as X-ray crystallography or nuclear magnetic resonance (NMR) spectroscopy. One of the most used methods to calculate protein structures from geometric restraints is simulated annealing. This method does not guarantee an exhaustive sampling of protein conformational space, which is a shortcoming as one protein may adopt multiple functional conformations, and it is important to determine them exhaustively. In this PhD project, the efficiency of a new method - derived from operations research and computational geometry - is studied in order to answer this question: How does this method explore the conformational spaces of small proteins? This method - implemented within the iBPprot software framework - treats protein structure determination as a distance geometry problem, which the interval branch-and-prune algorithm tries to solve by the full exploration of its solutions space. The results obtained by iBPprot on a set of test proteins, with sizes ranging from 24 to 120 residues and with known structures, are analyzed here. Using short-range exact distance restraints, it was possible to rebuild the structure of all protein targets, and for many of them it was possible to exhaustively explore their conformational spaces. In practice, it is not always possible to obtain exact distance restraints from experiments. Therefore, this method was then tested with interval data restraints. In these cases, iBPprot permitted the sampling of the positions of more than 70% of the atoms constituting the protein backbone for most of the targets. Furthermore, conformations whose r.m.s. deviations closer than 6 Angstrom to the target ones were obtained during the conformational space exploration. The quality of the generated structures was satisfactory with respect to Ramachandran plots, but needs improvement because of the presence of steric clashes in some conformers. The runtime for most performed calculations was competitive with existing structure determination method...