Sistemas Elétricos de Potência (SEPs) muitas vezes não são capazes de retomarem a uma nova condição de equilíbrio após grandes perdas de geração ou mesmo pela retirada de importantes linhas de transmissão. O déficit de potência causado por alguns desses distúrbios pode acarretar no declínio gradual da freqüência do sistema. Caso a reserva girante ou o próprio sistema de transmissão não sejam capazes de recompor o SEP, medidas corretivas devem ser tomadas para evitar o colapso do mesmo. Nesta condição de emergência, um montante de carga deve ser desconectado de forma a restaurar uma nova condição de equilíbrio através de um esquema emergencial conhecido como plano de corte de carga por subfrequência. Muitos trabalhos vem sendo desenvolvidos ao longo dos anos, nos quais são propostas diferentes técnicas para a determinação de planos de corte de carga. Na maioria delas utiliza-se uma modelagem equivalente e linearizada do sistema. Tais simplificações trazem grandes facilidades para a representação do sistema. Porém, para que a integridade do mesmo seja garantida, muitas vezes os planos de corte de carga envolvem montantes de carga maiores que o necessário. A metodologia apresentada neste trabalho utiliza uma representação não linear para o SEP, o que permite um estudo do comportamento dinâmico de suas unidades geradoras para que os limites de frequência sejam determinados. Assim, os planos podem ser determinados com eficiência, reduzindo o número de consumidores desprovidos de energia elétrica durante o processo de alívio de carga. Entretanto, a escolha de um modelo mais completo para a representação do sistema pode acarretar num grande esforço na análise e determinação dos esquemas de alívio de carga, quando aplicados em sistemas de grande porte. Sendo assim, é proposta neste trabalho uma metodologia capaz de auxiliar tais estudos, o que diminui os esforços tanto da parte computacional quanto da parte empregada pelo projetista. Uma abordagem energética é aplicada ao problema e, dessa forma, dada uma perda de geração é possível determinar o valor mínimo de frequência atingido pelo sistema sem que haja a necessidade de se conhecer a trajetória do ponto de operação do sistema. Portanto, é proposta uma metodologia baseada em funções energia para a determinação de planos de corte de carga e, posteriormente, são realizadas simulações em uma representação simplificada de um sistema elétrico de potência para a validação da mesma. Também é mostrado o comportamento da frequência do sistema durante uma condição de subfrequência sobre duas perspectivas. Uma delas utiliza-se de uma modelagem não linear para a representação do sistema e a outra utiliza-se do modelo linearizado para a representação deste mesmo sistema. Este trabalho tem por finalidade o estudo e modelagem matemática do problema emergencial de alívio de carga de uma forma introdutória, para que posteriormente, possa ser desenvolvida de uma ferramenta capaz de auxiliar tais estudos. O método proposto demonstrou-se muito promissor, apesar das simplificações utilizadas para a construção do modelo. / Electric power systems (EPS) are not always capable of achieving a new stable equilibrium point after a severe generation loss or even after the loss of important transmission lines. The lack of active power generation caused by some of these disturbances can lead to a gradual decay of the system frequency. If the spinning reserve or even the bulk transmission system are not capable of restoring the system, then, corrective actions should be taken to avoid a system collapse. Under this emergency condition, a portion of the load should be disconnected, as a way to restore a new stable equilibrium condition, through an emergency scheme known as under frequency load shedding (UFLS). Several works have been developed in this field throughout the years, in which different techniques are proposed to determine the load shedding schemes. The majority of these works use an equivalent linearized model of the system, which facilitates the system representation. However, in order to keep the integrity of the system, it is common to overestimate the shedding of loads. The validation of load shedding schemes that use a linear methodology is generally performed through simulations based on nonlinear models of the whole system. The methodology presented in this work uses a nonlinear representation for the EPS for developing an UFLS scheme, which permits a study of the dynamic behavior of its generators in order to find the frequency limits. ln this way, the schemes can be efficiently determined, aiming a reduction on the number of consumers affected by the load shedding scheme, and avoiding additional simulations to validate the designed scheme. An energetic approach is applied to the problem and, in this way, given a generation loss it is possible to determine the minimum frequency value achieved by the system without the need for the knowledge of the trajectory of the system\'s operating point. Voltage regulators and speed governors are neglected, and the loads and network equipments are represented through a constant impedance model, whereas the generators are modeled through its classical model.

