Esta dissertação apresenta um problema de otimização relacionado com a designação de rotas de carga completa para frota própria ou dedicada, visando a minimização dos custos de transporte numa rede de distribuição formada por fábricas uni-produto, centros de distribuição (consolidação) e clientes. Essas rotas são conjugadas formando ciclos fechados (viagens) para garantir a otimização do tempo através do movimento contínuo desta frota dedicada. A metodologia é aplicada em uma rede de distribuição de um fabricante de linha branca no Brasil. Além dos resultados econômicos favoráveis, outras contribuições para o tema de conjugação de rotas foram encontradas nesta dissertação, tais como, a regra de formação de caminhos, o limite para conjugação de rotas numa rede de distribuição e o desenvolvimento de uma estrutura para custear esses caminhos conjugados. O modelo de programação linear inteira desenvolvido mostrou-se apto a resolver problemas de tamanho real em tempo factível, mesmo com recursos computacionais comuns. / This thesis presents an optimization problem regarding the assignment of truckload lanes to a private or dedicated fleet to minimize transportation costs in a distribution network formed by single-product plants, distribution (consolidation) centers and clients. These lanes are conjugated in order to form closed cycles (trips) to guarantee time optimization through continuous movement of this dedicated fleet. This methodology is applied to a distribution network of a white goods manufacturer in Brazil. More than good economic results, there are others contributions for the theme of conjugated lanes in this thesis, such as, the rule of formation trips, the limit to conjugated lanes to a distribution network and the development of a structure to get the conjugated lanes\' costs. The model of integer linear program that was development is capable to solve the real problems in a reasonable time, even if with regular.

Esta dissertação trata do problema da distribuição de combustíveis com caminhões-tanque para realizar a entrega de derivados de petróleo para diversos postos de abastecimento a partir de uma base de distribuição. O problema consiste da determinação de rotas para veículos de uma frota heterogênea, visando minimizar o custo total de distribuição dos veículos envolvidos sujeitos a restrições de capacidade dos compartimentos de cada veículos. O objetivo é garantir que cada entrega seja alocada a exatamente um veículo e que todos os veículos sejam adequadamente seqüenciados. Deve-se notar que cada caminhão pode ter até seis compartimentos com diferentes capacidades. Além disso, são consideradas restrições que impedem que um veículo atenda determinado cliente. As restrições relacionadas a essa alocação de pedidos aos compartimentos dos veículos fazem esse problema tornar-se muito diferente de outros problemas de roteirização de veículos. Para ilustrar isso, uma entrega de 5.000 litros para um cliente apenas pode ser alocada em um compartimento de exatamente 5.000 litros, mas não a um compartimento maior preenchido parcialmente. Adicionalmente, caminhões do mesmo tamanho e capacidade (e.g. 30.000 litros) podem possuir diferentes números de compartimentos, inclusive de diferentes tamanhos (e.g. um caminhão de 30.000 litros pode ter 6 compartimentos de 5.000 litros ou 2 compartimentos de 10.000 litros e 2 compartimentos de 5.000 litros), tornando o problema aindamais complexo. Propõe-se inicialmente uma modelagem matemática inédita para o problema. Dada a dificuldade de resolver instâncias de tamanhos reais utilizando ferramentas comerciais de otimização como o ILOG CPLEX 9.0, foi também proposto um algoritmo heurístico que pode alcançar boas soluções em tempos curtos de processamento. Este algoritmo é inspirado em algumas idéias do GRASP. ) Ele se baseia em um método heurístico rápido de construção, que é repetidamente aplicado, baseado em um algoritmo de controle que, repedida e aleatoriamente, remove alguns pedidos da solução corrente, e então reconstrói uma nova solução a partir dos pedidos não-alocados restantes. Também são relatados resultados computacionais com diversos problemas de teste que foram gerados, considerando diferentes tamanhos de problema, bem como diferentes níveis de dificuldade de alocação de pedidos aos caminhões. / This Master\'s dissertation deals with the problem of distributing fuels by petroleum tank trucks in the context of the delivery of petroleum products to gas stations originating at a single distribution base. The problem comprises determining the vehicle delivery routes for a heterogeneous fleet, aiming to minimize the total distribution and fixed costs of the vehicles involved subject to capacity constraints for the tank compartments of each vehicle. The objective is to ensure that each delivery is assigned to exactly one truck and all trucks are properly sequenced. It should be noticed that each truck may have one to six tank compartments with different capacities eventually. In addition, there may be restrictions on which vehicles can service each client. The constraints related to the assignment of deliveries to truck compartments makes this problem much different from other vehicle routing problems, thus preventing the traditional routing approaches and formulations to be applied in this case. To illustrate this, a delivery of 5,000 liters to a single client can only be assigned to a compartment of exactly 5,000 liters, but not to a larger compartment which is not entirely filled up. In addition, trucks of the same size and capacity (e.g. 30,000 liters) may have different numbers of compartments and even different sizes (e.g. a 30,000 liters truck may have 6 compartments of 5,000 liters or 2 compartments of 10,000 liters and 2 compartments of 5,000 liters), making the problem even more complicated. We initially propose a novel mathematical IP formulation for this problem. Given the difficulty to solve instances of the same size as found in practice using off-the-shelf cutting-edge optimization tools like ILOG CPLEX 9.0, we also propose a heuristic algorithm that can reach good solutions in very short CPU times. This algorithm is inspired on some ideas of GRASP. ) It relies on a fast constructive heuristic, which is repeatedly applied, based on a control algorithm that repeatedly and randomly remove some deliveries from the current solution, and then rebuilds a new solution from the remaining unassigned and unrouted deliveries. We also report the computational results with several test problems that we have generated, considering different problem sizes, as well as different levels of difficulty related to assignment of orders to trucks.

