近年來隨著資訊科技的發展及電子商務的興起，許多企業為求提升生產及服務效率紛紛投入高效、精準的智慧化物流管理，無人化的倉儲、分揀、配送即為時下相當重要且熱門的投入項目與研究方向。
本研究提出一個新的裝箱問題稱為分割式容量裝箱問題，其應用方向為商品的倉儲與陳列，並以書櫃擺書的範例做為應用實例。啟發式演算法為其他許多演算法的基礎，其易於貼近應用問題的特性適合用於本研究所提出的實例問題。經由透過定義問題特性建構兩項啟發式演算法，其中詳述建構過程與擺放邏輯以增添建構過程的完整性，並於啟發式方法過程加入書本編碼機制以記錄書本擺放位置，使除了倉儲功用更在分揀與配送時增加其應用性。
兩項啟發式分別為書櫃優先擺放法與夾層優先擺放法，並分別考慮書本重量、高度、寬度進行挑選策略的條件以提升求解品質。為驗證兩項啟發式使用績效與隨機亂數不重複搜尋方法相比較求得的最好的解。實驗結果顯示夾層優先擺放啟發式方法之於所有方法所求最好的解有相當好的表現。實驗結果亦可得知啟發式方法相較於搜索方法可以處理與分析更大量的資料。

In recent years, with the development of information technology and the growth of e-commerce, many companies have invested in efficient and accurate intellective logistics management to improve the efficiency of their production and service. These made unmanned warehousing, unmanned selecting and unmanned drone important and popular for people to throw themselves into related research.
This paper proposes a new packing problem called dividable volume packing problem (DVPP) which can be used in the application of storage and display of goods. The DVPP example used in this study is to lay out books into bookshelf for real situation. Heuristic construction is the basis for many other algorithms, and its property of being able to closely mimic actual circumstances and makes it suitable for real-life problems. We first define properties of the problem and use them to construct two heuristic methods. We also define properties of the problem and use them to construct two heuristic methods to make the constructed process more clearly. Further, the book encoding mechanism is added into the heuristic process to record the position of books, giving the heuristic additional functions when operating warehouse work such as sorting and distributing.
Two heuristic methods have been constructed to solve the DVPP example problems. These methods are called Shelf First Locating (SFL), which is based on First-Fit strategy, and Layer First Locating (LFL), which are an extension of SFL. These methods consider the weights, heights and widths of books to improve the quality of solutions. To verify the usage performance of problem solving, a random number non-repetitive search method has been used to compare with the two heuristic methods. The result shows that the LFL heuristic method is the best among these methods for all experiments. The experimental results also show that the heuristic method can process and analyze a large amount of data than the search method.

