基于混合整數規劃的工廠產品托盤打包及裝箱問題研究

張晶蓉，賀占文，周艷杰，李玉民

自動化與智能化技術

基于混合整數規劃的工廠產品托盤打包及裝箱問題研究

張晶蓉，賀占文，周艷杰*，李玉民

（鄭州大學 管理學院，鄭州 450001）

針對工廠產品的托盤打包及裝箱問題，提出一種優化產品在托盤上的布局以及托盤與產品整體在集裝箱中的布局方法，以最大化集裝箱的空間利用。在滿足現實約束的條件下，以最大化產品裝載體積為目標建立混合整數規劃模型。考慮問題的復雜性，本文將所研究的問題分解為2個子問題，并建立兩階段裝載模型進行求解。第1階段，建立二維集裝箱裝載模型，確定多種托盤類型在集裝箱底面的平面布局；第2階段，建立三維托盤裝載模型，確定產品在托盤上的立體布局。鑒于精確求解該問題耗時較大，本文針對2個子問題設計兩階段啟發式算法求解。為驗證模型及算法的有效性，采用2組不同規模大小的算例進行測試。算例結果表明，在小、大2種規模算例中，裝載率平均差值分別為0和?0.5%，計算時間相差較大，本文提出的模型及算法在合理的時間內獲得了最優解或近似最優解。本研究能夠為工廠產品的托盤打包及裝箱提供快速高效的解決方案。

集裝箱；裝載；托盤打包；工廠產品；混合整數規劃；啟發式算法

隨著工廠倉庫的產品數量及種類的增多，在產品出庫時，托盤可將多種類型產品歸置整理成規格統一且具有一定體積形狀的產品單元，以促進包裝的標準化與模塊化。通過將產品整齊碼放在托盤上、打包再到集裝箱裝箱，提高了整個作業流程的效率。在運輸過程中，帶托盤運輸能有效提高裝卸效率，減少人工裝卸費用，減少貨損，便于產品數量統計及計價，降低運輸過程總時長。但大多工廠在解決產品的托盤打包和裝箱問題時，往往采用基于人工經驗知識的集裝箱裝載和規劃模式，導致集裝箱裝載方案的魯棒性不高，裝載率普遍較低。因此，有必要對產品的托盤打包及裝箱問題進行建模與優化，以提高集裝箱的空間利用率。

產品的托盤打包及裝箱問題包含了集裝箱裝載（Container Loading Problem，CLP）和托盤裝載（Pallet Loading Problem，PLP）2個經典的組合優化問題，其求解難度隨變量增加呈指數級增長，因此該NP-Hard問題難以求解。啟發式算法是求解這類問題的有效方法，近些年來，根據優化目標及約束條件的不同，學者們提出了相應的啟發式算法。

在集裝箱裝載方面，尚正陽等[1]針對一刀切約束下的二維裝箱問題，構建改進優先度算法求解，運行效果較優。Ignacio等[2]設計了集裝箱裝載率及產品價值最大化2個目標函數，利用集束搜索算法求解。劉勝等[3-4]考慮完全支撐及方向等約束條件，將樹搜索的思想應用于三維裝箱。Bayraktar等[5]考慮幾何約束以及不重疊約束，并利用混合人工蜂群算法進行求解。張長勇等[6]考慮產品裝載的順序約束、穩定性約束、不重疊約束等，并利用基于擬人裝載策略的改進遺傳算法求解。王帥等[7]設計基于強化學習的方法訓練所建立的裝箱模型解決機場行李箱的裝箱問題。呂雪菊等[8]考慮了穩定性約束、定向性以及完全切割約束，利用半徑多樣化小生境遺傳算法進行求解。

在托盤裝載方面，PLP按照所裝產品類型相同或不同可分為制造商托盤裝載（Manufacturer's Pallet Loading Problem，MPLP）和分銷商托盤裝載（Distributor's Pallet Loading Problem，DPLP）2種類型。大多學者采用將同質或異質的產品構成層，接著將產品層層堆碼的方法，使托盤數量最小化，此時構成層的過程可轉化為二維托盤裝載[9-10]。在二維托盤裝載方面，Pisinger等[11]考慮幾何約束以及不重疊約束，構建混合整數規劃模型，并介紹幾個新的下限。Cui等[12]考慮方向性約束以及完全切割約束，并利用價值修訂方程修訂生成產品的價值，并利用順序啟發式算法求解。宋衛生等[13]基于4種典型的托盤堆碼方式，以表面利用率最大為目標研究了貨物的裝載優化方式，并給出了最優排列方案。