Sistemas Elétricos de Potência (SEPs) muitas vezes não são capazes de retomarem a uma nova condição de equilíbrio após grandes perdas de geração ou mesmo pela retirada de importantes linhas de transmissão. O déficit de potência causado por alguns desses distúrbios pode acarretar no declínio gradual da freqüência do sistema. Caso a reserva girante ou o próprio sistema de transmissão não sejam capazes de recompor o SEP, medidas corretivas devem ser tomadas para evitar o colapso do mesmo. Nesta condição de emergência, um montante de carga deve ser desconectado de forma a restaurar uma nova condição de equilíbrio através de um esquema emergencial conhecido como plano de corte de carga por subfrequência. Muitos trabalhos vem sendo desenvolvidos ao longo dos anos, nos quais são propostas diferentes técnicas para a determinação de planos de corte de carga. Na maioria delas utiliza-se uma modelagem equivalente e linearizada do sistema. Tais simplificações trazem grandes facilidades para a representação do sistema. Porém, para que a integridade do mesmo seja garantida, muitas vezes os planos de corte de carga envolvem montantes de carga maiores que o necessário. A metodologia apresentada neste trabalho utiliza uma representação não linear para o SEP, o que permite um estudo do comportamento dinâmico de suas unidades geradoras para que os limites de frequência sejam determinados. Assim, os planos podem ser determinados com eficiência, reduzindo o número de consumidores desprovidos de energia elétrica durante o processo de alívio de carga. Entretanto, a escolha de um modelo mais completo para a representação do sistema pode acarretar num grande esforço na análise e determinação dos esquemas de alívio de carga, quando aplicados em sistemas de grande porte. Sendo assim, é proposta neste trabalho uma metodologia capaz de auxiliar tais estudos, o que diminui os esforços tanto da parte computacional quanto da parte empregada pelo projetista. Uma abordagem energética é aplicada ao problema e, dessa forma, dada uma perda de geração é possível determinar o valor mínimo de frequência atingido pelo sistema sem que haja a necessidade de se conhecer a trajetória do ponto de operação do sistema. Portanto, é proposta uma metodologia baseada em funções energia para a determinação de planos de corte de carga e, posteriormente, são realizadas simulações em uma representação simplificada de um sistema elétrico de potência para a validação da mesma. Também é mostrado o comportamento da frequência do sistema durante uma condição de subfrequência sobre duas perspectivas. Uma delas utiliza-se de uma modelagem não linear para a representação do sistema e a outra utiliza-se do modelo linearizado para a representação deste mesmo sistema. Este trabalho tem por finalidade o estudo e modelagem matemática do problema emergencial de alívio de carga de uma forma introdutória, para que posteriormente, possa ser desenvolvida de uma ferramenta capaz de auxiliar tais estudos. O método proposto demonstrou-se muito promissor, apesar das simplificações utilizadas para a construção do modelo. / Electric power systems (EPS) are not always capable of achieving a new stable equilibrium point after a severe generation loss or even after the loss of important transmission lines. The lack of active power generation caused by some of these disturbances can lead to a gradual decay of the system frequency. If the spinning reserve or even the bulk transmission system are not capable of restoring the system, then, corrective actions should be taken to avoid a system collapse. Under this emergency condition, a portion of the load should be disconnected, as a way to restore a new stable equilibrium condition, through an emergency scheme known as under frequency load shedding (UFLS). Several works have been developed in this field throughout the years, in which different techniques are proposed to determine the load shedding schemes. The majority of these works use an equivalent linearized model of the system, which facilitates the system representation. However, in order to keep the integrity of the system, it is common to overestimate the shedding of loads. The validation of load shedding schemes that use a linear methodology is generally performed through simulations based on nonlinear models of the whole system. The methodology presented in this work uses a nonlinear representation for the EPS for developing an UFLS scheme, which permits a study of the dynamic behavior of its generators in order to find the frequency limits. ln this way, the schemes can be efficiently determined, aiming a reduction on the number of consumers affected by the load shedding scheme, and avoiding additional simulations to validate the designed scheme. An energetic approach is applied to the problem and, in this way, given a generation loss it is possible to determine the minimum frequency value achieved by the system without the need for the knowledge of the trajectory of the system\'s operating point. Voltage regulators and speed governors are neglected, and the loads and network equipments are represented through a constant impedance model, whereas the generators are modeled through its classical model.

