優化訂單履行流程對物流業至關重要。在包裝過程中用智慧方法代替人工基於經驗判斷的作業方式，不僅可以提高工作效率，還可以消除投入資源的浪費。在這項研究中，我們聚焦於考量互斥商品類別的三維多尺寸箱型裝箱問題 (Three-dimensional multiple bin-size bin packing problem with compatible categories, 3D-MBSBPPCC)，其中用於包裝商品的箱子具有不同的尺寸，且只有屬於相容商品類別的商品才能包裝在同一個箱子中。在考量特定的限制條件下，本研究旨在開發啟發式演算法來找出最佳的商品裝箱方案，藉此更有效地利用投入資源，並提升包裝的效率和安全性。
以最小化所需箱數和最小化箱子總浪費空間為目標，我們首先使用降序首次適應演算法尋找初始解。接著應用配箱演算法執行包裝作業和評估解決方案。然後採用以模擬退火為基底的演算法，通過在子集合之間移動商品來改善解決方案。最後提出基於模擬退火演算法和基因演算法的混合啟發式演算法改善求解品質。我們使用實際的例子進行測試。測試結果顯示，所提出的演算法可以有效地解決該問題。

Optimizing the order fulfillment process is crucial to the logistics industry. Replacing experience-based judgment with intelligent methods in the packing process not only improves work efficiency but also eliminates resource wastage. In this study, we focus on the three-dimensional multiple bin-size bin packing problem with compatible categories (3D-MBSBPPCC), where different box types are used to pack the products and only products from compatible categories can be packed in the same box. By considering specific constraints, this study aims at developing an algorithm to find the best packing pattern, which can make better use of resources, and improve packaging efficiency and security.
With the goal of minimizing the number of boxes required and minimizing the total unused space in the boxes, we first use the first-fit decreasing algorithm to find an initial solution. Next, the carton configuration algorithm is applied to perform packing and evaluate the solution. Then, a simulated annealing (SA)-based algorithm is employed to improve the solution by moving the products among the subsets of the solution. Finally, hybrid metaheuristics, based on both SA and the genetic algorithm, are proposed to improve the solution quality. We test our proposed packing algorithms on real-world instances. The experimental results demonstrate that the proposed algorithms are effective in solving the 3D-MBSBPPCC.

Alvarez-Valdés, Ramón, Francisco Parreño, and José Manuel Tamarit. 2013. 'A GRASP/Path relinking algorithm for two-and three-dimensional multiple bin-size bin packing problems', Computers Operations Research, 40: 3081-90.
Bortfeldt, A., H. Gehring, and D. Mack. 2003. 'A parallel tabu search algorithm for solving the container loading problem', Parallel Computing, 29: 641-62.
Bortfeldt, Andreas, and Gerhard Wäscher. 2013. 'Constraints in container loading – A state-of-the-art review', European Journal of Operational Research, 229: 1-20.
Chen, CS, Shen-Ming Lee, and QS Shen. 1995. 'An analytical model for the container loading problem', European Journal of Operational Research, 80: 68-76.
Ekici, Ali. 2022. 'Variable-sized bin packing problem with conflicts and item fragmentation', Computers & Industrial Engineering, 163: 107844.
Eley, Michael. 2003. 'A bottleneck assignment approach to the multiple container loading problem', OR Spectrum, 25: 45-60.
Gajda, Mikele, Alessio Trivella, Renata Mansini, and David Pisinger. 2022. 'An optimization approach for a complex real-life container loading problem', Omega, 107.
Galinier, Philippe, and Jin-Kao Hao. 1999. 'Hybrid evolutionary algorithms for graph coloring', Journal of combinatorial optimization, 3: 379-97.
Huang, Yao-Huei, F. J. Hwang, and Hao-Chun Lu. 2016. 'An effective placement method for the single container loading problem', Computers & Industrial Engineering, 97: 212-21.
Kang, Jangha, and Sungsoo Park. 2003. 'Algorithms for the variable sized bin packing problem', European Journal of Operational Research, 147: 365-72.
Li, Tzuu-Hseng S., Chih-Yin Liu, Ping-Huan Kuo, Nien-Chu Fang, Cheng-Hui Li, Ching-Wen Cheng, Cheng-Ying Hsieh, Li-Fan Wu, Jie-Jhong Liang, and Chih-Yen Chen. 2017. 'A Three-Dimensional Adaptive PSO-Based Packing Algorithm for an IoT-Based Automated e-Fulfillment Packaging System', IEEE Access, 5: 9188-205.
Li, Xueping, Zhaoxia Zhao, and Kaike Zhang. 2014. "A genetic algorithm for the three-dimensional bin packing problem with heterogeneous bins." In IIE Annual Conference. Proceedings, 2039. Institute of Industrial and Systems Engineers (IISE).
Li, Ying, Mingzhou Chen, and Jiazhen Huo. 2022. 'A hybrid adaptive large neighborhood search algorithm for the large-scale heterogeneous container loading problem', Expert Systems with Applications, 189: 115909.
Martello, Silvano, David Pisinger, and Daniele Vigo. 2000. 'The Three-Dimensional Bin Packing Problem', Operations research, 48: 256-67.
Muritiba, Albert E Fernandes, Manuel Iori, Enrico Malaguti, and Paolo Toth. 2010. 'Algorithms for the bin packing problem with conflicts', INFORMS Journal on Computing, 22: 401-15.
Paquay, Célia, Michael Schyns, and Sabine Limbourg. 2016. 'A mixed integer programming formulation for the three‐dimensional bin packing problem deriving from an air cargo application', International Transactions in Operational Research, 23: 187-213.
Santos, Luiz F. O. Moura, Renan Sallai Iwayama, Luísa Brandão Cavalcanti, Leandro Maciel Turi, Fabio Emanuel de Souza Morais, Gabriel Mormilho, and Claudio B. Cunha. 2019. 'A variable neighborhood search algorithm for the bin packing problem with compatible categories', Expert Systems with Applications, 124: 209-25.
Truong, Cong-Tan-Trinh, Lionel Amodeo, and Farouk Yalaoui. 2020. "A mathematical model for three-dimensional open dimension packing problem with product stability constraints." In International Conference on Optimization and Learning, 241-54. Springer.
Wu, Y., W. K. Li, M. Goh, and R. de Souza. 2010. 'Three-dimensional bin packing problem with variable bin height', European Journal of operational research, 202: 347-55.
Zhang, De-Fu, Yu Peng, Wen-Xing Zhu, and Huo-Wang Chen. 2009. 'A hybrid simulated annealing algorithm for the three-dimensional packing problem', Chinese Journal of Computers, 32: 2147-56.
Zheng, Jia-Nian, Chen-Fu Chien, and Mitsuo Gen. 2015. 'Multi-objective multi-population biased random-key genetic algorithm for the 3-D container loading problem', Computers & Industrial Engineering, 89: 80-87.