三維裝箱問題能有效幫助物流、運輸、製造業等產業管理或解決存貨、運輸、提升空間利用率等問題，在實務上非常有研究意義。本研究探討的問題為三維裝箱問題中的背包裝載問題，問題限制類型為多卸貨點，其實務上之應用為物流配送問題。連鎖門市或宅配的配送方式與一般背包裝載問題不盡相同，主要原因為連鎖門市或宅配在配送時有一定的送貨路程，故有一定的卸貨順序，如果隨意堆疊或未依照順序擺放，將造成卸貨時間增加，且易發生搬動失誤。故本研究考量貨物下方支撐率、運輸穩定性，以及卸貨效率，包含卸貨人員在卸貨時之可行性及方便性，以期達到在不需挪移其他卸貨點的貨物之情形下即可完成卸貨。
過去文獻對三維裝箱中的背包裝載問題，大多採用啟發式演算法來求解，優點是可解決規模較大的問題，缺點則是求出的解不一定為最佳解。本研究針對三維背包裝載問題中之一特殊情況限制－多卸貨點問題，提出一個二元整數規劃模式(全排法)進行求解，期望在一容器空間中，找出最大總利潤的擺放方式，並在問題規模較大導致二元整數規劃模型無法在限定時間內求出最佳解時，採用斜層排列啟發式演算法(斜排法)進行求解，以期提升貨物運輸穩定性，亦更接近總體最佳解的擺貨方式。
本研究先以小問題比較三種演算法－全排法、層排法、斜排法之執行效率及求解品質，發現全排法雖可求得全域最佳解，在問題規模增加時，求解時間遠大於其他兩種方法。在斜排法及層排法比較中可發現，斜排法求解結果更接近全域最佳解，求解時間亦較短。在參數分析中，可以發現不論是當貨物及容器之相對體積增加、箱子種類增加、卸貨點個數減少、箱子數量增加，都會造成執行時間增加，主要原因都是貨物之排列組合方式增加，使迭代運算時間上升。

This study provides a heuristic algorithm based on binary-integer programming (BIP) model for the problem of packing rectangular boxes into a container or truck with multi-drop situations. We assume that the delivery route of the container is already known in advance and the volume of the cargo is less than or equal to the container’s capacity, and the objective is to find an arrangement that maximizes the profit. The arrangement avoids additional handling at each drop-off point by considering the sequence of unloading boxes, as well as ensures that the boxes do not overlap each other and the cargo loading is stable. Generally, we use heuristics algorithms to solve three-dimensional knapsack loading problems. The shortcoming is that it cannot find overall optimal solution. In this study, we proposed a BIP model to deal with small scale problems and a BIP-based heuristics algorithm to solve large scale problems.