在引入托盤的集裝箱裝載方面，Liu等[14]研究家具工廠產品的裝載問題，考慮將已裝載產品的托盤裝載到集裝箱后，在剩余空隙中加入未被裝載的產品，從而使集裝箱利用率最大，利用樹搜索算法與貪婪算法實現。Alonso等[15-16]研究卡車車廂結合托盤的裝載問題，該文獻假設已確定好每個產品在托盤上的層布局，將產品及托盤整體裝入車廂；為保證產品在車廂的穩定性，需滿足多個約束條件，利用混合整數規劃模型及貪心隨機自適應搜索算法求解。

綜上所述，目前大多數文獻均是單獨提高集裝箱或托盤的空間利用。雖然有少量文獻研究了引入托盤的集裝箱裝載問題，但該類文獻僅考慮將托盤與產品整體裝入集裝箱或車廂中，未同時考慮產品的托盤打包及裝箱問題，以及未考慮裝載多種托盤類型。本文將產品的托盤打包及裝箱過程進行統籌優化，考慮實際裝載過程中的諸多約束，建立以最大化產品裝載體積為目標的集裝箱-托盤裝載模型。為降低問題的復雜度，將所研究的問題分解為2個子問題，并建立兩階段裝載模型求解。考慮到產品數量較多時模型求解困難的問題，設計兩階段啟發式算法求解。本文采用2種不同規模大小的算例對所提的模型及算法進行測試，驗證模型的正確性和算法的有效性、收斂性及穩定性。

1 問題描述與建模

1.1 問題描述

本文基于以下假設進行研究：工廠有多種產品類型，且每種產品類型數量充足；產品全部為規則的長方體形狀；產品的重量在托盤以及集裝箱承重范圍之內；不考慮產品之間以及產品與托盤之間存在擠壓變形的情況；托盤僅能放置在集裝箱底面，以簡化裝卸流程；每個托盤可裝載多個類型的產品；為保證裝載穩定性，在產品裝載完成之后，允許將托盤固定，并把縫隙填充。

圖1 坐標系以及集裝箱、托盤和產品的尺寸

1.2 符號說明

本文所用的參數和變量說明見表1。

圖2 不重疊約束

表1 參數符號

Tab.1 Parameter symbol

1.3 模型構建

1.3.1 集裝箱-托盤裝載模型

本文參考文獻[7]不重疊約束的建模思路，在、、軸方向上對產品位置關系進行約束。保證任意2個產品及托盤之間不發生重疊，且不能超出集裝箱的尺寸范圍，建立以裝載產品體積之和最大化為目標的集裝箱-托盤裝載模型。在集裝箱裝載過程中同時確定產品在托盤上的布局，以及產品和托盤整體在集裝箱中的位置，其中裝載在集裝箱中的產品只能完全放置在一個托盤中。具體模型如下：

(2)

1.3.2 兩階段裝載模型

由于上述集裝箱-托盤裝載模型復雜度高、難以求解，因此考慮將所研究的問題拆分為二維集裝箱裝載和三維托盤裝載2個子問題，建立兩階段裝載模型對2個子問題分別建模。具體步驟如下所出。

1）第1階段。確定多種類型托盤在集裝箱底面的布局。建立二維集裝箱裝載模型確定托盤在集裝箱底面的布局，即確定裝入集裝箱底面托盤的種類、數量及位置，如圖3所示，這些二維托盤整體形成集合。該模型以裝入集裝箱的托盤表面積最大化為目標函數，考慮托盤裝載時的不重疊約束條件，在、軸方向上約束托盤之間的位置關系。具體的裝載模型如下：

其中，式（25）為目標函數，表示裝入集裝箱的托盤表面積之和最大化；式（26）—式（30）確保托盤之間不發生重疊；式（31）—式（32）確保托盤的尺寸小于集裝箱的尺寸；式（33）—式（35）表示決策變量約束。

(37)

其中，式（36）為目標函數，表示裝進三維托盤集合的產品的體積之和最大化；式（37）—式（43）表示確保產品之間不發生重疊；式（44）表示產品最多只能放進1個托盤中；式（45）—式（47）表示決策變量約束。