[pt] Este trabalho consiste da aplicação de métodos de planos de corte (euclideano acelerado e cortes disjuntivos) na solução de problemas de programação inteira pura do tipo 0- 1 e suas especializações para o problemas de particionamento, quando combinados com técnicas de penalidades para fixação de variáveis. Desenvolve-se um estudo de técnicas de penalidades, que permitem fixar variáveis a valores inteiros a partir da solução ótima da relaxação linear do problema inteiro. As variáveis fixadas são eliminadas do problema e este é reescrito, tendo suas dimensões originais reduzidas. Sugerem-se melhorias no cálculo destas penalidades, levando-se em conta a estrutura particular do problema de particionamento. Finalmente, propõe-se um novo enfoque para a solução de problemas de particionamento: um algoritmo de planos de corte que utiliza técnicas de penalidades, com a finalidade de acelerar a convergência dos métodos puros de planos de corte e de reduzir os problemas por estes apresentados. Resultados computacionais são apresentados, comparando-se o desempenho (i) do algoritmo euclideano acelerado, (ii) do algoritmo de cortes disjuntivos e (iii) do algoritmo de cortes disjuntivos utilizando-se técnicas de penalidades. Para este último algoritmo, são comparados os resultados obtidos utilizando-se técnicas de penalidades genéricas para problemas inteiros do tipo 0-1 e as melhorias destas penalidades, especificas para problemas de particionamento. Considerando-se o problemas de particionamento e as melhorias propostas no cálculo de penalidades, mostra-se que é, freqüentemente, possível fixar um maior número de variáveis ou até mesmo resolver-se diretamente o problema 0-1 original. Em alguns casos, ao aplicar-se o algoritmo de planos de corte com técnicas de penalidades não só pode- se acelerar a convergência, como também superar os problemas de degenerescência dual e erros por arredondamento apresentados pelos algoritmos puros de plano de corte. / [en] This work consists on the application of cutting plane techniques (accelerated euclidean algorithm and disjunctive cuts) for solving pure 0-1 integer problems and their specializations for the set partitioning problem, when combined to penalty techniques for fixing variables. A study on penalty techniques, which allows the fixation of variables to integer values, is also developed. These penalties are directly derived from the optimal tableau nof the linear relaxation of the integer problem. The variables fixed due to penalties are eliminated and the problem is reformulated, having its initial dimensions reduced. Some improvements on the evaluation of penalties are suggested, taking into account the special structure of the set partitioning problem. Finally, a new approach to the solution of set partitioning problems is proposed: a cutting plane algorithm which uses penalty techniques, in order to accelerate the convergence of pure cutting plane methods and overcome the problems arising from their use. Computational results are shown, allowing to compare the performance of (i) the accelerated euclidean algorithm, (ii) the disjunctive cut algorithm and (iii) the last one combined with penalty techniques. For the latter, the results obained by the use of generic penalties for 0-1 integer programs are compared with those obtained by the use of the improved penalties for ser partitioning problems. Taking into account set partitioninng problems and the improvements proposed for the evaluation of penalties, it is shown that very often it is possible to fix more variables to integer values and even to solve directly the original 0-1 problem. For some cases, by applying the cutting plane algorithm together with penalties, it is possible to accelerate the convergence and overcome dual degeneracy and round-off errors arising from the use of pure cutting plane algorithms.

