基于混合整數(shù)規(guī)劃的工廠產(chǎn)品托盤打包及裝箱問(wèn)題研究

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

自動(dòng)化與智能化技術(shù)

基于混合整數(shù)規(guī)劃的工廠產(chǎn)品托盤打包及裝箱問(wèn)題研究

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

（鄭州大學(xué) 管理學(xué)院，鄭州 450001）

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

集裝箱；裝載；托盤打包；工廠產(chǎn)品；混合整數(shù)規(guī)劃；啟發(fā)式算法

隨著工廠倉(cāng)庫(kù)的產(chǎn)品數(shù)量及種類的增多，在產(chǎn)品出庫(kù)時(shí)，托盤可將多種類型產(chǎn)品歸置整理成規(guī)格統(tǒng)一且具有一定體積形狀的產(chǎn)品單元，以促進(jìn)包裝的標(biāo)準(zhǔn)化與模塊化。通過(guò)將產(chǎn)品整齊碼放在托盤上、打包再到集裝箱裝箱，提高了整個(gè)作業(yè)流程的效率。在運(yùn)輸過(guò)程中，帶托盤運(yùn)輸能有效提高裝卸效率，減少人工裝卸費(fèi)用，減少貨損，便于產(chǎn)品數(shù)量統(tǒng)計(jì)及計(jì)價(jià)，降低運(yùn)輸過(guò)程總時(shí)長(zhǎng)。但大多工廠在解決產(chǎn)品的托盤打包和裝箱問(wèn)題時(shí)，往往采用基于人工經(jīng)驗(yàn)知識(shí)的集裝箱裝載和規(guī)劃模式，導(dǎo)致集裝箱裝載方案的魯棒性不高，裝載率普遍較低。因此，有必要對(duì)產(chǎn)品的托盤打包及裝箱問(wèn)題進(jìn)行建模與優(yōu)化，以提高集裝箱的空間利用率。

產(chǎn)品的托盤打包及裝箱問(wèn)題包含了集裝箱裝載（Container Loading Problem，CLP）和托盤裝載（Pallet Loading Problem，PLP）2個(gè)經(jīng)典的組合優(yōu)化問(wèn)題，其求解難度隨變量增加呈指數(shù)級(jí)增長(zhǎng)，因此該NP-Hard問(wèn)題難以求解。啟發(fā)式算法是求解這類問(wèn)題的有效方法，近些年來(lái)，根據(jù)優(yōu)化目標(biāo)及約束條件的不同，學(xué)者們提出了相應(yīng)的啟發(fā)式算法。

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

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

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

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

1 問(wèn)題描述與建模

1.1 問(wèn)題描述

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

圖1 坐標(biāo)系以及集裝箱、托盤和產(chǎn)品的尺寸

1.2 符號(hào)說(shuō)明

本文所用的參數(shù)和變量說(shuō)明見(jiàn)表1。

圖2 不重疊約束

表1 參數(shù)符號(hào)

Tab.1 Parameter symbol

1.3 模型構(gòu)建

1.3.1 集裝箱-托盤裝載模型

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

(2)

1.3.2 兩階段裝載模型

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

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

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

(37)

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

1.3.3 兩階段啟發(fā)式算法

當(dāng)產(chǎn)品數(shù)量較多時(shí)，兩階段裝載模型的第2階段利用三維托盤裝載模型求解較為困難，難以在合理的時(shí)間內(nèi)得到滿意解。目前，已有較多文獻(xiàn)求解該類組合優(yōu)化問(wèn)題[17]?？紤]到求解的時(shí)效性，本文設(shè)計(jì)兩階段啟發(fā)式算法進(jìn)行求解，在第2階段對(duì)三維托盤裝載模型進(jìn)行優(yōu)化。算法步驟如下所示。

1）第1階段。調(diào)用CPLEX求解器對(duì)二維集裝箱裝載模型進(jìn)行求解，可以在短時(shí)間內(nèi)確定多種托盤類型在集裝箱底面的布局，因此不需要優(yōu)化。

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

其中，式（48）為目標(biāo)函數(shù)，表示裝進(jìn)若干個(gè)托盤的產(chǎn)品底面積最大化；式（49）—式（53）確保產(chǎn)品之間不發(fā)生重疊；式（54）表示產(chǎn)品最多只能放進(jìn)一個(gè)托盤中；式（55）—式（57）表示決策變量約束。

2 實(shí)驗(yàn)方案

本文選取鄭州市某食品加工廠為研究對(duì)象，以該工廠的產(chǎn)品托盤打包及裝箱問(wèn)題為例，根據(jù)實(shí)地調(diào)研資料，設(shè)置2組規(guī)模大小的算例數(shù)據(jù)，以驗(yàn)證模型的正確性及算法的有效性與尋優(yōu)性。

圖3 啟發(fā)式三維托盤裝載示意圖

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

2.1 實(shí)驗(yàn)參數(shù)設(shè)置

本文設(shè)置2種規(guī)模大小的算例數(shù)據(jù)，小規(guī)模算例有6種產(chǎn)品類型，大規(guī)模算例有12種產(chǎn)品類型，各設(shè)置5組實(shí)驗(yàn)，每組實(shí)驗(yàn)由10個(gè)算例構(gòu)成。在2組算例中，根據(jù)實(shí)地調(diào)研資料，將產(chǎn)品數(shù)據(jù)利用Matlab中的（）函數(shù)在區(qū)間范圍內(nèi)隨機(jī)生成，托盤選自該食品加工廠使用的托盤類型，集裝箱尺寸為標(biāo)準(zhǔn)20英尺（1英尺=0.304 8米）。算例的具體數(shù)據(jù)來(lái)源及范圍如表2所示。