1.3.3 兩階段啟發式算法

當產品數量較多時，兩階段裝載模型的第2階段利用三維托盤裝載模型求解較為困難，難以在合理的時間內得到滿意解。目前，已有較多文獻求解該類組合優化問題[17]。考慮到求解的時效性，本文設計兩階段啟發式算法進行求解，在第2階段對三維托盤裝載模型進行優化。算法步驟如下所示。

1）第1階段。調用CPLEX求解器對二維集裝箱裝載模型進行求解，可以在短時間內確定多種托盤類型在集裝箱底面的布局，因此不需要優化。

在確定產品在托盤表面的布局時，將該裝載過程建立二維托盤裝載模型，即在第1階段選定的托盤表面集合和給定的產品底面集合中，計算裝載托盤表面積利用率最大的產品集合。該模型以裝載產品的表面積最大化為目標函數，考慮產品之間的不重疊約束條件，在、軸方向上約束產品之間的位置關系，具體的模型如下所示：

其中，式（48）為目標函數，表示裝進若干個托盤的產品底面積最大化；式（49）—式（53）確保產品之間不發生重疊；式（54）表示產品最多只能放進一個托盤中；式（55）—式（57）表示決策變量約束。

2 實驗方案

本文選取鄭州市某食品加工廠為研究對象，以該工廠的產品托盤打包及裝箱問題為例，根據實地調研資料，設置2組規模大小的算例數據，以驗證模型的正確性及算法的有效性與尋優性。

圖3 啟發式三維托盤裝載示意圖

本文利用Matlab完成數據的輸入輸出處理，并利用IBM ILOG CPLEX12.8對建立的模型進行求解。實驗程序運行在Intel(R) Core(TM) i7-7500U CPU@2.70 GHz 2.90 GHz處理器上，運行環境為Windows 10企業版。

2.1 實驗參數設置

本文設置2種規模大小的算例數據，小規模算例有6種產品類型，大規模算例有12種產品類型，各設置5組實驗，每組實驗由10個算例構成。在2組算例中，根據實地調研資料，將產品數據利用Matlab中的（）函數在區間范圍內隨機生成，托盤選自該食品加工廠使用的托盤類型，集裝箱尺寸為標準20英尺（1英尺=0.304 8米）。算例的具體數據來源及范圍如表2所示。

2.2 小規模算例

式中：=1, 2。

表2 測試算例參數

Tab.2 Parameters of experimental case

表3 小規模算例數據對比

Tab.3 Comparison of small-scale experimental case data

表3列出了集裝箱-托盤裝載模型、兩階段裝載模型對5組小規模算例進行計算的結果（裝載率和運行時間）。從裝載率角度來看，集裝箱-托盤裝載模型與兩階段裝載模型在一定時間內實現了精確求解，獲得了最優解，1均為0，驗證了2個模型的正確性及有效性。

將2個模型對5組小規模算例的平均運行時間繪制成折線圖，如圖4所示。由圖4可知，兩階段裝載模型的折線斜率相對變化幅度不大，魯棒性相對較好，且對5組算例的平均運行時間相對較少，總平均運行時間僅為109.41 s，而集裝箱-托盤裝載模型的平均運行時間為473.87 s。可以看出相較于集裝箱-托盤裝載模型，兩階段裝載模型在較短時間內獲得了最優解，收斂性好。究其原因，兩階段裝載模型在第1階段中確定了托盤裝載數量，減少了第2階段解的搜索空間，從而收斂性相對較好，提高了求解速度，減少了運行時間。

圖4 5組小規模算例的平均運行時間折線圖

2.3 大規模算例

表4 大規模算例數據對比

Tab.4 Comparison of large-scale experimental case data

對表4中5組實驗的2值按照升序排列，如圖5所示。由圖5可知，在5組實驗中，折線圖的上下界為[?5%，5%]，斜率增長速度相對較小，說明該算法求解的裝載率與下界值相差不大，魯棒性強。全部實驗中，2最大值為3.72%，最小值為?4.18%，平均值為?0.5%，說明兩階段啟發式算法的裝載率與下界值相差不大。在保證了產品裝載垛形穩定的約束條件下，兩階段啟發式算法獲得了理想的裝載方案。

圖5 5組大規模算例實驗的G2值折線圖