CAMPOS, Victor Almeida. Um estudo do politopo e dos limites inferiores gerados pela formulação de coloração dos representantes. 2005. 108 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2005. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-12T18:37:10Z No. of bitstreams: 1 2005_dis_vacampos.pdf: 624425 bytes, checksum: 13eb092def3e5c973c883bf32b893ba8 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-22T12:41:39Z (GMT) No. of bitstreams: 1 2005_dis_vacampos.pdf: 624425 bytes, checksum: 13eb092def3e5c973c883bf32b893ba8 (MD5) / Made available in DSpace on 2016-07-22T12:41:39Z (GMT). No. of bitstreams: 1 2005_dis_vacampos.pdf: 624425 bytes, checksum: 13eb092def3e5c973c883bf32b893ba8 (MD5) Previous issue date: 2005 / The vertex coloring problem is one of the most studied problems in graph theory for its relevance in practical and theoretical fields. From a theoretical point of view, it is a NP-Hard problem. Moreover, it is classified among the most difficult problems of NP- Hard in the sense that finding an approximation to the chromatic number is also NP-Hard. The importance of the coloring problem motivates searching for methods to find lower bounds close to the chromatic number. Historically, the first lower bounds used were obtained from the size of maximal cliques. More recently, relaxed integer programming formulations gained more attention. A formulation which found good lower bounds was the coloring problem through stable sets whose relaxed lower bound equals the fractional chromatic number. In this work, we make a comparison between the known integer programming formulations to motivate our choice for the Representatives formulation. We revise this formulation to remove symmetry and present a partial study of the polytope associated with the convex hull of its integer solutions. We discuss how to se the Representatives formulation to get lower bounds for the fractional chromatic number and we show how to get such lower bounds that differ at most by one unit to its exact value. / O problema de coloração de vértices é considerado um dos modelos mais estudados em teoria dos grafos pela sua relevância em campos práticos e teóricos. Do ponto de vista teórico, o problema de coloração é NP - Difícil. Além disto, foi classificado entre os problemas mais difíceis de NP, no sentido de que achar uma aproximação para o número cromático também é NP - Difícil. A importância do problema de coloração tem incentivado a investigar métodos para encontrar limitantes inferiores próximos do número cromático. Historicamente, os primeiros limitantes inferiores utilizados para resolvê-lo lidavam com cliques maximais. Mais recentemente, popularizou-se a utilização de relaxações lineares de formulações de programação inteira. Uma formulação que mostrou bons limitantes inferiores foi a formulação por conjuntos independentes, cujo valor de relaxação equivale ao número cromático fracionário. No presente trabalho, fazemos uma comparação entre as formulações de programação inteira conhecidas para indicar a escolha pela formulação dos representantes. Revisamos a formulação para remover simetrias existentes e apresentamos um estudo parcial do politopo associado ao fecho convexo de suas soluções inteiras. Discutimos como é possível utilizar a formulação dos representantes para gerar limites inferiores para o número cromático fracionário. Realizamos a implementação de um método de planos de corte para aproximar o número cromático fracionário e mostramos que podemos gerar limitantes inferiores que normalmente não diferem em mais de uma unidade.