Bischoff, E. E., & Ratcliff, M. S. W. (1995). Issues in the development of approaches to container loading. Omega, 23, 377–390.
Bischoff, E.E. (2006). Three-dimensional packing of items with limited load bearing strength. European Journal of Operational Research, 168, 952–966.
Bortfeldt, A., & Gehring, H. (1998). A tabu search algorithm for weakly heterogeneous container loading problems. OR Spectrum, 20(4), 237-250.
Bortfeldt, A., & Gehring, H. (1999). Zur Behandlung von Restriktionen bei der Stauraumoptimierung am Beispiel eines genetischen Algorithmus fürdas Containerbeladeproblem. In: Kopfer, H., Bierwirth, C. (Eds.), Logistik Management – Intelligente I+KTechnologien, Springer, Berlin, 83–100.
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., Gehring, H., & Mack, D. (2003). A parallel tabu search algorithm for solving the container loading problem. Parallel Computing, 29(5), 641-662.
Bortfeldt, A., & Mack, D. (2007). A heuristic for the three dimensional strip packing problem. European Journal of Operational Research, 183(3), 1267-127.
Bortfeldt, A., & Wäscher, G. (2012). Constraints in container loading – A state-of-the-art review. European Journal of Operational Research, 229, 1-20.
Ceschia, S., & Schaerf, A. (2011). Local search for a multi-drop multi-container loading problem. Journal of Heuristics, 19(2), 275-294.
Chen, C.S., Lee, S.M., & Shen, Q.S. (1995). An analytical model for the container loading problem. European Journal of Operational Research 80, 68–76.
de Araujo, O. C. B., & Armentano, V.A. (2007). A multi-start random constructive heuristic for the container loading problem. Pesquisa Operacional, 27, 311–331.
Dereli, Z. T., & Das, G. S. (2010). A hybrid simulated annealing algorithm for solving multi-objective container-loading problems. Applied Artificial Intelligence, 24, 463–486.
Dyckhoff, H., & Finke, U. (1992). Cutting and Packing in Production and Distribution. Physica-Verlag. Heidelberg.
Egeblad, J., Garavelli, C., Lisi, L., & Pisinger, D. (2010). Heuristics for container loading of furniture. European Journal of Operational Research, 200, 881–892.
Eley, M. (2002). Solving container loading problems by block arrangements. European Journal of Operational Research, 141, 393–409.
Falkenauer, E. (1996). A hybrid grouping genetic algorithm for bin packing. J Heuristics, 2(1), 5–30.
Fanslau, T., & Bortfeldt, A. (2010). A tree-search algorithm for solving the container loading problem. INFORMS Journal on Computing, 22, 222–235.
Fuellerer, G., Doerner, K., Hartl, R.F., & Iori, M. (2010). Metaheuristics for vehicle routing problems with three-dimensional loading constraints. European Journal of Operational Research, 201, 751–759.
Gehring, H., & Bortfeldt, A. (1997). A genetic algorithm for solving the container loading problem. International Transactions in Operational Research, 4(5-6), 401-418.
Gendreau, M., Iori, M., Laporte, G., & Martello, S. (2006). A tabu search algorithm for a routing and container loading problem. Transportation Science, 40, 342–350.
Gilmore, P. C., & Gomory, R. E. (1965). Multistage cutting stock problems of two and more dimensions. Operations Research, 13(1), 94−120.
Gonçalves, J. F., & Resende, M. G. C. (2012). A parallel multi-population biased random-key genetic algorithm for a container loading problem. Computers &Operations Research, 39, 179–190.
Hemminki, J., Leipälä,T., & Nevalainen, O. (1998). On-line packing with boxes of different size. International Journal of Production Research, 36, 2225–2245.
Haessler, R.W., & Talbot, F.B. (1990). Load planning for shipments of low density products. European Journal of Operational Research 44, 289–299.
Hodgson, T.J. (1982). Combined approach to the pallet loading problem. IIE Transactions, 14, 175–182.
Jin, Z., Ohno, K., & Du, J. (2004). An efficient approach for the three-dimensional container packing problem with practical constraints. Asia–Pacific Journal of Operational Research, 21, 279–295.
Junqueira, L., Morabito, R., & Yamashita, D. S. (2012a). Three-dimensional container loading models with cargo stability and load bearing constraints. Computers and Operations Research, 31(1), 74–85.
Junqueira, L., Morabito, R., & Yamashita, D. S. (2012b). MIP-based approaches for the container loading problem with multi-drop constraints. Annals of Operations Research, 199, 51–75.
Lai, K. K., Xue, J., & Xu, B. (1998). Container packing in a multi-customer delivering operation. Computers & Industrial Engineering, 35, 323–326.
Li, H. L., & Chang, C. T. (1998). An approximately global optimization method for assortment problems. European Journal of Operational Research, 105(3), 604–612.
Lin, J. L., Foote, B., Pulat, S., & Cheung, J. Y. (1993). Hybrid genetic algorithm for container packing in three dimensions. In: Proceedings of the 9th Conference on AI for Applications, IEEE Computer Society Press, Orlando, Florida, USA, 353–359.
Liu, J., Yue, Y., Dong, Z., Maple, C., & Keech, M. (2011a). A novel hybrid Tabu Search approach the container loading. Computers &Operations Research, 38, 797–807.
Liu, W. Y., Lin, C. C., Yu, C. S. (2011b). On the three-dimensional container packing problem under home delivery service. Asia–Pacific Journal of Operational Research, 1–20.
Liu S., Zhu F. H., Lv Y. S., & Li Y. T. (2015). A Heuristic Orthogonal Binary Tree Search Algorithm for Three Dimensional Container Loading Problem. Chinese journal of computers, 1-19.
Loh, H. T., & Nee, A. Y. C. (1992). A packing algorithm for hexahedral boxes. In Proceedings of the Industrial Automation Conference, 115–126.
Lu Y. P., & Zha J. Z. (2002). Sequence triplet method for 3D rectangle packing problem. Journal of Software, 13(11), 2183−2187.
Mack, D., Bortfeldt, A., & Gehring, H. (2004). A parallel hybrid local search algorithm for the container loading problem. International Transactions in Operational Research, 11, 511–533.
Martello, S., & Toth, P. (1990a). Knapsack problems: algorithms and computer implementations. John Wiley & Sons. New York.
Martello, S., & Toth, P. (1990b). Lower bounds and reduction procedures for the bin packing problem. Discrete Applied Math, 28(1), 59–70.
Moura, A., & Oliveira, J. F. (2005). A GRASP approach to the container-loading problem. IEEE Intelligent Systems, 20(4), 50-57.
Parreno, F., Alvarez-Valdes, 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. (2002). Heuristics for the container loading problem. European Journal of Operational Research, 141, 382–392.
Ren, J., Tian, Y., & Sawaragi, T. (2011). A tree search method for the container loading problem with shipment priority. European Journal of Operational Research, 214,526–535.
Tarantilis, C. D., Zachariadis, E. E., & Kiranoudis, D. T. (2009). A hybrid metaheuristic algorithm for the integrated vehicle routing and three-dimensional container-loading problem. IEEE Transactions on Intelligent Transportation Systems, 10, 255–271.
Techanitisawad, A., & Tangwiwatwong, P. (2004). A GA-based heuristic for the interrelated container selection loading problems. Industrial Engineering and Management Systems, 3, 22–37.
Wäscher G., Haußner H., & Schumann H. (2007). An improved typology of cutting and packing problems. European Journal of Operational Research, 183(3), 1109-1130.