Algoritmos exatos e heurísticos para variações de problemas de roteamento, empacotamento e corte guilhotinado

• Ano de defesa: 2020
• Autor(a) principal: Eduardo Theodoro Bogue
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de Minas Gerais; Brasil; Programa de Pós-Graduação em Ciência da Computação; UFMG
• Palavras-chave em Português: Programação Dinâmica; Programação Linear Inteira; Problema do Roteamento de Veículos com Múltiplas Janelas de Tempo; Problema do Corte Guilhotinado Bidimensional em Três Estágios com Restrições de Precedência em Lote; Problema da Configuração de Produtos; Computação – Teses; Programação dinâmica; Programação linear inteira.; Problema de roteamento de veículos
• Link de acesso: http://hdl.handle.net/1843/33972

Combinatorial optimization problems occur in mny practical everyday situations, such as transportation and distribution logistics, resource allocation, among others. Cutting, packaging, and vehicle routing problems are examples of classic and well-studied combinatorial optimization problems. New variants of these problems emerge as applications require additional constraints or relax some constraints of the problem. In this thesis we are interested in three variants of classic problems in literature: the Vehicle Routing Problem with Multiple Time Windows (VRPMTW), the Product Configuration Problem (PCP), and the 2-Dimensional Cutting Stock Problem Batch Constraints (2DCSP-BC). For the Vehicle Routing Problem with Multiple Time Windows, we propose , a Column Generation (CG) algorithm and a post-optimization heuristic based on a Variable Neighborhood Search (VNS) to provide both lower and upper bounds for the cost optimal solution VRMTW. The results showed that CG was able to produce lower bounds within one hour of running time for l 66.7 \% of the instances.Besides, the post-optimization heuristic was able to improve the solution provided by the VNS heuristic in 28.9 %, finding interger optimal solutions for 39,9% of instances where lower bounds are known, the average optimality gap was 6, 0 \% on average. In the Product Configuration Problems, an entire linear programming formulation and an exact pseudo-polynomial time dynamic programming algorithm were proposed. Computational experiments showed that both algorithms were able to find optimal solutions for all instances evaluated with up to 10,000 components. Finally, three heuristics were developed for the 2-Dimensional Cutting Stock Problem Batch Constraints 2DCSP-BC, where two heuristics are based on heuristics from the literature, and one heuristics is based dynamic programming algorithm. Computational experiments performed on the realistic instances showed that the dynamic programming heuristics obtained the best er results tamog the constructive heuristics.