從運行時間來看，兩階段裝載模型的平均運行時間為3 636.02 s，而兩階段啟發式算法的平均運行時間僅為1.82 s，運行時間差距相對較大，在較短的時間內便獲得了理想的裝載方案。究其原因，該算法在第2階段將三維托盤裝載問題轉化為二維托盤裝載問題，極大地縮小了解的搜索空間，在頂部剩余空間中按照體積大小順序裝入產品，提高了裝載率，收斂性好；且在50個算例實驗中，兩階段啟發式算法的運行時間標準差為2.14，平均標準差僅為1.17，說明算法的穩定性較好。

從以上分析結果可以看出，在大規模算例實驗中，兩階段啟發式算法所產生的產品裝載方案既保證了產品裝載的垛型穩定，又具有高的空間利用率，避免產生浪費；兩階段啟發式算法能在較短的時間內得到好的裝載方案，魯棒性強，實用性好，能為工廠產品的托盤打包及裝箱提供參考。

3 結語

將工廠產品的托盤打包及裝箱問題進行統籌優化，建立了以產品裝載體積最大化為目標的集裝箱-托盤裝載模型，并將該問題分解為二維集裝箱裝載和三維托盤裝載2個子問題，針對2個子問題建立了兩階段裝載模型進行求解。當產品數量過多導致模型難以求解時，建立兩階段啟發式算法求解。采用2種規模大小的算例對模型和算法進行了測試，驗證了模型及算法的有效性。本文的研究能夠為工廠產品的托盤打包及裝箱問題提供滿意的解決方案，從而減少空間浪費，提高經濟效益。但本文所提的模型及算法還有一些不足之處，隨著產品數量的增加，模型及算法復雜度更高，計算時間更長等；本文只考慮在集裝箱底部裝載托盤，未考慮托盤承重問題。因此，將來的工作需進一步優化算法，提高計算速度，同時將考慮更多的實際應用場景和約束條件，以提出更好、更適用的解決方案。

[1] 尚正陽, 黃秋妍, 康正陽, 等. 一刀切約束下的二維裝箱問題高效求解算法[J]. 包裝工程, 2021, 42(7): 231-238.

SHANG Zheng-yang, HUANG Qiu-yan, KANG Zheng-yang, et al. Efficient Heuristic Algorithm for the Two-Dimensional Guillotine Rectangular Bin Packing Problem[J]. Packaging Engineering, 2021, 42(7): 231-238.

[2] ARAYA I, MOYANO M, SANCHEZ C. A Beam Search Algorithm for the Biobjective Container Loading Problem[J]. European Journal of Operational Research, 2020, 286(2): 417-431.

[3] 劉勝, 沈大勇, 商秀芹, 等. 求解三維裝箱問題的多層樹搜索算法[J]. 自動化學報, 2020, 46(6): 1178-1187.

LIU Sheng, SHEN Da-yong, SHANG Xiu-qin, et al. A Multi-Level Tree Search Algorithm for Three Dimensional Container Loading Problem[J]. Acta Automatica Sinica, 2020, 46(6): 1178-1187.

[4] 劉勝, 朱鳳華, 呂宜生, 等. 求解三維裝箱問題的啟發式正交二叉樹搜索算法[J]. 計算機學報, 2015, 38(8): 1530-1543.

LIU Sheng, ZHU Feng-hua, LYU Yi-sheng, et al. A Heuristic Orthogonal Binary Tree Search Algorithm for Three Dimensional Container Loading Problem[J]. Chinese Journal of Computers, 2015, 38(8): 1530-1543.

[5] BAYRAKTAR T, ERS?Z F, KUBAT C. Effects of Memory and Genetic Operators on Artificial Bee Colony Algorithm for Single Container Loading Problem[J]. Applied Soft Computing Journal, 2021, 108: 107462.

[6] 張長勇, 翟一鳴. 基于改進遺傳算法的航空集裝箱裝載問題研究[J]. 北京航空航天大學學報, 2021, 47(7): 1345-1352.

ZHANG Chang-yong, ZHAI Yi-ming. Air Container Loading Based on Improved Genetic Algorithm[J]. Journal of Beijing University of Aeronautics and Astronautics, 2021, 47(7): 1345-1352.

[7] 王帥, 洪振宇. 基于強化學習的機場行李裝箱優化方法[J]. 包裝工程, 2022, 43(3): 257-263.

WANG Shuai, HONG Zhen-yu. Optimization Method of Baggage Packing in Airport Based on Reinforcement Learning[J]. Packaging Engineering, 2022, 43(3): 257-263.

