O problema de dimensionamento de lotes com restrições de capacidade (CLSP) consiste em determinar um plano de produção que satisfaça a demanda requerida, respeitando as limitações de capacidade, com o menor custo possível, ou seja, minimizando os custos de produção, estocagem e preparação de máquina. Encontrar uma solução factível para o CLSP, considerando tempo de preparação de máquina, é NP-completo. Nesta dissertação, para a resolução do CLSP, utiliza-se a decomposição de Dantzig-Wolfe e o procedimento de geração de colunas, encontrando bons limitantes inferiores. Duas diferentes estratégias de decomposição são exploradas, decomposição por itens e períodos. Para a obtenção de uma solução inteira para o problema (limitante superior) foram exploradas heurísticas lagrangianas, onde a solução inicial para as heurísticas provém da geração de colunas. Os limitantes obtidos podem ser utilizados em métodos exatos, como por exemplo, em algoritmos do tipo branch-and-price. Experimentos computacionais, baseados em exemplares gerados aleatoriamente, foram realizados e os resultados analisados, as variações dos parâmetros das instâncias foram sugeridas na literatura / The Capacitated Lot Sizing Problem (CLSP) consists in determining a production plan such that all demands are met and the total costs of production, inventory and setup are minimized. Since the problem to find a feasible solution to the CLSP with setup times is NP-complete, large problem instances have been solved by heuristic methods. In this dissertation, we are particularly concerned in using the methodology of Dantzig-Wolfe decomposition and column generation to generate good bounds to the CLSP with setup times and costs. Here, we analyse two types of decomposition which are based on items and time periods (lower bound) and some lagrangian-based heuristics (upper bound). Numerical results based on randomly generated intances suggest that highquality lower bounds are obtained by column generation algorithms, such as well as upper bounds by heuristics. These bounds are useful in exact solution methods, such as branch-and-price algorithms

O problema de dimensionamento de lotes com restrições de capacidade (CLSP) consiste em determinar um plano de produção que satisfaça a demanda requerida, respeitando as limitações de capacidade, com o menor custo possível, ou seja, minimizando os custos de produção, estocagem e preparação de máquina. Encontrar uma solução factível para o CLSP, considerando tempo de preparação de máquina, é NP-completo. Nesta dissertação, para a resolução do CLSP, utiliza-se a decomposição de Dantzig-Wolfe e o procedimento de geração de colunas, encontrando bons limitantes inferiores. Duas diferentes estratégias de decomposição são exploradas, decomposição por itens e períodos. Para a obtenção de uma solução inteira para o problema (limitante superior) foram exploradas heurísticas lagrangianas, onde a solução inicial para as heurísticas provém da geração de colunas. Os limitantes obtidos podem ser utilizados em métodos exatos, como por exemplo, em algoritmos do tipo branch-and-price. Experimentos computacionais, baseados em exemplares gerados aleatoriamente, foram realizados e os resultados analisados, as variações dos parâmetros das instâncias foram sugeridas na literatura / The Capacitated Lot Sizing Problem (CLSP) consists in determining a production plan such that all demands are met and the total costs of production, inventory and setup are minimized. Since the problem to find a feasible solution to the CLSP with setup times is NP-complete, large problem instances have been solved by heuristic methods. In this dissertation, we are particularly concerned in using the methodology of Dantzig-Wolfe decomposition and column generation to generate good bounds to the CLSP with setup times and costs. Here, we analyse two types of decomposition which are based on items and time periods (lower bound) and some lagrangian-based heuristics (upper bound). Numerical results based on randomly generated intances suggest that highquality lower bounds are obtained by column generation algorithms, such as well as upper bounds by heuristics. These bounds are useful in exact solution methods, such as branch-and-price algorithms

Submitted by Aelson Maciera (aelsoncm@terra.com.br) on 2017-09-26T19:15:52Z No. of bitstreams: 1 DissCDAC.pdf: 10114021 bytes, checksum: b3e4f52846924539caadab8587fe2250 (MD5) / Approved for entry into archive by Ronildo Prado (bco.producao.intelectual@gmail.com) on 2018-01-26T18:36:20Z (GMT) No. of bitstreams: 1 DissCDAC.pdf: 10114021 bytes, checksum: b3e4f52846924539caadab8587fe2250 (MD5) / Approved for entry into archive by Ronildo Prado (bco.producao.intelectual@gmail.com) on 2018-01-26T18:36:39Z (GMT) No. of bitstreams: 1 DissCDAC.pdf: 10114021 bytes, checksum: b3e4f52846924539caadab8587fe2250 (MD5) / Made available in DSpace on 2018-01-26T18:42:45Z (GMT). No. of bitstreams: 1 DissCDAC.pdf: 10114021 bytes, checksum: b3e4f52846924539caadab8587fe2250 (MD5) Previous issue date: 2017-03-10 / Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) / This work aims at treating the Dynamic Vehicle Allocation Problem (DVAP) in the context of the Brazilian Freight Transportation system. The problem consists of allocating empty vehicles to different terminals so as to attend the demand of freight transport during a predetermined planning horizon while maximizing the profit from these services. These type of decisions arise in customized freight transport services and in between-terminals operations of consolidation freight services. Given the size of the resulting models of real life problems confronted by third party logistics operators are large for using exact solution methods, heuristic methods have been used for giving good quality solution at the expense of optimality guarantee. In this context, the objective of this work is to contribute with solution methods that provide optimality guarantee or quality solution certificates for treating large-scale problems in reasonable computational times. The methods utilized are lagrangean relaxation, using subgradient optimization, and DantzigWolfe decomposition together with a lagrangian heuristic and factibilization method, respectively. Computational experiments are presented and analyzed for randomly generated instances and real-world instances from a brasilian freight operator. The latter method shows great potential for treating large-scale problems. / Este trabalho aborda o problema de Alocação Dinâmica de Veículos (PADV) no contexto de Transporte Rodoviário de Carga. O problema envolve alocar veículos de carga para atender a demanda de transporte de carga prevista entre terminais durante um horizonte de tempo multiperíodos e finito. O objetivo e maximizar o lucro gerado pelos serviços completados. Este tipo de decisões surge nos serviços de transporte de carga de lotação e na parcela de transporte de transferência dos serviços de transporte de carga consolidada. Dado que o tamanho dos problemas que enfrentam as transportadoras logísticas sÃo consideravelmente grandes parase resolver com métodos exatos em tempos computacionais aceitáveis, tem-se utilizado métodos heurísticos para dar boas soluções sem garantia de otimalidade mas em tempos toleráveis a estes problemas. Neste contexto, pretende-se contribuir com métodos de solução que proporcionem garantia de otimalidade e/ou boas soluções aproximadas, acompanhadas de certificados de otimalidade ou de qualidade de solução, para tratar problemas de porte em tempos razoáveis. Os métodos propostos estao baseados em relaxação lagrangiana, utilizando o método de otimização do subgradiente, e na decomposto de Dantzig Wolfe, utilizando a técnica de geração de colunas, além de heurísticas lagrangianas e de factibilização acopladas nestes métodos. Experimentos computacionais usando instâncias geradas aleatoriamente e baseados em dados reais de transportadoras brasileiras sao apresentados e analisados, para as duas abordagens, mostrando seus potenciais de aplicação pratica, principalmente para problemas de grande porte.