2.2 小規(guī)模算例

式中：=1, 2。

表2 測(cè)試算例參數(shù)

Tab.2 Parameters of experimental case

表3 小規(guī)模算例數(shù)據(jù)對(duì)比

Tab.3 Comparison of small-scale experimental case data

表3列出了集裝箱-托盤裝載模型、兩階段裝載模型對(duì)5組小規(guī)模算例進(jìn)行計(jì)算的結(jié)果（裝載率和運(yùn)行時(shí)間）。從裝載率角度來(lái)看，集裝箱-托盤裝載模型與兩階段裝載模型在一定時(shí)間內(nèi)實(shí)現(xiàn)了精確求解，獲得了最優(yōu)解，1均為0，驗(yàn)證了2個(gè)模型的正確性及有效性。

將2個(gè)模型對(duì)5組小規(guī)模算例的平均運(yùn)行時(shí)間繪制成折線圖，如圖4所示。由圖4可知，兩階段裝載模型的折線斜率相對(duì)變化幅度不大，魯棒性相對(duì)較好，且對(duì)5組算例的平均運(yùn)行時(shí)間相對(duì)較少，總平均運(yùn)行時(shí)間僅為109.41 s，而集裝箱-托盤裝載模型的平均運(yùn)行時(shí)間為473.87 s?？梢钥闯鱿噍^于集裝箱-托盤裝載模型，兩階段裝載模型在較短時(shí)間內(nèi)獲得了最優(yōu)解，收斂性好。究其原因，兩階段裝載模型在第1階段中確定了托盤裝載數(shù)量，減少了第2階段解的搜索空間，從而收斂性相對(duì)較好，提高了求解速度，減少了運(yùn)行時(shí)間。

圖4 5組小規(guī)模算例的平均運(yùn)行時(shí)間折線圖

2.3 大規(guī)模算例

表4 大規(guī)模算例數(shù)據(jù)對(duì)比

Tab.4 Comparison of large-scale experimental case data

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

圖5 5組大規(guī)模算例實(shí)驗(yàn)的G2值折線圖

從運(yùn)行時(shí)間來(lái)看，兩階段裝載模型的平均運(yùn)行時(shí)間為3 636.02 s，而兩階段啟發(fā)式算法的平均運(yùn)行時(shí)間僅為1.82 s，運(yùn)行時(shí)間差距相對(duì)較大，在較短的時(shí)間內(nèi)便獲得了理想的裝載方案。究其原因，該算法在第2階段將三維托盤裝載問(wèn)題轉(zhuǎn)化為二維托盤裝載問(wèn)題，極大地縮小了解的搜索空間，在頂部剩余空間中按照體積大小順序裝入產(chǎn)品，提高了裝載率，收斂性好；且在50個(gè)算例實(shí)驗(yàn)中，兩階段啟發(fā)式算法的運(yùn)行時(shí)間標(biāo)準(zhǔn)差為2.14，平均標(biāo)準(zhǔn)差僅為1.17，說(shuō)明算法的穩(wěn)定性較好。

從以上分析結(jié)果可以看出，在大規(guī)模算例實(shí)驗(yàn)中，兩階段啟發(fā)式算法所產(chǎn)生的產(chǎn)品裝載方案既保證了產(chǎn)品裝載的垛型穩(wěn)定，又具有高的空間利用率，避免產(chǎn)生浪費(fèi)；兩階段啟發(fā)式算法能在較短的時(shí)間內(nèi)得到好的裝載方案，魯棒性強(qiáng)，實(shí)用性好，能為工廠產(chǎn)品的托盤打包及裝箱提供參考。

3 結(jié)語(yǔ)

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

[1] 尚正陽(yáng), 黃秋妍, 康正陽(yáng), 等. 一刀切約束下的二維裝箱問(wèn)題高效求解算法[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] 劉勝, 沈大勇, 商秀芹, 等. 求解三維裝箱問(wèn)題的多層樹(shù)搜索算法[J]. 自動(dòng)化學(xué)報(bào), 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] 劉勝, 朱鳳華, 呂宜生, 等. 求解三維裝箱問(wèn)題的啟發(fā)式正交二叉樹(shù)搜索算法[J]. 計(jì)算機(jī)學(xué)報(bào), 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] 張長(zhǎng)勇, 翟一鳴. 基于改進(jìn)遺傳算法的航空集裝箱裝載問(wèn)題研究[J]. 北京航空航天大學(xué)學(xué)報(bào), 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] 王帥, 洪振宇. 基于強(qiáng)化學(xué)習(xí)的機(jī)場(chǎng)行李裝箱優(yōu)化方法[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] 呂雪菊, 倪靜. 基于自適應(yīng)空間劃分策略的三維裝箱問(wèn)題[J]. 系統(tǒng)工程, 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] 宋衛(wèi)生, 薛陽(yáng). 托盤裝載優(yōu)化設(shè)計(jì)系統(tǒng)的開(kāi)發(fā)[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

國(guó)家自然科學(xué)基金資助項(xiàng)目（72201252）；河南省社科規(guī)劃決策咨詢項(xiàng)目（2022JC10）；河南省高校智庫(kù)研究項(xiàng)目（2023ZKYJ21）

責(zé)任編輯：曾鈺嬋