二維棧板裝載問題數學模式與演算法之設計與分析

Development of a mathematical model and heuristic algorithms for the two-dimensional pallet loading problem

吳崑誌(Kun-Chih Wu)

指導教授 ： 丁慶榮

元智大學/工程學院/工業工程與管理學系/碩士(2007年)

https://doi.org/10.6838/YZU.2007.00356

摘要

棧板是物料搬運中的重要元件，現今已被廣泛的使用在產品之儲存與運送上。棧板裝載問題(palelt loading problem; PLP)探討如何將物品裝載至棧板上，並使得棧板空間使用率最大，有效的增加棧板的空間使用率可減少儲存空間之浪費並降低運輸成本。本研究主要探討單一物品之二維棧板裝載問題，其目標是將長寬為(a, b)之物品裝載至長寬為(L, W)之棧板內，並使得物品數量最多。由於單一物品之二維棧板裝載問題屬於NP-Hard之問題，文獻中大多是採用區塊概念之啟發式方法來求解，本研究則是採用以四區塊演算法為基礎之模擬退火演算法(Simulated Annealing; SA)來求解此問題。由於四區塊概念為基礎之演算法，並不易求解困難之問題，因此本研究建構一個新的數學模式將問題分成兩個階段來求解，第一個階段係求解棧板裝載問題之最佳擺放量，第二階段則是求解第一階段解之擺放方式，並且以CPLEX求解此數學模式。透過將問題分割成兩階段求解，有效降低問題求解之困難度。求解文獻的標竿測試例題中，除了少部分較困難之例題求得最佳解所需之時間較久之外，大部分例題本數學模式皆可在一百秒內求得最佳解，與其他正確解法相較，本研究所提之模式減少變數數量與限制式數量可以在較短的時間內求得最佳解。

關鍵字

棧板裝載問題 ； 模擬退火演算法 ； 數學規劃 ； 樹搜尋 ； 物流管理

並列摘要

Pallets have become the fundamental component in the world of material handling. The Pallet Loading Problem (PLP) considers packing small boxes onto a pallet and maximizes the space utilization of the pallet. Better utilization of pallets can lead to increasing of storage capacity and material handling throughput. The two-dimensional identical item pallet loading problem is considered in this thesis, the objective is to pack identical small rectangles (a, b) (i.e. the bottom face of boxes) onto a large rectangle (L, W) (i.e. the pallet surface) and maximizing the number of small rectangles placed on the pallet. This problem belongs to NP-Hard, therefore, heuristic algorithms are adopted for solving this problem. Two approaches are proposed in this research. A four-block based simulated annealing (SA) algorithm is first proposed. This algorithm can solve simple instances but cannot obtain optimal solutions for difficult instances. Thus, the second approach, a two-phase algorithm is proposed. In the first phase, a new integer programming model is developed to find the maximum number of boxes that can be placed onto the pallet by CPLEX. The feasible layout for the solution obtained in the first phase is then generated by a tree search algorithm in the second phase. Different sets of instances are treated. The results show that our algorithms can solve the 2-dimentsional pallet loading problem effectively.

並列關鍵字

Pallet Loading Problem ； Simulated Annealing ； Mathematical Model ； Tree Search ； Logistics Management

參考文獻

6. Alvarez-Valdes, R., Parreño, F., J. and Tamarit, M. (2005a), “A GRASP algorithm for constrained two-dimensional non-guillotine cutting problems”, Journal of the Operational Research Society, Vol. 56, pp. 414-425.

7. Alvarez-Valdes, R., Parreño, F., J. and Tamarit, M. (2005b), “A branch-and-cut algorithm for the pallet loading problem”, Computers & Operations Research, Vol. 32, pp. 3007-3029.

8. Alvarez-Valdes, R., Parreno, F. and Tamarit, J. M. (2005c), “A tabu search algorithm for the pallet loading problem”, OR Spectrum, Vol. 27, pp. 43-61.

9. Barnse, F. W. (1979), “Packing the maximum number of mxn tiles in a large pxq rectangle”, Discrete Mathematics, Vol. 26, pp. 93-100.

10. Beasley, J. E. (1985), “An exact two-dimensional non-guillotine cutting tree search procedure”, Operations Research, Vol. 33, pp. 49-64.