Conselho Nacional de Desenvolvimento CientÃfico e TecnolÃgico / O problema de coloraÃÃo de vÃrtices à considerado um dos modelos mais estudados em teoria dos grafos pela sua relevÃncia em campos prÃticos e teÃricos. Do ponto de vista teÃrico, o problema de coloraÃÃo à NP - DifÃcil. AlÃm disto, foi classificado entre os problemas mais difÃceis de NP, no sentido de que achar uma aproximaÃÃo para o nÃmero cromÃtico tambÃm à NP - DifÃcil. A importÃncia do problema de coloraÃÃo tem incentivado a investigar mÃtodos para encontrar limitantes inferiores prÃximos do nÃmero cromÃtico. Historicamente, os primeiros limitantes inferiores utilizados para resolvÃ-lo lidavam com cliques maximais. Mais recentemente, popularizou-se a utilizaÃÃo de relaxaÃÃes lineares de formulaÃÃes de programaÃÃo inteira. Uma formulaÃÃo que mostrou bons limitantes inferiores foi a formulaÃÃo por conjuntos independentes, cujo valor de relaxaÃÃo equivale ao nÃmero cromÃtico fracionÃrio. No presente trabalho, fazemos uma comparaÃÃo entre as formulaÃÃes de programaÃÃo inteira conhecidas para indicar a escolha pela formulaÃÃo dos representantes. Revisamos a formulaÃÃo para remover simetrias existentes e apresentamos um estudo parcial do politopo associado ao fecho convexo de suas soluÃÃes inteiras. Discutimos como à possÃvel utilizar a formulaÃÃo dos representantes para gerar limites inferiores para o nÃmero cromÃtico fracionÃrio. Realizamos a implementaÃÃo de um mÃtodo de planos de corte para aproximar o nÃmero cromÃtico fracionÃrio e mostramos que podemos gerar limitantes inferiores que normalmente nÃo diferem em mais de uma unidade. / The vertex coloring problem is one of the most studied problems in graph theory for its relevance in practical and theoretical fields. From a theoretical point of view, it is a NP-Hard problem. Moreover, it is classified among the most difficult problems of NP- Hard in the sense that finding an approximation to the chromatic number is also NP-Hard. The importance of the coloring problem motivates searching for methods to find lower bounds close to the chromatic number. Historically, the first lower bounds used were obtained from the size of maximal cliques. More recently, relaxed integer programming formulations gained more attention. A formulation which found good lower bounds was the coloring problem through stable sets whose relaxed lower bound equals the fractional chromatic number. In this work, we make a comparison between the known integer programming formulations to motivate our choice for the Representatives formulation. We revise this formulation to remove symmetry and present a partial study of the polytope associated with the convex hull of its integer solutions. We discuss how to se the Representatives formulation to get lower bounds for the fractional chromatic number and we show how to get such lower bounds that differ at most by one unit to its exact value.

This work consists in proposing a methodology for the conversion of conventional sectioning machines in CNC equipments. The study is directed to the furniture industry and considers the possibility to outfit this kind of equipment with two programmable motion axes, through the utilization of devices as linear guides activated by engines with positioning accuracy. The system specifies one of the axes for motion and positioning of the plate to be counted, according to the dimensions of the project and other axis for the displacement of the limit sensor of the cutting tool. The technique consists in generating automatically the CNC programs for the adapted machine with data coming from systems of cutting plans generation. This work shows how to implement this technique through CAD application and considers two possibilities of obtaining the Cutting Plan data. On the first case, the sequence of cutting, defined with specialized computer programs, is converted in a drawing on CAD, that after is processed for the generation of the CNC program to the machine. The other alternative is to consider the possibility to implement techniques dedicated to the definition of the cutting arrangement, through CAD routines. In this case, a manual method was purposed with the goal to demonstrate the technique that assumes that the furniture project is virtually defined on CAD through 3D drawing resources. To demonstrate the validity of the methodology were elaborated two virtual projects a kitchen and a bedroom for which were generating the cutting plans with different techniques and their CNC programs. This study shows that the number of patterns produced for cutting planes through the proposed empirical method for a software used is the same. However, note that there is a difference in the occupied area, comparing the use of sheet parts in the software and the empirical method, it would not be feasible due to the sum of surpluses generated a longer period of production. / Este trabalho consiste em propor uma metodologia para conversão de máquinas seccionadoras convencionais em equipamentos CNC. O estudo é direcionado à indústria moveleira e considera a possibilidade de equipar esse tipo de equipamento com dois eixos de movimentação programáveis, através da utilização de dispositivos como guias lineares acionadas por motores com precisão de posicionamento. O sistema especifica um dos eixos para movimentação e posicionamento da chapa a ser cortada, conforme dimensões de projeto e outro eixo para deslocamento do sensor de fim de curso da ferramenta de corte. A técnica consiste em gerar automaticamente os programas CNC para a máquina adaptada a partir de dados provenientes de sistemas de geração de planos de corte. O trabalho mostra como implementar essa técnica através de aplicativos CAD e considera duas possibilidades de obtenção dos dados do Plano de Corte. No primeiro caso, a sequência de corte, definida em programas computacionais especializados, é convertida em um desenho do CAD, que posteriormente é processado para a geração do programa CNC para a máquina. A outra alternativa é considerar a possibilidade de implementação de técnicas dedicadas à definição do arranjo do corte, através de rotinas do CAD. Nesse caso, um método empírico foi proposto com o objetivo de demonstrar a técnica, que parte do princípio de que o projeto do móvel esteja virtualmente definido no CAD através de recursos 3D de desenho. Para demonstrar a validade da metodologia, foram elaborados dois projetos virtuais uma cozinha e um quarto para os quais foram gerados os planos de corte por diferentes técnicas e os respectivos programas CNC. O estudo realizado mostra que a quantidade de arranjos gerados para planos de corte através do método empírico proposto em relação a um software utilizado é a mesma. Além disso, nota-se que existe uma diferença de área ocupada, comparando-se o aproveitamento das peças na chapa no software e no método empírico, o mesmo não seria viável devido ao somatório de sobras geradas num período maior de produção.

