在過去幾十年中，裝箱問題(Bin Packing Problem, BPP）已廣泛被應用於工業生產製造、物流配送、資源配置等產業。為降低成本，三維裝箱問題的目標大多以最大化每個箱子的填充率、最小化使用的箱子數量、最小化使用的高度為主。儘管已有許多學者投入裝箱問題之研究，但尚未有研究以最小化高度為三維裝箱問題之目標，同時將穩定度與重量分布納入考量。因此，本研究首先以混合整數規劃(Mixed Integer Programming)描述問題，其次，由於裝箱問題已證明為NP-hard問題，當資料量大時無法求得最佳解，僅可求得近似解。故本研究使用廣泛應用在解決裝箱問題的基因演算法來求解，實驗結果證實本研究實作的基因演算法在內容物件數量小時可取得最佳解，當物件數量增加時仍可在合理的時間範圍內可獲得良好的近似解。因此，在實務上，本研究實作之基因演算法能有效的降低整體高度並提高其填充率及穩定性。

In the last decades, Bin Packing Problem (BPP) has been widely used in industrial manufacturing, logistics distribution, resource allocation, and other industries. In order to reduce costs, most of the objectives of the three-dimensional packing problem are to maximize the filling rate of each box, minimize the number of boxes used, or minimize the height of use. Although many scholars have been studying packing problem, no research has been done to minimize the height of the three-dimensional bin packing problem, while considering both stability and weight distribution. Therefore, this paper first describes the problem by Mixed-integer programming. Secondly, since the packing problem has been proved to be an NP-hard problem, and when the amount of data is large, only the approximate solution can be obtained and the optimal solution cannot be obtained. Therefore, this study uses a Genetic algorithm that is widely used to solve the Bin Packing Problem. The experimental results confirm that the Genetic algorithm implemented in this study can obtain the best solution when the number of contents is small. As the number of contents increases, it can still obtain a good approximate solution within a reasonable time frame. So, in practice, the Genetic algorithm implemented in this study can effectively reduce the overall height and improve its filling rate and stability.

第一章 緒論 1
第一節 研究背景與動機 1
第二節 研究目的 3
第三節 研究流程 4
第二章 文獻探討 6
第一節 裝箱問題 6
第二節 基因演算法 10
第三節 啟發式演算法及裝箱問題 15
第三章 研究方法 17
第一節 符號定義 17
第二節 問題定義 18
第三節 基因演算法設計 20
第四節 貪婪演算法設計 24
第四章 實驗與分析 25
第一節 實驗設計 25
第二節 實驗結果 26
第五章 結論 30
參考文獻 31

Allen, S. D., Burke, E. K., & Mareček, J. (2012). A space-indexed formulation of packing boxes into a larger box. Operations Research Letters, 40(1), 20-24.
Anderson-Cook, C. M. (2005). Practical genetic algorithms. In: Taylor & Francis.
Beasley, J. E. (1985). An algorithm for the two-dimensional assortment problem. European Journal of Operational Research, 19(2), 253-261.
Bischoff, E. E. (2006). Three-dimensional packing of items with limited load bearing strength. European Journal of Operational Research, 168(3), 952-966.
Bortfeldt, A., & Gehring, H. (1998). Applying tabu search to container loading problems. In Operations Research Proceedings 1997 (pp. 533-538). Springer, Berlin, Heidelberg.
Bortfeldt, A., & Gehring, H. (2001). A hybrid genetic algorithm for the container loading problem. European Journal of Operational Research, 131(1), 143-161.
Bortfeldt, A., & Wäscher, G. (2013). Constraints in container loading–A state-of-the-art review. European Journal of Operational Research, 229(1), 1-20.
Chen, C. S., Lee, S. M., & Shen, Q. S. (1995). An analytical model for the container loading problem. European Journal of Operational Research, 80(1), 68-76.
Crainic, T. G., Perboli, G., & Tadei, R. (2009). TS2PACK: A two-level tabu search for the three-dimensional bin packing problem. European Journal of Operational Research, 195(3), 744-760.
Crainic, T. G., Perboli, G., & Tadei, R. (2008). Extreme point-based heuristics for three-dimensional bin packing. Informs Journal on computing, 20(3), 368-384.
Dereli, T., & Das, G. S. (2011). A hybrid ‘bee (s) algorithm’for solving container loading problems. Applied Soft Computing, 11(2), 2854-2862.
Elhedhli, S., Gzara, F., & Yan, Y. F. (2017). A MIP-based slicing heuristic for three-dimensional bin packing. Optimization Letters, 11(8), 1547-1563.
Faina, L. (2000). A global optimization algorithm for the three-dimensional packing problem. European Journal of Operational Research, 126(2), 340-354.
Falkenauer, E. (1996). A hybrid grouping genetic algorithm for bin packing. Journal of heuristics, 2(1), 5-30.
Friesen, D. K., & Langston, M. A. (1986). Variable sized bin packing. SIAM journal on computing, 15(1), 222-230.
Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: a guide to NP-completeness. In: WH Freeman and Company, San Francisco.
Gehring, H. (1997). A genetic algorithm for solving the container loading problem. International transactions in operational research, 4(5-6), 401-418.
Gilmore, P. C., & Gomory, R. E. (1965). Multistage cutting stock problems of two and more dimensions. Operations research, 13(1), 94-120.
Gilmore, P. C., & Gomory, R. E. (1961). A linear programming approach to the cutting-stock problem. Operations research, 9(6), 849-859.
Goldberg, D. E. (1985). Computer-Aided Gas Pipeline Operation Using Genetic Algorithms And Rule Learning Part I: Genetic Algorithms In Pipeline Optimization. In (pp. 32): Society of Petroleum Engineers.
Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning, Addison Wesley, Reading, MA. SUMMARY THE APPLICATIONS OF GA-GENETIC ALGORITHM FOR DEALING WITH SOME OPTIMAL CALCULATIONS IN ECONOMICS.He, K., Huang, W. J. C., & Engineering, I. (2010). A caving degree based flake arrangement approach for the container loading problem. 59(2), 344-351.
Hifi, M., Negre, S., & Wu, L. (2014). Hybrid greedy heuristics based on linear programming for the three‐dimensional single bin‐size bin packing problem. International Transactions in Operational Research, 21(1), 59-79.
Holland, J. H. (1992). Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. MIT press.
Huang, W., & He, K. (2009). A new heuristic algorithm for cuboids packing with no orientation constraints. Computers & Operations Research, 36(2), 425-432.
Junqueira, L., Morabito, R., & Yamashita, D. S. (2012). MIP-based approaches for the container loading problem with multi-drop constraints. Annals of Operations Research, 199(1), 51-75.
Li, H. L., & Chang, C. T. (1998). An approximately global optimization method for assortment problems. European Journal of Operational Research, 105(3), 604-612.
Lodi, A., Martello, S., & Monaci, M. (2002). Two-dimensional packing problems: A survey. European journal of operational research, 141(2), 241-252.
Lodi, A., Martello, S., & Vigo, D. (2002). Heuristic algorithms for the three-dimensional bin packing problem. European Journal of Operational Research, 141(2), 410-420.
Lodi, A., Martello, S., & Vigo, D. (1999). Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems. INFORMS Journal on Computing, 11(4), 345-357.
Martello, S., Pisinger, D., & Vigo, D. (2000). The three-dimensional bin packing problem. Operations research, 48(2), 256-267.
Michalewicz, Z., Janikow, C. Z., & Krawczyk, J. B. (1992). A modified genetic algorithm for optimal control problems. Computers & Mathematics with Applications, 23(12), 83-94.
Mohanty, B. B., Mathur, K., & Ivancic, N. J. (1994). Value considerations in three-dimensional packing—A heuristic procedure using the fractional knapsack problem. European Journal of Operational Research, 74(1), 143-151.
Paquay, C., Schyns, M., & Limbourg, S. (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(1-2), 187-213.
Parreño, F., Alvarez-Valdés, R., Oliveira, J. F., & Tamarit, J. M. (2010). Neighborhood structures for the container loading problem: a VNS implementation. Journal of Heuristics, 16(1), 1-22.
Parreño, F., Alvarez-Valdés, R., Tamarit, J. M., & Oliveira, J. F. (2008). A maximal-space algorithm for the container loading problem. INFORMS Journal on Computing, 20(3), 412-422.
Pisinger, D., & Sigurd, M. (2005). The two-dimensional bin packing problem with variable bin sizes and costs. Discrete Optimization, 2(2), 154-167.
Pisinger, D. (2002). Heuristics for the container loading problem. European journal of operational research, 141(2), 382-392.
Tao, Y., & Wang, F. (2015). An effective tabu search approach with improved loading algorithms for the 3L-CVRP. Computers & Operations Research, 55, 127-140.
Wu, Y., Li, W., Goh, M., & de Souza, R. (2010). Three-dimensional bin packing problem with variable bin height. European journal of operational research, 202(2), 347-355.
Xiang, X., Yu, C., Xu, H., & Zhu, S. X. (2018). Optimization of Heterogeneous Container Loading Problem with Adaptive Genetic Algorithm. Complexity, 2018.
Yan, Y. F. (2015). Three-Dimensional Bin Packing in Mixed-case Palletization (Master's thesis, University of Waterloo).
Zhu, W., Huang, W., & Lim, A. (2012). A prototype column generation strategy for the multiple container loading problem. European Journal of Operational Research, 223(1), 27-39.
莊雅筑. (2017). 裝箱問題於商品組合之應用. 臺中科技大學流通管理系碩士班學位論文, 1-56.