Calculating an optimized pallet packing plan by minimizing the number of pallets
Palonen, Joonas (2023)
2023
Tietotekniikan DI-ohjelma - Master's Programme in Information Technology
Informaatioteknologian ja viestinnän tiedekunta - Faculty of Information Technology and Communication Sciences
This publication is copyrighted. Only for Your own personal use. Commercial use is prohibited.
Hyväksymispäivämäärä
2023-10-19
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:tuni-202310118757
https://urn.fi/URN:NBN:fi:tuni-202310118757
Tiivistelmä
This thesis explores the challenges and solutions associated with calculating a pallet packing plan. The framework for the thesis comes from a real-world industrial setting, which poses additional constraints on the problem formulation. The goal of our work is to prove on a concept level, that there is room for optimization and that packing plans can be made more efficient with the use of constraint programming paradigm. This is done by implementing a new methodology for calculating pallet packing plans and comparing the existing and proposed methods through simulations.
The study delves into combinatorial optimization problems, with a particular focus on the Knapsack Problem, Bin Packing Problem, Pallet Loading Problem, and Circle Bin Packing Problem. It also discusses the computational complexity associated with these problems.
We provide a detailed description of the business constraints associated with pallet packing and propose a three-step algorithm as a solution. This algorithm begins with packing individual reels into stacks, followed by assigning these stacks to pallets, and finally optimizing the packing plan by iterating over all the pallets to fit the stacks onto smaller pallets, if possible. This approach can be viewed as a combination of 1D-Bin Packing Problem (1D-BPP) and 2D-Circle Bin Packing Problem (2D-CBPP). By breaking a 3D problem into two sub-parts we can reduce the simultaneous complexity of the problem and integrate business and manufacturing process constraints into the calculation process.
We conducted experiments with artificial data and simulations on historical order data to benchmark the time complexity and feasibility of our proposed packing plan implementation. In conclusion, we discuss the successes and shortcomings of our Proof-of-Concept (PoC) implementation. We acknowledge that while our proposed method can handle complex problem instances, it requires further development and optimization to improve calculation speed and the feasibility of the packing plans in practice. We suggest that a combination of the existing and proposed implementations could provide the best results, with the existing method handling most problem instances and our new implementation tackling more complex cases.
The study delves into combinatorial optimization problems, with a particular focus on the Knapsack Problem, Bin Packing Problem, Pallet Loading Problem, and Circle Bin Packing Problem. It also discusses the computational complexity associated with these problems.
We provide a detailed description of the business constraints associated with pallet packing and propose a three-step algorithm as a solution. This algorithm begins with packing individual reels into stacks, followed by assigning these stacks to pallets, and finally optimizing the packing plan by iterating over all the pallets to fit the stacks onto smaller pallets, if possible. This approach can be viewed as a combination of 1D-Bin Packing Problem (1D-BPP) and 2D-Circle Bin Packing Problem (2D-CBPP). By breaking a 3D problem into two sub-parts we can reduce the simultaneous complexity of the problem and integrate business and manufacturing process constraints into the calculation process.
We conducted experiments with artificial data and simulations on historical order data to benchmark the time complexity and feasibility of our proposed packing plan implementation. In conclusion, we discuss the successes and shortcomings of our Proof-of-Concept (PoC) implementation. We acknowledge that while our proposed method can handle complex problem instances, it requires further development and optimization to improve calculation speed and the feasibility of the packing plans in practice. We suggest that a combination of the existing and proposed implementations could provide the best results, with the existing method handling most problem instances and our new implementation tackling more complex cases.