[pt] O problema de Roteamento de Veículos com restrição de capacidade (CVRP) é um dos problemas mais estudados em Otimização Combinatória. Sendo uma generalização imediata do conhecido problema do Caixeiro Viajante, o CVRP tem atraído a atenção dos pesquisadores mais proeminentes da área desde os anos 60. Um dos algoritmos mais importantes para a sua resolução foi proposto no início dos anos 80 quando um algoritmo utilizando uma relaxação Lagrangeana particularmente adequada provou ser bastante superior aos algoritmos contemporâneos. Este algoritmo sugeriu a utilização de técnicas de geração de colunas que, nos anos seguintes até o início dos anos 90, assumiram o rótulo de melhor algoritmo para o CVRP. Finalmente, em meados dos anos 90, algoritmos de planos de corte apresentaram resultados que convenceram a comunidade de que esta deveria ser a abordagem para resolver os problemas mais difíceis de CVRP. Esta dissertação apresenta uma revisão deste algoritmos anteriores e propõe um formulação que permite reunir o melhor deles. O algortimo resultante, que pode ser rotulado como de branch-and-cut-and-price, trabalha com um número exponencial de variáveis e restrições que definem um espaço relaxado de soluções que corresponde à interseção dos espaços de solução relaxados utilizados pelos algoritmos anteriores. Esta dissertação também descreve um implementação especial do algoritmo de programação dinâmica para resolução do problema de geração de colunas. Estratégias para fazer um branching robusto também são discutidas. Tudo isso permite construir um algoritmo que é capaz de ter uma boa performance quando aplicado a diferentes classes de instâncias. A experiência computacional mostrou que a abordagem proposta obtém limites inferiores consistentemente melhores que os dos algoritmos anteriores. Mais ainda, permite resolver em tempo hábil diferentes tipos de instâncias de até 135 vértices, incluindo 18 que foram resolvidas pela primeira vez. / [en] The Capacitated Vehicle Routing problem (CVRP) has been one of the most studied problems in the field of Combinatorial Optimization. A straight forward generalization of the popular Travelling Salesperson problem, the CVRP has drawn attention of the most prominent researchers since the early 60`s. One of the most important algorithms appeared in the early 80`s when a suitable Lagrangean relaxation algorithm has demonstrated to be far better than the contemporary ones. This algorithm suggested the use of column generation algorithms that succeeded to become the best ones in the late 80`s and early 90`s. Finally, in the mid 90`s, cutting plane methods presented results that convinced the community that this should be the approach for solving the hardest CVRP problems. This dissertation presents an overview of those early algorithms and proposes a formulation that allows uniting the best contributions of them. The resulting algorithm, labeled as a branch-and-cut-and-price algorithm, deals with exponentially many variables and constraints that define a relaxed solution space that is the intersection of the relaxed solution spaces considered in the previous algorithms. The dissertation also describes a specially devised dynamic programming algorithm to solve the column generation subproblem and discusses robust branching strategies that altogether allowed to build an algorithm that perfoms well on several different classes of instances. The computational experience has shown that the approach here proposed leads to lower bounds superior than the previous ones. Moreover, it allowed to consistently solve instances with up to 135 vertices, including 18 that were solved for the first time.

Submitted by Franciele Moreira (francielemoreyra@gmail.com) on 2017-10-20T16:09:47Z No. of bitstreams: 2 Dissertação - Lorrany Cristina da Silva - 2017.pdf: 8394886 bytes, checksum: 9cc1461b937a65a8c50964b3dea86623 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2017-10-23T10:05:52Z (GMT) No. of bitstreams: 2 Dissertação - Lorrany Cristina da Silva - 2017.pdf: 8394886 bytes, checksum: 9cc1461b937a65a8c50964b3dea86623 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2017-10-23T10:05:52Z (GMT). No. of bitstreams: 2 Dissertação - Lorrany Cristina da Silva - 2017.pdf: 8394886 bytes, checksum: 9cc1461b937a65a8c50964b3dea86623 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2017-06-28 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / Three different integer linear programming models for the Vehicle Routing Problem with Two-dimensional Loading Constraints are developed in this work. The version of the problem studied considers that the unloading of the rectangular items can respect or not the sequence of the clients visited on the route, that is, we solve the sequential and unrestricted versions of the problem. The first model deals with the problem completely, that is, with all constraints inserted at once. The second and third models are based, respectively, on a three- and two-index formulation. Separation routines are considered to detect violated inequalities related with packing on the second and third models, while the third model also considers cuts on connectivity and capacity. Computational experiments were carried out over instances of the literature with the quantity of customers ranging from 15 to 36 and items from 15 to 114, besides to consider the cases in which the cost of traversing an edge is integer and real. The models with cuts on demand were better in relation to the first model, besides being competitive when comparing with the results fromthe literature. The first model solved 4 of the 80 instances, the three-index model solved 7 and, the two-index model solved 53. On the sequential version, the adopted model solved 33 instances for the case with integer costs (and 37 for the case with real costs). In comparing with a recent heuristic from the literature, the best model was capable of tying in 48 instances in the unrestricted version and 24 in the sequential version. / Neste trabalho desenvolvem-se três modelos de programação linear inteira para o Problema de Roteamento de Veículos com Restrições de Empacotamento Bidimensional. A versão do problema estudado considera que o descarregamento dos itens retangulares pode respeitar (ou não) a sequência de clientes visitados na rota, ou seja, resolve-se as versões sequencial e irrestrita do problema. O primeiro modelo trata do problema de forma completa, isto é, com todas as restrições inseridas de uma só vez. O segundo e o terceiro modelo são baseados, respectivamente, em uma formulação de três e dois índices. Rotinas de separação são consideradas para detectar desigualdades violadas de empacotamento no segundo e no terceiro modelo, enquanto o último modelo considera também cortes de conectividade e capacidade. Experimentos computacionais foram realizados em instâncias da literatura com número de clientes variando de 15 a 36 e itens de 15 até 114, além de considerar os casos em que o custo da aresta é inteiro ou real. Os modelos com cortes sob demanda foram melhores em relação ao primeiro modelo, além de serem competitivos quando comparado com a literatura. O modelo completo encontrou a solução ótima em 4 das 80 instâncias, o modelo de três índices 7 e o modelo de dois índices 53. Na versão sequencial, o modelo adotado resolveu 33 instâncias para o custo inteiro (e 37 para o custo real). Na comparação com uma heurística recente da literatura, o melhor modelo conseguiu empatar em 48 instâncias na versão irrestrita e em 24 na versão sequencial.