[8] 呂雪菊, 倪靜. 基于自適應空間劃分策略的三維裝箱問題[J]. 系統工程, 2020, 38(4): 95-102.

LYU Xue-ju, NI Jing. Three Dimensional Container Loading Problem Based on Adaptive Spatial Partition Strategy[J]. Systems Engineering, 2020, 38(4): 95-102.

[9] ALJUHANI D, PAPAGEORGIOU L. Improved Layout Structure with Complexity Measures for the Manufacturer's Pallet Loading Problem (MPLP) Using a Block Approach[J]. Journal of Industrial Engineering and Management, 2021, 14(2): 231-249.

[10] DELL'AMICO M, MAGNANI M. Solving a Real-Life Distributor's Pallet Loading Problem[J]. Mathematical and Computational Applications, 2021, 26(3): 53-63.

[11] PISINGER D, SIGURD M. The Two-Dimensional Bin Packing Problem with Variable Bin Sizes and Costs[J]. Discrete Optimization, 2005, 2(2): 154-167.

[12] CUI Y P, CUI Y D, TANG T B. Sequential Heuristic for the Two-Dimensional Bin-Packing Problem[J]. European Journal of Operational Research, 2015, 240(1): 43-53.

[13] 宋衛生, 薛陽. 托盤裝載優化設計系統的開發[J]. 包裝工程, 2021, 42(13): 205-211.

SONG Wei-sheng, XUE Yang. Development of Pallet Loading Optimization Design System[J]. Packaging Engineering, 2021, 42(13): 205-211.

[14] SHENG Liu, ZHAO Hong-xia, DONG Xi-song, et al. A Heuristic Algorithm for Container Loading of Pallets with Infill Boxes[J]. European Journal of Operational Research, 2016, 252(3): 728-736.

[15] ALONSO M T, ALVAREZ-VALDES R, PARRE?O F. A GRASP Algorithm for Multi Container Loading Problems with Practical Constraints[J]. 4OR, 2020, 18(4): 49-72.

[16] ALONSO M T, ALVAREZ-VALDES R, IORI M, et al. Mathematical Models for Multi Container Loading Problems with Practical Constraints[J]. Computers & Industrial Engineering, 2018, 127: 722-733.

[17] SHI Yong, ZHOU Yan-jie, BOUDOUH T, et al. A Lexicographic-Based Two-Stage Algorithm for Vehicle Routing Problem with Simultaneous Pickup-Delivery and Time Window[J]. Engineering Applications of Artificial Intelligence, 2020, 95(2): 103901.

Pallet Packing and Container Loading of Factory Products Based on Mixed Integer Programming Approach

ZHANG Jing-rong, HE Zhan-wen, ZHOU Yan-jie*, LI Yu-min

(School of Management, Zhengzhou University, Zhengzhou 450001, China)

The work aims to propose a method to optimize the layout of products on pallets and the layout of pallets and products in containers to maximize container space utilization, thus solving the problem in pallet packing and container loading of factory products. A mixed integer programming model was developed to optimize the volume of the loaded product under realistic constraints. Due to the complexity of the problem, the studied problem was divided into two sub-problems and a two-stage loading model was established for solution. In the first stage, a two-dimensional container loading model was established to determine the plane layout of pallets on the bottom of containers. In the second stage, a three-dimensional pallet loading model was established to determine the 3D layout of products on the pallet. In view of that accurate solution was time-consuming, a two-stage heuristic algorithm was designed to solve the two sub-problems. To verify the effectiveness of the model and algorithm, two groups of examples with different sizes were adopted. The results showed that the average difference of loading rate was 0 and ?0.5% in small and large-scale experimental cases, respectively, but the calculation time was quite different. The model and algorithm proposed could obtain the optimal solution or approximate optimal solution in a reasonable time. This study can provide a fast and efficient solution for pallet packing and container loading of factory products.

container; loading; pallet packing;factory products; mixed integer programming; heuristic algorithm

U294.3

A

1001-3563(2023)17-0143-09

10.19554/j.cnki.1001-3563.2023.17.017

2022-12-02

國家自然科學基金資助項目（72201252）；河南省社科規劃決策咨詢項目（2022JC10）；河南省高校智庫研究項目（2023ZKYJ21）

責任編輯：曾鈺嬋