O objetivo desse trabalho é o de estudar o problema de programação de tarefas num ambiente produtivo com uma única máquina com data comum de entrega. Nesse caso, as tarefas, depois de processadas uma única vez na máquina, devem ser entregues em uma data comum e sofrem penalidades de adiantamento e de atraso conforme o instante em que são completadas. Na prática, esse problema é encontrado em casos de pedidos de lotes de produtos com data de entrega comum préespecificada, embarques para exportação e material químico ou misturas que têm vida média de curta duração. Problemas desse tipo são NP-hard (Hall, Kubiak & Sethi, 1991; Hoogeven & van de Velde, 1991), sendo comumente tratados na literatura através de heurísticas e meta-heurísticas. Visto não ser de nosso conhecimento a existência na literatura de tratamento desse problema através de métodos exatos, propôs-se a utilização de um algoritmo do tipo branch-and-bound para obtenção da solução ótima do problema que minimize a soma das penalidades de adiantamento e de atraso. No desenvolvimento do algoritmo, a utilização de propriedades do problema foi importante na elaboração de limitantes inferiores e regras de dominância que melhoraram a eficiência do modelo. Os experimentos realizados avaliaram o desempenho de diferentes critérios elaborados, como escolha do nó pai, limitante inferior, ordem de execução das estratégias e ordem de construção da seqüência. Os resultados obtidos mostraram-se robustos quando comparados com o benchmark da literatura e revelaram o bom desempenho do modelo para problemas de pequeno porte, superando o desempenho de programas de otimização comerciais. / The objective of this work is to study the single-machine scheduling problem with a common due date. In this case, jobs, after be processed only once in the machine, must be delivered in a common due date and they are penalized of earliness or tardiness according to their completion time. This problem is found in cases of batch production with prespecified common due date, exportation shipping and chemical material that has short half-life period. This kind of problem is NP-hard (Hall, Kubiak & Sethi, 1991; Hoogeven & van de Velde, 1991) and it has been treated in the literature by heuristics and meta-heuristics. Not having knowledge about previous treatment by exact methods in the literature, it was proposed the implementation of a branch-and-bound algorithm to obtain the optimal solution that minimizes the total weighted earliness and tardiness penalties. In the development of the algorithm, the utilization of problem properties was important to the elaboration of lower bounds and pruning rules that have enhanced the efficiency of the model. The realized tests have evaluated the performance of different criteria, like the choice of father node, lower bound, strategy execution order and sequence construction order. The obtained results have demonstrated robustness comparing to benchmark and they have revealed the good working of the model for small problems, overcoming optimization software performance.