1. İ. Babaoğlu, “Solving 2D strip packing problem using fruit fly optimization algorithm,” Procedia computer science. Vol. 111, pp. 52-57, 2017.
2. S. Borjian, V.H. Manshadi, C. Barnhart, & P. Jaillet, “Managing relocation and delay in container terminals with flexible service policies,” arXiv preprint arXiv:1503.01535, 2015.
3. M. Buljubašić, & M. Vasquez, “Consistent neighborhood search for one-dimensional bin packing and two-dimensional vector packing,” Computers & Operations Research, Vol. 76, pp. 12-21, 2016.
4. S.G. Christensen, D.M. Rousoe, ”Container loading with multi-drop constraints,” International Transactions in Operational Research Vol. 16, pp. 727–743, 2009.
5. E.G. Coffman, M.R. Garey, and D.S. Johnson,“Approximation algorithms for bin-packing-an updated survey,” Algorithm Design for Computer System Design, Springer Verlag, Wien, Vol. 171, pp. 49–106, 1984.
6. H. Dyckhoff, “A typology of cutting and packing problems,” European Journal of Operational Research Vol. 44, pp. 145–159, 1990.
7. L. Epstein, and V.S. Rob, “Optimal online algorithms for multidimensional packing problems,” SIAM Journal on Computing, Vol. 35, No. 2, pp. 431–448, 2005.
8. E. Falkenauer, “A hybrid grouping genetic algorithm for bin packing”, Journal of Heuristics, Vol. 2, No. 1, pp. 5–30, 1996
9. X. Feng, I. Moon, & J. Shin, “Hybrid genetic algorithms for the three-dimensional multiple container packing problem.” Flexible Services and Manufacturing Journal, Vol. 27, No. 2, pp. 451-477, 2015
10. J. N. D. Gupta, and J.C. Ho, “A new heuristic algorithm for the one-dimensional bin-packing problem,” Production Planning &; Control, Vol. 10, No. 6, pp. 598–603, 1999.
11. D. S. Liu, K. C. Tan, S. Y. Huang, C. K.Goh, & W.K. Ho, “On solving multi-objective bin packing problems using evolutionary particle swarm optimization,” European Journal of Operational Research, Vol. 190, pp. 357-382, 2008.
12. S. Martello, M. Monaci, & D. Vigo, “An exact approach to the strip-packing problem,” INFORMS Journal on Computing, Vol. 15, No.3, pp. 310-319, 2003.
13. S. Martello, and P. Toth, “Knapsack Problems, Algorithms and Computer Implementations,” John Wiley and Sons Ltd: England, 1990.
14. D. Pisinger, , “Heuristics for the container loading problem.” European Journal of Operational Research Vol. 141, pp. 382–392, 2002.
15. H. Shachnai, and T. Tamir, “Polynomial time approximation schemes for class-constrained packing problems,” Journal of Scheduling, Vol. 4, pp. 313–338, 2001.
16. S.M. Soak, S.W. Lee, G.T. Yeo, &M.G. Jeon, “An effective evolutionary algorithm for the multiple container packing problem,” Progress in Natural Science, Vol. 18, pp. 337–344, 2008.
17. A. Steinberg, “A strip-packing algorithm with absolute performance bound 2,” SIAM Journal on Computing, Vol. 26, No. 2, pp. 401-409, 1997.
18. P. Thapatsuwan, P. Pongcharoen, C. Hicks, & W. Chainate, “Development of a stochastic optimisation tool for solving the multiple container packing problems,” International Journal of Production Economics, Vol. 140, No.2, pp. 737-748, 2012.
19. X. Tong, Y. J. Woo, D.W. Jang, & K.H. Kim, “Heuristic rules based on a probabilistic model and a genetic algorithm for relocating inbound containers with uncertain pickup times,” International Journal of Industrial Engineering Theory, Applications and Practice, Vol.22, pp. 93-101, 2015.
20. G. Wäscher, H. Haußner, & H. Schumann, “An improved typology of cutting and packing problems,” European Journal of Operations Research, Vol. 183, pp. 1109–1130, 2007.
21. L. Wei, H. Qin, B. Cheang, & X. Xu, “An efficient intelligent search algorithm for the two‐dimensional rectangular strip packing problem," International Transactions in Operational Research, Vol. 23, No.1-2, pp. 65-92, 2016.
22. L. Wei, T. Tian, W. Zhu, & A. Lim, “A block-based layer building approach for the 2D guillotine strip packing problem,” European Journal of Operational Research, Vol. 239, No.1, pp. 58-69, 2014.
23. L. Wei, Q. Hu, S.C. Leung, & N. Zhang, "An improved skyline based heuristic for the 2D strip packing problem and its efficient implementation." Computers & Operations Research, Vol. 80, pp. 113-127, 2017.
24. E. C. Xavier, F. K. Miyazawa, “A one-dimensional bin packing problem with shelf divisions,” Discrete Applied Mathematics, Vol. 156, pp. 1083-1096, 2008.
25. D. Zhang, Y. Che, F. Ye, Y. W. Si, & S. C. Leung,” A hybrid algorithm based on variable neighborhood for the strip packing problem,” Journal of Combinatorial Optimization, Vol. 32, No.2, pp. 513-530, 2016.
26. 林采端, 分類式裝箱問題之研究, 國立臺灣科技大學資訊管理系研究所博士論文(2014)