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

Abstract

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.