CoordenaÃÃo de AperfeiÃoamento de Pessoal de NÃvel Superior / O principal objetivo deste trabalho à avaliar a relevÃncia de infraestruturas econÃmicas para a competitividade industrial dos estados do Cearà e Santa Catarina no perÃodo 1980 â 2010, sendo o perÃodo tratado no trabalho sob a forma de quinquÃnios, com a tÃcnica de AnÃlise EnvoltÃria de Dados (DEA), haja vista o Ãltimo estado apresentar indÃstria desconcentrada em seu territÃrio e maior participaÃÃo no PIB industrial brasileiro e o estado nordestino apresentar, nas Ãltimas dÃcadas, iniciativas para desconcentrar a indÃstria da regiÃo metropolitana de Fortaleza, tornando-se mais competitivo. Para isso, considerou-se como benchmark o estado de SÃo Paulo por apresentar historicamente o maior PIB industrial das unidades da federaÃÃo. Com testes economÃtricos fora definida uma funÃÃo de produÃÃo e foram usados dados das seguintes variÃveis: Capital, emprego e variÃveis de infraestrutura (comunicaÃÃes, energia e transportes). Foram formuladas capacidades (indicadores) com as informaÃÃes de infraestrutura. A DEA tem como princÃpio comparar a eficiÃncia entre unidades (realidades operacionais ao invÃs de ideais intangÃveis). Considerando-se a eficiÃncia clÃssica, cerca de 52% das observaÃÃes foram classificadas como eficientes (Cearà apresentou o maior nÃmero de unidades eficientes). No entanto, para a eficiÃncia composta normalizada, considerada como uma avaliaÃÃo pessimista, somente 1 observaÃÃo foi considerada eficiente (Santa Catarina no ano de 2000). Independentemente do tipo de eficiÃncia, Santa Catarina apresentou a menor eficiÃncia mÃdia. Os resultados encontrados corroboram para a relevÃncia (peso) das infraestruturas consideradas para a eficiÃncia (competitividade industrial) dos estados.

nÃo hà / A resoluÃÃo de um Problema de Sequenciamento sempre à uma operaÃÃo que demanda grandes recursos, devido ao grande volume de dados inerentes a formulaÃÃo do problema. O uso bem sucedido do Algoritmo GenÃtico quando aplicado ao Problema de Sequenciamento ClÃssico deu-se atravÃs dos experimentos computacionais encontrados na literatura. O objetivo geral deste trabalho à relacionar as similaridades do Problema de Sequenciamento ClÃssico como um Problema do Caixeiro Viajante e resolvÃ-lo utilizando a metaheurÃstica Algoritmo GenÃtico. Foram realizados experimentos computacionais utilizando as instÃncias da OR-Library (Beasley, 1990), conjunto de dados de Taillard (1993). A anÃlise das soluÃÃes obtidas por operadores genÃticos foram realizadas, com o intuito de mostrar a evoluÃÃo da busca. O mÃtodo proposto foi comparado com outros mÃtodos discretos, onde constata-se o bom desempenho do Algoritmo GenÃtico, apresentando melhores resultados em 69 das 90 instÃncias testadas. / The resolution of a Flow Shop Problem is always an operation which requires great resources, due to the large volume of data inherent in the problem formulation. The successful use of Genetic Algorithm when applied to the Classic FSP took place through computational experiments found in the literature. The aim of this work is to relate the similarities of the Classic Scheduling Problem as a Traveling Salesman Problem (TSP) and solve it using the Genetic Algorithm metaheuristic. Computational experiments were performed using the OR - Library instances (Beasley, 1990), dataset of Taillard (1993). The analysis of the solutions obtained by genetic operators were carried out in order to show the progress of the search. The proposed method was compared with other discrete methods where there is evidence of the good performance of Genetic Algorithm

