41 |
Modelagem e meta-heurísticas para o problema de roteamento de veículos com janelas de tempo, múltiplos entregadores e múltiplas viagens em uma empresa de distribuição de bebidasSouza Neto, José Ferreira de 21 March 2016 (has links)
Submitted by Izabel Franco (izabel-franco@ufscar.br) on 2016-10-06T17:59:08Z
No. of bitstreams: 1
DissJFSN.pdf: 5729965 bytes, checksum: 946688f479f7780db197fa49b4b4c853 (MD5) / Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2016-10-20T13:51:08Z (GMT) No. of bitstreams: 1
DissJFSN.pdf: 5729965 bytes, checksum: 946688f479f7780db197fa49b4b4c853 (MD5) / Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2016-10-20T13:51:14Z (GMT) No. of bitstreams: 1
DissJFSN.pdf: 5729965 bytes, checksum: 946688f479f7780db197fa49b4b4c853 (MD5) / Made available in DSpace on 2016-10-20T13:51:20Z (GMT). No. of bitstreams: 1
DissJFSN.pdf: 5729965 bytes, checksum: 946688f479f7780db197fa49b4b4c853 (MD5)
Previous issue date: 2016-03-21 / Não recebi financiamento / Vehicle routing problems occur in many practical situations where the pickup and/or delivery
of goods is required. In this context, the present research aims to contribute to the study of
logistic operations that arise in companies that deliver products on a regular basis to
customers in densely populated urban areas. The problem consists in designing minimal cost
daily routes serving the maximal number of customers. To this end, the crew of each vehicle
comprise multiple deliverymen as means to reduce service times. Based on a case study in a
drinks producer and distributor in the state of São Paulo, it is proposed a mixed integer linear
programming model that comprise costs with own and chartered vehicles and the number of
deliverymen, and various operational constraints such as time windows in customers, multiple
daily trips, time limitations for the circulation of some vehicle types in specific areas,
compatibility between vehicles and customers, maximum load in each vehicle, maximum
route time and minimum load for the realization of a second trip. Results obtained by solving
the model with real instances through exact (branch&cut), heuristic (constructive, local
search, GRASP and Simulated Annealing) and hybrid (GRASP and branch&cut) approaches
demonstrate the good quality of the generated solutions, and indicate the potential of
application of some of these methods in practice. / Problemas de roteamento de veículos ocorrem em diversas situações práticas onde se faz
necessária a distribuição e/ou coleta de produtos. Nesse contexto, a presente pesquisa visa o
estudo das operações logísticas presentes em empresas que entregam produtos em base
regular a clientes localizados em áreas urbanas de alta densidade demográfica. O problema
consiste na obtenção de rotas de mínimo custo visando o atendimento do maior número de
clientes da carteira diária. Para tal, a tripulação de cada veículo pode contemplar múltiplos
entregadores para redução dos tempos de serviço. Com base em um estudo de caso em uma
distribuidora de bebidas do interior do Estado de São Paulo, é proposto um modelo de
programação linear inteira mista que considera custos com frota própria e fretada e com o
número de entregadores, e diversas restrições operacionais, tais como janelas de tempo em
clientes, múltiplas viagens diárias, limitações de horários de circulação de tipos de veículos,
compatibilidade entre veículos e clientes, capacidade máxima de carga a ser transportada em
cada veículo, tempo máximo de rota e carga mínima para realização da segunda viagem.
Resultados da resolução do modelo para instâncias reais por meio de abordagens exatas
(branch&cut), heurísticas (construtiva, busca local, GRASP e Simulated Annealing) e híbrida
(GRASP e branch&cut), demonstram a boa qualidade das soluções geradas, e evidenciam o
potencial de uso dessas metodologias na prática.
|
42 |
Um modelo de otimização para as operações de produção de vapor em caldeiras industriais: um estudo de caso na indústria de alimentosRocco, Cleber Damião 11 February 2011 (has links)
Made available in DSpace on 2016-06-02T19:51:48Z (GMT). No. of bitstreams: 1
3491.pdf: 1251165 bytes, checksum: 650dd47d0fec8bae05ba378f445f91dc (MD5)
Previous issue date: 2011-02-11 / Universidade Federal de Sao Carlos / The aim of this work was to develop and apply a mathematical optimization model to support some key decisions in the steam production operation system with multiple industrial boilers. In the food industry, key decisions into this system are, normally, taken based on people experience, not through decision support tools based on operations research. The proposed model approaches the fuel replenishment decisions, fuel transportation and fuel inventory management. The model also determines the start-up and shutdown moments for each boiler, as well as, which of them will produce steam. An algebraic modeling language was used to implement computationally the model, which was solved by an optimization software. The adjustments and model validation were performed through a case study carried out in a large scale food industry localized in Goiania (GO). In computational experiments conducted with company s data, the results obtained by the model showed better economic performance than those from the company. In face of the good outcomes obtained by applying the model and the lack of protocols or decision tools for the studied system, this model presents itself as a feasible alternative to be considered to support some key-decisions in the steam production system with industrial boilers. / O objetivo deste trabalho foi desenvolver e aplicar um modelo matemático de otimização para apoiar algumas das principais decisões na operação de produção de vapor em múltiplas caldeiras industriais. Em indústrias de alimentos, essas decisões, em geral, são tomadas com base na experiência dos envolvidos e não com ferramentas de auxílio à tomada de decisão apoiadas pela pesquisa operacional. O modelo proposto contempla as decisões de aquisições de combustíveis dos fornecedores, o transporte para fábrica e o gerenciamento dos estoques dos combustíveis adquiridos no sistema. O modelo também determina os momentos de acionamento e desligamento das caldeiras, bem como em quais delas haverá produção de vapor. Uma linguagem de modelagem algébrica foi utilizada para implementar computacionalmente o modelo, que foi resolvido por meio de um software de otimização. Os ajustes e a validação do modelo ocorreram por meio de um estudo de caso realizado em uma indústria de alimentos de grande porte localizada em Goiânia (GO). Nos experimentos realizados com os dados fornecidos pela empresa, os resultados obtidos com o modelo apresentaram melhores desempenhos econômicos do que aqueles praticados pela operação real. Diante dos bons resultados alcançados na aplicação do modelo em situações reais e da ausência de protocolos ou ferramentas para apoiar as decisões no sistema estudado, o modelo proposto apresenta-se como uma alternativa viável para apoiar algumas das principais decisões na operação de produção de vapor em caldeiras industriais.
|
43 |
Modelos de programação linear inteira mista para resolver problemas de planejamento da expansão e da operação de sistemas de transmissão de energia elétrica / Mixed integer linear programming models to solve problems of expansion and operation planning of electric energy transmission systemsVillajuan Montes, Cristiam Victor [UNESP] 19 February 2016 (has links)
Submitted by CRISTIAM VICTOR VILLAJUAN MONTES (cvillajuanm@gmail.com) on 2016-08-15T21:31:33Z
No. of bitstreams: 1
Cristiam Villajuan Montes_UNESP (1) ULTIMO.pdf: 4084141 bytes, checksum: ca80d95f9d6b055991ca9609f4c832a4 (MD5) / Approved for entry into archive by Ana Paula Grisoto (grisotoana@reitoria.unesp.br) on 2016-08-17T13:34:56Z (GMT) No. of bitstreams: 1
villajuanmontes_cv_me_ilha.pdf: 4084141 bytes, checksum: ca80d95f9d6b055991ca9609f4c832a4 (MD5) / Made available in DSpace on 2016-08-17T13:34:56Z (GMT). No. of bitstreams: 1
villajuanmontes_cv_me_ilha.pdf: 4084141 bytes, checksum: ca80d95f9d6b055991ca9609f4c832a4 (MD5)
Previous issue date: 2016-02-19 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Os problemas de planejamento da expansão de sistemas de transmissão e de fluxo de potência ótimo são de grande importância na área de sistemas de transmissão de energia elétrica. O primeiro consiste em determinar a expansão ótima do sistema, que deve ocorrer com o menor gasto monetário possível. No problema fluxo de potência ótimo deve-se encontrar o estado de operação do sistema de forma a minimizar um objetivo, no caso, os custos de geração. Ambos problemas possuem modelos de programação não-linear inteira mista. Além disto, o resultado ótimo de ambos deve cumprir com restrições operacionais, como o limite de tensão nas barras, os limites de fluxos nos ramos e os limites dos geradores. Para resolver os problemas citados, neste trabalho são apresentados modelos matemáticos de programação linear inteiro misto, aproximados, baseados em um modelo linearizado de fluxo de carga AC, que considera a presença da potência reativa, das perdas no sistema e magnitudes de tensões nas barras diferentes do valor nominal. Todos os modelos foram escritos na linguagem de modelagem matemática AMPL e resolvidos com o solver comercial CPLEX. Os modelos propostos foram testados com os sistemas IEEE de 14, 30, 57, 118 e 300 barras e com o sistema Garver para o planejamento da expansão de sistemas de transmissão. Os resultados foram comparados utilizando-se um fluxo de carga não linear, para verificar-se a precisão dos modelos propostos. / The transmission network expansion planning and the optimal power flow problems are of great importance in the field of electricity transmission systems. The first consists in determining the optimal expansion of the system, which must be done with the least possible investment. In the optimal power flow problem it must found the operating status of the system in order to minimize an objective, in this case, generation costs. Both problems have mixed-integer nonlinear programming models. In addition, the optimal solution of both must comply with operating constraints, such as the voltage limit on buses, the limits flows in branches and the limits of the generators. To solve the problems cited, in this work are presented approximate mixed integer linear programming models based on a linearized AC load flow model, which considers the presence of reactive power, the losses in the system and of nominal bus voltage magnitudes. All models were written in mathematical modeling language AMPL and solved with the commercial solver CPLEX. The proposed models were tested with the IEEE systems of 14, 30, 57, 118 and 300 buses and with the Garver system for transmission network expansion planning. Results were compared using a nonlinear load flow model, to verify the accuracy of the proposed models.
|
44 |
Desenvolvimento de um modelo matemático para minimização do custo total da operação de transporte de petróleo via marítima.PUCU, Paulo Aliberto Barros. 20 April 2018 (has links)
Submitted by Jesiel Ferreira Gomes (jesielgomes@ufcg.edu.br) on 2018-04-20T20:05:55Z
No. of bitstreams: 1
Paulo Aliberto Barros PUCU – TESE (PPGEQ) 2015.pdf: 1544520 bytes, checksum: 9f0c94dbee5a50446ebe3c2ab8e538a5 (MD5) / Made available in DSpace on 2018-04-20T20:05:55Z (GMT). No. of bitstreams: 1
Paulo Aliberto Barros PUCU – TESE (PPGEQ) 2015.pdf: 1544520 bytes, checksum: 9f0c94dbee5a50446ebe3c2ab8e538a5 (MD5)
Previous issue date: 2015-02-24 / O Brasil possui atualmente 115 plataformas de petróleo, sendo 79 fixas e 34 flutuantes, com capacidade de produção de 2,1 milhões de barris diários de petróleo. Diante desta produção torna-se necessária uma estratégia eficiente para a distribuição deste petróleo
para as refinarias, onde será processado e refinado. O petróleo proveniente das plataformas é transportado para as refinarias através de navios ou dutos, sendo que grande parte do custo operacional de produção é devido ao seu transporte. Por este motivo a minimização do custo de transporte é extremamente importante. Este trabalho tem por objetivo, utilizando a técnica de programação matemática (Programação Linear Inteira Mista – PLIM), reduzir os custos decorrentes do sistema de transporte. O modelo consiste em uma frota heterogênea de navios, os quais apresentam compartimentos que só podem ser ocupados por um único tipo de produto em cada viagem. Inicialmente são geradas todas as possíveis rotas e, posteriormente, selecionados os navios, associados às respectivas rotas, de forma a atender as demandas das refinarias e a necessidade de retirada de petróleo dos tanques de armazenamento das plataformas. Para a implementação do modelo foi utilizado o software GAMS (General Algebraic Modeling System), juntamente com os solveres de otimização CPLEX e BONMIN. / Currently, Brazil has 115 petroleum platforms, been 79 fixed and 34 floating, with daily production capacity of 2.1 million barrels of oil. Given this production is necessary a strategy for the efficient distribution of oil to refineries, where it will be processed and
refined. Oil from the platforms is transported to refineries through pipelines or ships, with much of the operational cost of production is due to transport. For this reason the minimization of the cost of transport is extremely important. This work has for
objective, using the technique of mathematical programming (linear mixed integer
programming - LMIP), reduce costs arising from transport system. The model consists
of a heterogeneous fleet of ships, which have compartments that can only be occupied
by a single type of product on each trip. Initially are generated all possible routes and
then selected the vessels, associated with their routes in order to attend the demand of
refineries and the need for removal of oil in the storage tanks of the platforms. For the
implementation of the model was used the software GAMS (General Algebraic
Modeling System), together with the solveres of CPLEX and BONMIN optimization.
The results were satisfactory.
|
45 |
Modelos de programação linear inteira mista para resolver problemas de planejamento da expansão e da operação de sistemas de transmissão de energia elétrica /Villajuan Montes, Cristiam Victor January 2016 (has links)
Orientador: Marcos Julio Rider Flores / Resumo: Os problemas de planejamento da expansão de sistemas de transmissão e de fluxo de potência ótimo são de grande importância na área de sistemas de transmissão de energia elétrica. O primeiro consiste em determinar a expansão ótima do sistema, que deve ocorrer com o menor gasto monetário possível. No problema fluxo de potência ótimo deve-se encontrar o estado de operação do sistema de forma a minimizar um objetivo, no caso, os custos de geração. Ambos problemas possuem modelos de programação não-linear inteira mista. Além disto, o resultado ótimo de ambos deve cumprir com restrições operacionais, como o limite de tensão nas barras, os limites de fluxos nos ramos e os limites dos geradores. Para resolver os problemas citados, neste trabalho são apresentados modelos matemáticos de programação linear inteiro misto, aproximados, baseados em um modelo linearizado de fluxo de carga AC, que considera a presença da potência reativa, das perdas no sistema e magnitudes de tensões nas barras diferentes do valor nominal. Todos os modelos foram escritos na linguagem de modelagem matemática AMPL e resolvidos com o solver comercial CPLEX. Os modelos propostos foram testados com os sistemas IEEE de 14, 30, 57, 118 e 300 barras e com o sistema Garver para o planejamento da expansão de sistemas de transmissão. Os resultados foram comparados utilizando-se um fluxo de carga não linear, para verificar-se a precisão dos modelos propostos. / Abstract: The transmission network expansion planning and the optimal power flow problems are of great importance in the field of electricity transmission systems. The first consists in determining the optimal expansion of the system, which must be done with the least possible investment. In the optimal power flow problem it must found the operating status of the system in order to minimize an objective, in this case, generation costs. Both problems have mixed-integer nonlinear programming models. In addition, the optimal solution of both must comply with operating constraints, such as the voltage limit on buses, the limits flows in branches and the limits of the generators. To solve the problems cited, in this work are presented approximate mixed integer linear programming models based on a linearized AC load flow model, which considers the presence of reactive power, the losses in the system and of nominal bus voltage magnitudes. All models were written in mathematical modeling language AMPL and solved with the commercial solver CPLEX. The proposed models were tested with the IEEE systems of 14, 30, 57, 118 and 300 buses and with the Garver system for transmission network expansion planning. Results were compared using a nonlinear load flow model, to verify the accuracy of the proposed models. / Mestre
|
46 |
Mathematical optimization of unbalanced networks operation with smart grid devices / Otimização matemática da operação de sistemas de distribuição considerando dispositivos de redes inteligentesSabillón Antúnez, Carlos Francisco 26 March 2018 (has links)
Submitted by CARLOS FRANCISCO SABILLON ANTUNEZ (cfsa27@gmail.com) on 2018-05-23T00:13:45Z
No. of bitstreams: 1
20180522ATeseCarlos.pdf: 6005665 bytes, checksum: cc46f4ea50bb15771fa5c7f3ce3f8107 (MD5) / Approved for entry into archive by Cristina Alexandra de Godoy null (cristina@adm.feis.unesp.br) on 2018-05-24T14:51:28Z (GMT) No. of bitstreams: 1
sabillonantunez_cf_dr_ilha.pdf: 6416516 bytes, checksum: 8832a0c7772aecb5081e9daa768de603 (MD5) / Made available in DSpace on 2018-05-24T14:51:28Z (GMT). No. of bitstreams: 1
sabillonantunez_cf_dr_ilha.pdf: 6416516 bytes, checksum: 8832a0c7772aecb5081e9daa768de603 (MD5)
Previous issue date: 2018-03-26 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / As redes de distribuição de energia elétrica devem estar preparadas para fornecer um serviço econômico e confiável a todos os clientes, bem como para integrar tecnologias relacionadas à geração distribuída, armazenamento de energia e veículos elétricos. Uma representação adequada da operação das redes de distribuição, considerando as tecnologias de redes inteligentes, é fundamental para atingir esses objetivos. Este trabalho apresenta formulações matemáticas para a operação em regime permanente das redes de distribuição, que consideram o desequilíbrio de redes trifásicas. Modelos matemáticos da operação de dispositivos relacionados à redes inteligentes presentes em redes de distribuição são desenvolvidos (e.g., dispositivos de controle volt-var, sistemas de armazenamento de energia e veículos elétricos). Além disso, características relacionadas à dependência da tensão das cargas, geração distribuída e limites térmico e de tensão também estão incluídos. Essas formulações constituem um marco matemático para a análise de otimização da operação das redes de distribuição de energia elétrica, o que possibilita modelar os processos de tomada de decisões. Objetivos diferentes relacionados a aspectos técnicos e/ou econômicos podem ser almejados dentro deste marco; Além disso, a extensão para otimização multi-período e multi-cenário é discutida. Os modelos apresentados são construídos com base em formulações de programação linear inteira mista, evitando o uso de formulações não-lineares inteiras mistas convencionais. A aplicação do marco apresentado é ilustrada em abordagens de controle para coordenação de carregamento de veículos elétricos, controle de magnitude de tensão e controle de geração distribuída renovável. Diversos métodos são desenvolvidos, com base no marco de otimização matemática, para otimizar a operação de sistemas de distribuição desbalanceados, considerando não apenas diferentes penetrações de veículos elétricos e fontes de energia renováveis, mas também a presença de sistemas de armazenamento e dispositivos de controle volt-var. A este respeito, o agendamento dinâmico e a otimização multi-período de janela rolante são frequentemente usados para alcançar uma operação ótima na rede. A eficácia e robustez das metodologias, bem como a confiabilidade do marco de otimização matemática, são verificados usando vários sistemas de teste (e.g., 123-node, 34-node e 178-node) com nós de média e baixa tensão, diferentes janelas de controle e várias disponibilidades de controle relacionadas aos dispositivos de rede inteligente. / Electric distribution networks should be prepared to provide an economic and reliable service to all customers, as well as to integrate technologies related to distributed generation, energy storage, and plug-in electric vehicles. A proper representation of the electric distribution network operation, taking into account smart grid technologies, is key to accomplish these goals. This work presents mathematical formulations for the steady-state operation of electric distribution networks, which consider the unbalance of three-phase grids. Mathematical models of the operation of smart grid-related devices present in electric distribution networks are developed (e.g., volt-var control devices, energy storage systems, and plug-in electric vehicles). Furthermore, features related to the voltage dependency of loads, distributed generation, and voltage and thermal limits are also included. These formulations constitute a mathematical framework for optimization analysis of the electric distribution network operation, which could assist planners in decision-making processes. Different objectives related to technical and/or economic aspects can be pursued within the framework; in addition, the extension to multi-period and multi-scenario optimization is discussed. The presented models are built based on mixed integer linear programming formulations, avoiding the use of conventional mixed integer nonlinear formulations. The application of the presented framework is illustrated throughout control approaches for plug-in electric vehicle charging coordination, voltage magnitude control, and renewable distributed generation control. Several methods are developed, based on this framework, to optimize the operation of unbalanced distribution systems considering not only different penetrations of electric vehicles and renewable energy sources but also the presence of storage systems and volt-var control devices. In this regard, dynamic scheduling and rolling multi-period optimization are often used to achieve optimal economic operation in the grid. The effective and robustness of the methodologies, as well as the reliability of the mathematical framework, are verified using many test systems (e.g., 123-node, 34-node, and 178-node) with medium and low voltage nodes, different operation control time frames, and several control availabilities related to the smart grid devices.
|
47 |
Problema de roteamento de veículos com frota mista, janelas de tempo e custos escalonados. / Fleet size and mix vehicle routing problem with time windows and scaled costs.João Luiz Veiga Manguino 18 February 2013 (has links)
O tema de roteamento de veículos é de grande importância na literatura e tem sido amplamente estudada pela sua importância para muitas indústrias. Com a evolução na literatura, mais características foram adicionadas para torná-lo mais próximo de situações reais. Alinhado com esta tendência, este trabalho aborda o problema de roteamento de veículos quando há a terceirização da frota que realiza as entregas. Uma forma de cobrança do frete é por meio de custos escalonados, que são calculados de acordo com o tipo de veículo e a distância percorrida, com valores fixos para cada faixa de distância. Embora seja uma forma comum de trabalho na indústria, nenhum trabalho focado nesta característica foi encontrado na literatura. Este problema é o problema de roteamento de veículos com frota mista, janelas de tempo e custos escalonados (FSMVRPTWSC). Ao abordar este problema, este trabalho apresenta um modelo de programação linear inteira mista que é avaliado em um cenário real da indústria. Além disso, três heurísticas de inserção sequencial são propostas para lidar com problemas maiores. Estes métodos são examinados por meio de testes computacionais em 168 problemas de referência gerados para este problema. Os experimentos numéricos mostram que os métodos são robustos e eficientes, apresentando um bom desempenho em conjuntos de problemas com diversas características. / The theme of vehicle routing is of great importance in the literature and has been widely studied for its relevance to many industries and, throughout the literature, more characteristics have been added to make it closer to real situations. Aligned with this trend, this paper addresses the vehicle routing problem when there is outsourcing of the fleet that delivers goods. One form of freight charging is by scaled costs, which are calculated according to the type of vehicle and the distance traveled, with fixed values for each distance range. Though it is a common form of work in the industry, no work focused on this characteristic was found in the literature. This problem is the fleet size and mix vehicle routing problem with time windows and scaled costs (FSMVRPTWSC). In approaching this problem, this paper presents a mixed integer linear programming model that is evaluated under a real situation scenario. Furthermore, three sequential insertion heuristics are proposed in order to deal with larger problems. These methods are examined through a computational comparative study in 168 benchmark problems generated for this problem. The numerical experiments show that the methods are robust and efficient, performing well in different problem sets.
|
48 |
Modelos para o problema de roteamento de veículos com restrições de empacotamento bidimensional / Models for the vehicle routing problem with two-dimensional loading constraintsSilva, Lorrany Cristina da 28 June 2017 (has links)
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.
|
49 |
Estabilidade de Carga no Problema de Carregamento de ContêineresOliveira, Liliane de Azevedo 22 February 2017 (has links)
Submitted by Erika Demachki (erikademachki@gmail.com) on 2017-06-21T21:21:46Z
No. of bitstreams: 2
Dissertação - Liliane de Azevedo Oliveira - 2017.pdf: 1274368 bytes, checksum: 9b7a4aa781e0951c3f12045277a55582 (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Erika Demachki (erikademachki@gmail.com) on 2017-06-29T18:27:23Z (GMT) No. of bitstreams: 2
Dissertação - Liliane de Azevedo Oliveira - 2017.pdf: 1274368 bytes, checksum: 9b7a4aa781e0951c3f12045277a55582 (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2017-06-29T18:27:23Z (GMT). No. of bitstreams: 2
Dissertação - Liliane de Azevedo Oliveira - 2017.pdf: 1274368 bytes, checksum: 9b7a4aa781e0951c3f12045277a55582 (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Previous issue date: 2017-02-22 / Fundação de Amparo à Pesquisa do Estado de Goiás - FAPEG / In this work we applied an algorithm based on the resolution of integer linear models for the problem of packing boxes into a single container considering the cargo stability constraint. The problem consists of arranging items (boxes) of different sizes inside a large object (container) to maximize the occupied container volume while respecting the imposed constraints. Four methods are investigated and compared due to vertical cargo stability, in which three of these methods are proposed in this work and based on the equilibrium of rigid bodies, and the other one is based on the factor of support of boxes bottom faces. In the case of the factor of support, a set of constraints can be inserted totally in the integer formulation, while in the other methods cutting planes are inserted during optimization of the formulation by a branch-and-cut algorithm. Computational tests on instances from the literature show that the usage of a factor of support underestimates the value of the optimal solution. The computational tests showed that the use of the factor of support may underestimate the solution, but its use with integer linear programming models has the advantage that feasible solutions are stable, while the other developed methods only verify stability and thus they depend of the integer linear program to return feasible solutions more quickly. By the way, the methods for the cargo stability developed here also overcame the factor of support for tests involving different types of mesh to pack into the container. / Aplica-se um algoritmo baseado na resolução de modelos de programação linear inteira para o problema de carregamento de caixas dentro de um único contêiner considerando a restrição de estabilidade de carga. O problema em estudo consiste em arranjar itens (caixas) de diferentes tamanhos dentro de um objeto maior (contêiner), de maneira maximizar a ocupação do volume do contêiner enquanto respeita as restrições dadas. Quatro métodos são investigados e comparados quanto a estabilidade vertical do empacotamento, sendo que três deles são desenvolvidos neste trabalho e baseados em conceitos do equilíbrio de corpos rígidos, enquanto um deles é baseado no fator de suporte da base das caixas. No caso do fator de suporte, um conjunto de restrições pode ser inserido totalmente dentro da formulação inteira, enquanto nos demais métodos planos de corte são inseridos durante a resolução da formulação por um algoritmo branch-and-cut.
Os testes computacionais mostraram que o uso do fator de suporte pode subestimar a solução, porém seu uso com modelos de programação linear inteira tem a vantagem das soluções viáveis poderem ser estáveis, enquanto os demais métodos desenvolvidos apenas verificam a estabilidade e, assim, dependem do programa linear inteiro retornar soluções viáveis mais rapidamente. Os métodos para a estabilidade de carga desenvolvidos neste trabalho mostraram-se superiores ao fator de suporte para testes envolvendo diferentes tipos de malhas para o empacotamento no contêiner.
|
50 |
Novos limitantes inferiores para o flowshop com buffer zero / New lower bounds for the zero buffer flowshopJoão Vítor Silva Robazzi 08 August 2018 (has links)
O sequenciamento e a programação da produção trazem grandes benefícios financeiros às empresas se realizados de forma adequada. Atualmente, soluções generalizadas apresentam resultados aceitáveis, porém têm como consequência benefícios inferiores quando comparados a estudos específicos. O ramo da otimização de resultados possui dois tipos de soluções: as exatas para problemas de menores dimensões e não exatas, ou heurísticas, para problemas de médias e grandes dimensões. Este trabalho apresenta algoritmos exatos do tipo Branch & Bound e Modelos de Programação Linear Inteira Mista para solucionar quatro variações de problemas de scheduling: Fm|block|∑Cjm, Fm|block|∑Tj, Fm|block, Sijk|∑Cjm e Fm|block, Sijk|∑Tj. As abordagens utilizadas são inéditas na literatura e apresentaram resultados animadores para a maioria dos cenários. O limitante para o tempo total de fluxo obteve resposta ótima em 100% dos casos para problemas de até 20 tarefas e 4 máquinas em menos de uma hora. Para o tempo total de atraso, o limitante se mostrou mais eficiente quando os valores das due dates apresentam alta taxa de dispersão. Para os casos com setup, foram elaboradas três variações de limitantes para cada problema. O limitante com setup que apresentou o melhor desempenho foi o que obteve a melhor relação entre o seu valor numérico e seu custo computacional. Os modelos MILP solucionaram 100% dos problemas sem setup para até 20 tarefas e 4 máquinas e para os casos com setup, foram solucionados problemas de até 14 tarefas e 4 máquinas no tempo limite de uma hora. Os testes computacionais mostram a eficiência na redução do número de nós e, consequentemente, no tempo de execução. Portanto, o estudo realizado indica que, para problemas de pequeno porte e médio, os métodos em questão possuem grande potencial para aplicações práticas. / Job Sequence and Programming give benefits both financial and organizational to any company when performed properly. Nowadays, there is still a gap between theory and practice due to solutions that are short in specification. The analyzed problems differ in type and dimension thus modifying its complexity. The results optimization field is divided into two types of solution: the exact solution for minor problems and the non-exact solution for greater dimension problems. The present paper presents exact algorithms to solve the problems Fm|block|∑Cjm, Fm|block|∑Tj, Fm|block, Sijk|∑Cjm by the Branch & Bounds and Mixed Integer Linear Program models. The approaches are new and presented good results for most cases. Bounds for the no-setup total flow time scenario solved 100% of the 20 jobs and 4 machines cases. High dispersion range due dates contributed for the effectiveness of the no-setup total tardiness bound\'s effectiveness. Three different approaches were developed for the setup cases. The best approach aimed to optimize the value/effort factor for the B&B. The Mixed Integer Linear Program models solved 100% of the no-setup cases for 20 jobs and 4 machines. The MILPs setup cases solved optimally 14 jobs and 4 machines cases. Computational tests were executed and analyzed and they highlighted the node count reduction and, consequently, the execution time. The present study points out that the exact methods can be applied to small and medium scheduling problems in practice.
|
Page generated in 0.0225 seconds