| 摘要(英) |
In recent years, with the rise of Industry 4.0, there has been a revolutionary development in various aspects such as digital technology, automated machinery for loading and unloading, smart manufacturing, and the application of the Internet of Things (IoT). These advancements have not only led to significant growth in different industries but have also effectively improved production efficiency and reduced costs. The primary goal of Industry 4.0 is to integrate manufacturing resources, data, and processes to establish a more flexible and intelligent manufacturing industry. In this process, the critical process of product packaging and shipping has become crucial. A well-optimized arrangement during the packing of goods can lead to highly efficient utilization of loading space. This not only conserves the quantity of tools for carrying goods, such as pallets, containers, and trucks, but also reduces the time and labor costs associated with repetitive placement attempts.
This paper applies image processing technology to identify box sizes for the purpose of automated categorization of various types of boxes. It conducts packing computations for boxes of different sizes and quantities using traditional trial-and-error method, greedy algorithm, and depth-first search algorithm. By comparing the differences in computation results and analyzing the strengths and weaknesses of these three methods in practical applications, the heuristic greedy algorithm is ultimately chosen for subsequent experimental applications involving packing constraint conditions. To better align with practical requirements, this study introduces conditions involving weight limits, base area limits, and position constraints in the packing calculation. The experiments involve loading mechanical parts from production into boxes, stacking them onto pallets, and finally loading the pallets and goods into containers. Considering various safety requirements, the experiments are conducted with different individual and combined constraint conditions. The more constraint conditions are added, the more the efficiency of space utilization is reduced.
In this study, we utilized the Python programming language to write code. During the experiments, we employed the Matplotlib toolbox, specifically mplot3d, to visualize the results of the packing computations in three-dimensional graphs for observation purposes. Additionally, the program simultaneously recorded the execution results into a CSV file during the packing computation process. After the computation concluded, the results can be viewed by opening the CSV file in Excel to examine the packing outcome data. Comparing the results obtained by the heuristic greedy algorithm employed in this study with those obtained by the traditional trial-and-error method for solving the three-dimensional bin packing problem, it was found that the heuristic approach saved up to approximately 16.20% of available space. |
| 參考文獻 |
[1] G. Dantzig, R. Fulkerson, and S. Johnson, “Solution of a Large-Scale Traveling-Salesman Problem”, Operations Research, vol. 2, no. 4, pp. 393-410, 1954.
[2] D. S. Johnson, “Fast Algorithms for Bin Packing”, Journal of Computer and System Sciences, vol. 8, issue 3, pp. 272-314, 1974.
[3] S. Martello, D. Vigo, “Exact Solution of the Two-Dimensional Finite Bin Packing Problem”, Management Science, vol. 44, issue 3, pp. 388-399, 1998.
[4] D. Pisinger, “Heuristics for the Container Loading Problem”, European Journal of Operational Research, vol.141, issue 2, pp. 382-392, 2002.
[5] K. Kang, I. Moon, H. Wang, “A Hybrid Genetic Algorithm with a New Packing Strategy for the Three-Dimensional Bin Packing Problem”, Applied Mathematics and Computation, vol. 219, issue 3, pp. 1287-1299, Oct. 2012.
[6] H. Zhao et.al., “Learning Practically Feasible Policies for Online 3D Bin Packing”, Science China Information Sciences, vol. 65, pp. 1-17, 2022.
[7] S. Kirkpatrick et.al., “Optimization by Simulated Annealing”, Science, vol. 220, no. 4598, pp. 671-680, 1983.
[8] M. Dorigo, “Optimization, Learning and Natural Algorithms”, Ph. D. Thesis, Politecnico di Milano, 1992.
[9] F. Glover, ‘‘Future Paths for Integer Programming and Links to Artificial Intelligence’’ Computers & Operations Research, vol. 13, no. 5, pp. 533-549, Jan. 1986.
[10] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, “Introduction to Algorithms (3rd Edition)”, MIT Press, 2009.
[11] J. L. De Castro Silva, N. Y. Soma, and N. Maculan, “A Greedy Search for the Three-Dimensional Bin Packing Problem: The Packing Static Stability Case”, International Transactions in Operational Research, vol. 10, issue 2, pp. 141-153, 2003.
[12] J. Kang, S. Park, “Algorithms for the Variable Sized Bin Packing Problem”, European Journal of Operational Research, vol. 147, issue 2, pp. 365-372, 2003.
[13] R. Tarjan, “Depth-First Search and Linear Graph Algorithms”, SIAM Journal on Computing, vol. 1, no. 2, pp. 146-160, 1972.
[14] G. J. Holzmann, D. A. Peled, and M. Yannakakis, “On Nested Depth First Search”, The Spin Verification System, vol. 32, pp. 81-89, 1996.
[15] A. Lodi, S. Martello, and D. Vigo, “Recent Advances on Two-Dimensional Bin Packing Problems”, Discrete Applied Mathematics, vol. 123, no. 1-3, pp. 379-396, 2002.
[16] M. R. Garey, D. S. Johnson, “Computers and Intractability: A Guide to the Theory of NP-Completeness”, Freeman, 1979.
[17] A. Lodi, S. Martello, and M. Monaci, “Two-Dimensional Packing Problems: A Survey”, European Journal of Operational Research, vol. 141, issue 2, pp.241-252, Sep. 2002.
[18] B. Guo, J. Hu, J. Li, F. Wu, Q. Peng, and Q. Zhang, “Two-Dimensional Irregular Packing Problems: A Review”, Frontiers in Mechanical Engineering, vol. 8, 2022.
[19] H, Kellerer, U. Pferschy, and D. Pisinger, “Knapsack Problems”, Springer, 2004.
[20] ISO 6780:2003, “Flat Pallets for Intercontinental Materials Handling — Principal Dimensions and Tolerances”, 2020,
“https://www.iso.org/standard/30524.html”.
[21] 長榮貨櫃通。收費項目費率表。2023。“https://www.containerlink.com.tw/cl/CLINK_QueryFeeExchange”。
[22] 長榮海運股份有限公司。貨櫃規格明細。
“https://www.evergreen-marine.com/tw/tei1/jsp/TEI1_Containers.jsp#Dry_1”。 |
[Endnote RIS 格式]
[相關文章]
[文章引用]
[完整記錄]
[館藏目錄]
至系統瀏覽論文 (2028-10-20以後開放)
plurk
funp
live
udn
HD
myshare
netvibes
friend
youpush
delicious
baidu
Google bookmarks
del.icio.us
hemidemi
facebook
twitter
google
reddit