nÃo hà / The continuous growth of populations and their concentration in great urban centers is reflected in an increasing demand for products and services in such areas. However, the distribution of a range of different products within the same geographic area, in many cases relying on the same transportation infrastructure, is becoming ever more complex and costly. The purpose of this study was to develop and test an application based on metaheuristic Genetic Algorithms (GA) designed to optimize the logistics of product distribution and delivery. In the literature this is known as the Travelling Salesman Problem (TSP) of the NPhard class. The method was initially tested on small and intermediate problems from the TSP library. Performance was satisfactory within an acceptable computational time. Subsequently, the method was tested in a real-life scenario: a specialized product distributor in Fortaleza (Northeastern Brazil). Again, results were satisfactory as the method was able to optimize the logistics of all the distributorâs delivery routes. / O contÃnuo crescimento das populaÃÃes e a concentraÃÃo nos centros urbanos fazem com que a demanda por produtos e serviÃos tambÃm cresÃa nestas regiÃes. Entretanto, dentro de um mesmo espaÃo geogrÃfico, e em muitos casos, com a mesma infraestrutura de transporte disponÃvel, a distribuiÃÃo fÃsica de produtos torna-se uma atividade cada vez mais complexa e onerosa. O objetivo deste trabalho foi propor uma aplicaÃÃo baseada na MetaheurÃstica Algoritimos GenÃticos (AG), para ser utilizada em serviÃos de distribuiÃÃo fÃsica de produtos a fim de obter maior eficiÃncia logÃstica na construÃÃo da sequÃncia de entregas. Na literatura este problema à conhecido como uma variante do Problema do Caixeiro Viajante (PCV), e pertence à classe NP-Hard. O mÃtodo foi testado em problemas de pequeno e mÃdio porte da TSP-LIBRARY. Os resultados foram obtidos com desempenho satisfatÃrio num tempo computacional aceitÃvel. Para aplicaÃÃo prÃtica, foi considerada uma empresa especialista em distribuiÃÃo de produtos com atuaÃÃo no municÃpio de Fortaleza. Os resultados dos testes prÃticos foram aceitÃveis, uma vez que o mÃtodo conseguiu otimizar todas as rotas observadas e praticadas pela empresa.

Orientador: Vinicius Amaral Armentano / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-10T01:09:54Z (GMT). No. of bitstreams: 1 Fonseca_SaraLuisadeAndrade_M.pdf: 1363535 bytes, checksum: aa7c01c779a21ea25aa3b603425c92fe (MD5) Previous issue date: 2007 / Resumo: Em 1958, Gomory propôs uma desigualdade válida ou corte a partir do tableau do método simplex para programação linear, que foi utilizado no primeiro método genérico para resolução de problemas de programação inteira. Em 1960, o corte foi estendido para problemas de programação inteira mista. Em 1973, Chvátal sugeriu um corte derivado da formulação original do problema de programação inteira, e devido à equivalência com o corte de Gomory, este passou a ser chamado de corte de Chvátal-Gomory. A importância do corte de Gomory só foi reconhecida em 1996 dentro do contexto do método branch-and-cut para resolução de problemas de programação inteira e programação inteira mista. Desde então, este corte é utilizado em resolvedores comerciais de otimização. Recentemente, diversos cortes novos derivados do corte de Chvátal-Gomory foram propostos na literatura para programação inteira. Este trabalho trata do desenvolvimento de algoritmos para alguns destes cortes, e implementação computacional em um contexto de branch-and-cut, no ambiente do resolvedor CPLEX. A eficácia dos cortes é testada em instâncias dos problemas da mochila multidimensional, designação generalizada e da biblioteca MIPLIB. / Abstract: In 1958, Gomory proposed a valid inequality or cut from the tableau of the simplex method for linear programming, which was used in the first generic method for solving integer programming problems. In 1960, the cut was extended to handle mixed integer programming problems. In 1973, Chvátal suggested a cut that is generated from the original formulation of an integer programming problem, and due to the equivalence with the Gomory cut, it was named Chvátal-Gomory cut. The importance of the Gomory cut was recognized only in 1996 in the context of the branch-and-cut method for solving (mixed) integer programming problems. Today, such a cut is utilized in optimization commercial solvers. Recently, several new cuts derived from the Chvátal-Gomory cut have been proposed in the literature for integer programming. This work deals with the development of algorithms and computational implementations for some of the new proposed cuts, in a context of the branch-and-cut method, by using the CPLEX solver. The efficiency of the cuts is tested on instances of the multi-dimensional knapsack, generalized assignment problems, and instances from the MIPLIB library. / Mestrado / Automação / Mestre em Engenharia Elétrica

O presente trabalho trata da modelagem do ambiente operacional de uma empresa florestal dentro de um enfoque probabilístico. Objetiva-se com esta abordagem incorporar elementos probabilísticos em um modelo que venha a simular as incertezas do mundo real. Diversas técnicas foram utilizadas na modelagem do sistema simulador, dentre as quais destaca-se: o Modelo de Hertz para Análise de Risco em Investimentos de Capital e a Teoria das Oscilações Aleatórias dos Preços de Ativos Financeiros. A base de dados para a modelagem foi obtida a partir de uma planilha de custos e rendimentos operacionais de um projeto florestal implantado pela empresa Duratex S.A. no município de Lençóis Paulistas/SP no ano de 1990. O resultado do trabalho foi o desenvolvimento de um sistema computacional o qual permite comparar as opções de Reforma e de Condução de um projeto florestal. Concluiu-se que no projeto pesquisado a opção de Condução é preferível à opção de Reforma, haja visto que nesta última opção existe uma alta probabilidade (aproximadamente 40%) do resultado financeiro ser negativo. Uma elevada variabilidade nas variáveis de custo e de rendimento operacional, de um número significativo de operações, torna a Reforma Florestal uma opção de alto risco financeiro. / The present work treats of modeling the forestry operational environment under a probabilistic perspective. The purpose of this approach is to incorporate probability in a model that results in the simulation from uncertainty of the real world. Several technics were used in the modeling of the simulation system, among them are: the Hertz model of risk analyse in capital investment and the theory of random walkes in stock prices. The data base for the modeling was obtained from a cost and operational performance plan of a forestry project from Duratex Company, localized in Lençois Paulista city and implanted in 1990. The product from this work is the development of a computer system which permited to compare two forestry options: forestry conduction and forestry reform. It follows that the conduction option is preferred to the forestry reform option because in the last option there is a high probability (aprox.40%) to present a negative financial result. A high variability cost and operational performance from an expressive number of operations makes the forestry reform an option with a high risk.

A era do petróleo parece estar chegando ao fim e novas fontes de energia, renováveis e mais amigas do meio ambiente, já estão disponíveis para a sociedade. Dentre essas fontes, o biodiesel vem chamando a atenção das autoridades pela sua compatibilidade com o diesel e pelo potencial de geração de riqueza no campo. A Lei 11.097/2005 autorizou a introdução do biodiesel no Brasil, obrigando a adição de 2% ao diesel de petróleo, a partir do ano de 2008. O biodiesel é um produto obtido da transesterificação de óleos e gorduras de origem vegetal, animal ou residual que possui características muito semelhantes ao diesel do petróleo. Sendo assim, não é preciso “reinventar o carro” nem modificar a distribuição para o consumidor final, visto que os motores a diesel podem rodar, facilmente, com porções de biodiesel ao diesel o qual pode ser comercializado nos atuais postos de combustíveis. Assim, é necessário estruturar a cadeia produtiva do biodiesel, para que se possa atender a uma demanda capaz de substituir 2% do diesel comercializado, a partir do ano de 2008. Diante disso, este trabalho visa a elaborar um modelo matemático, utilizando as técnicas da programação linear para auxiliar na decisão sobre a localização das futuras usinas de biodiesel e a sua estrutura de distribuição. Como cada Estado do Brasil poderá utilizar diferentes fontes de óleo vegetal, com base em suas características (geoclimáticas) para a produção de biodiesel, cada Estado poderá ter diferentes configurações da cadeia produtiva. Este trabalho testou o modelo no Estado do Rio Grande do Sul onde a tendência é produzir biodiesel a partir do óleo de soja. O modelo demonstrou, dentre as alternativas escolhidas e com base nas premissas assumidas ao longo deste trabalho, que uma usina de escala grande (120.000 toneladas/ano), localizada em Canoas, seria a alternativa que minimizaria os custos totais de transporte e de instalação. Entretanto, o modelo proposto é flexível para diferentes contextos e distintos parâmetros, adaptando-se às necessidades de cada região. / The age of oil seems to be near the end and new sources of energy, renewable and more environmentally friendly, are already available for society. Amongst these sources, biodiesel has been standing out for its compatibility with diesel and for its potential of wealth generation in this field. The Brazilian law 11,097/2005 authorizes the introduction of biodiesel in Brazil, compelling a 2% addition into diesel oil from the year 2008. Biodiesel is results from the transesterification of oils and fats of vegetal, animal or residual origins, and has very similar characteristics to diesel oil. Thus, one does not need to “reinvent the car” or modify distribution for the final consumer, once diesel-run engines can easily work with portions of biodiesel mixed within diesel oil that is commercialized in current service stations. Thus, it is necessary to structure the productive chain of biodiesel so that it can take care of a demand replacing 2% of the diesel commercialized from the year 2008. Therefore, this work aims to elaborate a mathematical model, using linear programming techniques to help decide where to locate the future biodiesel plants as well as their distribution structure. As each state of Brazil will make use of different vegetal oil sources, due to geographic characteristics, when producing biodiesel, each state might have different configurations of productive chain. This work tests the model in the State of Rio Grande do Sul, where producing biodiesel from the soy oil is the trend. It demonstrates, amongst the alternatives chosen and based on the assumptions throughout this work, that a plant of large scale (120,000 tons per year) located in the city of Canoas would most probably be the alternative to minimize the total costs of transport and installation. However, the model proposed is flexible for different contexts and parameters, able to adapt to the necessities of each region.

Os problemas logísticos estão se apoiando de forma bastante expressiva na pesquisa operacional a fim de obter uma maior eficiência em suas operações. Dentre os vários problemas relacionados à designação de veículos em um sistema logístico, o de escalonamento de veículos com múltiplas garagens, MDVSP (Multiple Depot Vehicle Scheduling Problem), vem sendo abordado em diversas pesquisas. O MDVSP pressupõe a existência de garagens que interferem no planejamento das sequências com as quais as viagens devem ser executadas. Frequentemente, métodos exatos não podem resolver as grandes instâncias encontradas na prática e, para poder levá-las em consideração, várias abordagens heurísticas estão sendo desenvolvidas. O principal objetivo deste trabalho, portanto, foi solucionar o MDVSP através de uma heurística utilizando o método de busca-tabu. A principal motivação para a realização deste trabalho surgiu a partir da indicação de que apenas recentemente o uso de meta-heurísticas está sendo aplicado ao MDVSP (Pepin et al. 2008) e das limitações elencadas no estudo de Rohde (2008), o qual utilizou o algoritmo branch-and-bound em uma das etapas da heurística apresentada para resolver o problema, o que fez aumentar o tempo de resolução do problema. O método de pesquisa para solução deste problema foi baseado em adaptações das tradicionais técnicas de pesquisa operacional, e propiciou a resolução do MDVSP apresentando resultados bastante competitivos quanto ao custo da função objetivo, número de veículos utilizados e tempo computacional necessário. / Currently the logistical problems are relying quite significantly on Operational Research in order to achieve greater efficiency in their operations. Among the various problems related to the vehicles scheduling in a logistics system, the Multiple Depot Vehicle Scheduling Problem (MDVSP) has been addressed in several studies. The MDVSP presupposes the existence of depots that affect the planning of sequences to which travel must be performed. Often, exact methods cannot solve large instances encountered in practice and in order to take them into account, several heuristic approaches are being developed. The aim of this study was thus to solve the MDVSP using a meta-heuristic based on tabu-search method. The main motivation for this work came from the indication that only recently the use of meta-heuristics is being applied to MDVSP context (Pepin et al. 2008) and, also, the limitations listed by Rohde (2008) in his study, which used the branch-and-bound in one of the steps of the heuristic presented to solve the problem, which has increased the time resolution. The research method for solving this problem was based on adaptations of traditional techniques of Operational Research, and provided resolutions presenting very competitive results for the MDVSP such as the cost of the objective function, number of vehicles used and computational time.