基于分組策略的多目標(biāo)三維裝箱算法

張長(zhǎng)勇，吳剛鑫

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

基于分組策略的多目標(biāo)三維裝箱算法

張長(zhǎng)勇，吳剛鑫

（中國(guó)民航大學(xué) 電子信息與自動(dòng)化學(xué)院，天津 300300）

針對(duì)現(xiàn)有三維裝箱算法優(yōu)化目標(biāo)單一、優(yōu)化效率低的問(wèn)題，提出適用于求解大規(guī)模貨物裝載問(wèn)題的多目標(biāo)裝箱算法，以提高裝箱規(guī)劃效率，確保貨物運(yùn)輸安全?？紤]5種現(xiàn)實(shí)約束條件，以體積利用率和裝載垛型重心偏移量為優(yōu)化目標(biāo)，建立多目標(biāo)貨物裝載優(yōu)化模型。采用擬人式裝箱對(duì)貨物進(jìn)行預(yù)分組，減小決策空間，然后結(jié)合分組信息與裝箱算法生成初始解；引入數(shù)據(jù)驅(qū)動(dòng)的裝箱交叉算子提高算法收斂性；設(shè)計(jì)多策略變異算子提高算法結(jié)果的多樣性。以公共數(shù)據(jù)集和真實(shí)航空貨物數(shù)據(jù)作為實(shí)驗(yàn)數(shù)據(jù)進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，在滿足多種約束條件下，集裝箱裝載強(qiáng)異構(gòu)貨物平均體積利用率達(dá)到92.0%，重心位置空間偏移從20 cm減少到7.5 cm，并且算法運(yùn)行時(shí)間減少了73.5%。本文所提算法應(yīng)用于求解大規(guī)模多目標(biāo)三維裝箱問(wèn)題，提高了裝箱質(zhì)量和效率，可為三維裝箱算法的工程應(yīng)用提供參考。

三維裝箱；多目標(biāo)優(yōu)化；組合優(yōu)化；多變異策略

近年來(lái)，隨著我國(guó)的經(jīng)濟(jì)總量和對(duì)外貿(mào)易水平的逐步提升，貨物運(yùn)輸量逐年增加。貨物裝載是物流運(yùn)輸中的關(guān)鍵一環(huán)，貨物裝載自動(dòng)化、智能化可以提高物流綜合服務(wù)質(zhì)量，促進(jìn)國(guó)民經(jīng)濟(jì)發(fā)展。三維裝箱問(wèn)題是實(shí)現(xiàn)貨物裝載自動(dòng)化的關(guān)鍵之一，對(duì)提高貨物運(yùn)輸效率，保證貨物裝載質(zhì)量至關(guān)重要。

三維裝箱問(wèn)題是解空間龐大的NP-Hard問(wèn)題。為了得到近似最優(yōu)解，極點(diǎn)法、砌墻法、中心骨架法、三空間分割法、空間重組、擬人法等構(gòu)造性算法利用裝載經(jīng)驗(yàn)優(yōu)化裝箱布局，適用于解決貨物異構(gòu)性較低、裝箱約束條件少的裝箱問(wèn)題[1-2]。隨著裝箱問(wèn)題的發(fā)展，研究者開(kāi)始考慮多種復(fù)雜的現(xiàn)實(shí)約束[2-3]，并利用蟻群算法、化學(xué)優(yōu)化算法[4]、遺傳算法[5]以及一些混合鄰域搜索算法[6-9]求解裝箱問(wèn)題，此類(lèi)算法一般先利用構(gòu)造性算法生成初始裝載布局方案，再經(jīng)過(guò)鄰域搜索算法優(yōu)化布局方案，使較復(fù)雜的裝箱問(wèn)題能夠得到近似最優(yōu)解。由于考慮單一目標(biāo)的裝箱算法解決多樣的裝箱場(chǎng)景較為困難。Trivella等[10]設(shè)計(jì)了一種考慮負(fù)載平衡和裝箱數(shù)量的多目標(biāo)三維裝箱算法。Erbayrak等[11]提出一種以同批貨物完整和負(fù)載平衡為目標(biāo)的混合整數(shù)模型。由于多目標(biāo)三維裝箱問(wèn)題的目標(biāo)空間和決策空間更加龐大，使用構(gòu)造性算法和數(shù)學(xué)模型求解多目標(biāo)裝箱問(wèn)題僅能提供可行解，無(wú)法找到近似最優(yōu)解。趙向領(lǐng)等[12]提出了一種基于改進(jìn)遺傳算法的多目標(biāo)飛機(jī)配載模型，有效平衡了業(yè)載量和重心偏移量2個(gè)優(yōu)化目標(biāo)。近年來(lái)有學(xué)者開(kāi)始將多目標(biāo)進(jìn)化算法引入裝箱問(wèn)題[13]。為了提高多目標(biāo)進(jìn)化算法尋優(yōu)能力和保持解集的多樣性，很多學(xué)者對(duì)進(jìn)化算法進(jìn)行了改進(jìn)，如侯瑩等[14]設(shè)計(jì)了一種數(shù)據(jù)驅(qū)動(dòng)選擇策略的差分進(jìn)化算法，有效提升了算法求解復(fù)雜多目標(biāo)問(wèn)題的尋優(yōu)效率。Takagi等[15]提出了一種基于權(quán)重自適應(yīng)的分解多目標(biāo)進(jìn)化算法，通過(guò)不同子問(wèn)題之間的歐式距離判斷解的相似程度，并據(jù)此來(lái)調(diào)整解集的分布。

多目標(biāo)進(jìn)化算法的發(fā)展對(duì)解決多目標(biāo)三維裝箱問(wèn)題具有借鑒意義。本文以體積利用率和重心位置坐標(biāo)作為優(yōu)化目標(biāo)，提出一種基于分組策略的多目標(biāo)三維裝箱算法。通過(guò)貨物預(yù)分組策略和穩(wěn)定性移位設(shè)計(jì)降低問(wèn)題難度，設(shè)計(jì)自適應(yīng)選擇的裝箱進(jìn)化算子以加快收斂速度。利用公共數(shù)據(jù)集和真實(shí)航空貨物數(shù)據(jù)驗(yàn)證了算法的先進(jìn)性和適用性。

1 多目標(biāo)三維裝箱規(guī)劃模型

1.1 問(wèn)題描述問(wèn)題

1.2 假設(shè)條件

由于貨物多目標(biāo)三維裝箱優(yōu)化問(wèn)題的復(fù)雜性，為了簡(jiǎn)化數(shù)學(xué)模型，做出以下假設(shè)：

1）待裝貨物形狀均為長(zhǎng)方體。

2）貨物在最大承重范圍之內(nèi)可接受多層裝載。

3）待裝貨物重心為其幾何中心。

4）集裝箱中貨物的碼放位置不受區(qū)域的限制。

5）不考慮貨物在裝載過(guò)程中出現(xiàn)的擠壓變形等。

6）貨物充足，可以裝滿整個(gè)集裝箱。

1.3 模型建立

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

1.2.1 約束條件

根據(jù)裝箱問(wèn)題的現(xiàn)實(shí)條件，考慮約束條件如下。

1）總承載能力約束：規(guī)劃裝載貨物的總質(zhì)量不高于規(guī)定最大載重量。

2）箱體約束：貨物的各個(gè)頂點(diǎn)均在集裝箱內(nèi)部。

3）不重疊約束：2個(gè)貨物在、、3個(gè)平面的投影不存在2個(gè)投影面相交的情況。

4）穩(wěn)定性約束：貨物不可懸空，且要求每個(gè)貨物下表面接觸面積達(dá)一半以上。

5）貨物正交放置約束：保證貨物與集裝箱正交或平行。

為了減少不可行解對(duì)迭代方向的影響，將約束條件分類(lèi)為強(qiáng)約束條件和弱約束條件，其中強(qiáng)約束條件包括箱體約束、總質(zhì)量約束、總體積約束、不重疊約束，弱約束條件有穩(wěn)定性約束，順序約束。強(qiáng)約束嵌入到裝箱模型中，在目標(biāo)函數(shù)的每次評(píng)估前對(duì)解進(jìn)行約束篩選，減少了不可行解對(duì)迭代方向的影響；弱約束條件則在滿足強(qiáng)約束條件下進(jìn)行啟發(fā)式設(shè)計(jì)。

1.3.2 數(shù)學(xué)模型

式（1）～（19）為本文所考慮的目標(biāo)函數(shù)及約束條件；式（1）～（4）為目標(biāo)函數(shù)，分別為裝載規(guī)劃的體積利用率，重心與集裝箱安全重心、、方向的偏移距離；式（5）表示總承重能力約束；式（6）～（8）表示箱體約束；式（9）～（13）表示不重疊約束；式（14）～（16）表示穩(wěn)定性約束；式（17）～（19）表示貨物正交放置約束。

2 多目標(biāo)三維裝箱啟發(fā)式設(shè)計(jì)

2.1 擬人式裝載策略

為了使多目標(biāo)裝箱模型得到更優(yōu)的初始解，減少產(chǎn)生初始解耗時(shí)，采用一種簡(jiǎn)化的擬人式裝箱算法如圖1所示，算法對(duì)放置點(diǎn)進(jìn)行構(gòu)建、排序、隨機(jī)選取。用擬人算法對(duì)貨物進(jìn)行裝載的優(yōu)點(diǎn)是規(guī)則簡(jiǎn)單、裝載過(guò)程可觀測(cè)，并且其較差解也可以作為全局優(yōu)化算法的初始解。具體算法步驟如下：

1）載入貨物信息，進(jìn)行貨物信息預(yù)處理。

2）設(shè)定集裝箱左后下角作為初始可放置點(diǎn)。

3）按照規(guī)則對(duì)貨物排序。

4）根據(jù)約束條件檢測(cè)該貨物是否存在可放置點(diǎn)，存在可放置點(diǎn)，則隨機(jī)選取可放置點(diǎn)并放置當(dāng)前貨物，刪除已用可放置點(diǎn)；否則，將該貨物放置待裝貨物棧底，返回步驟3。

5）更新可放置點(diǎn)及剩余貨物信息。

6）判斷是否有貨物可裝載，若是，則返回步驟3；否則，輸出裝載方案。

圖1 擬人式裝箱示意圖

2.2 穩(wěn)定性移位設(shè)計(jì)

考慮到約束條件較多，穩(wěn)定性約束會(huì)導(dǎo)致得到的裝箱結(jié)果出現(xiàn)貨物懸空或者重心可變動(dòng)余量較少的問(wèn)題。為了使該算法在優(yōu)化過(guò)程中有良好的解集篩選環(huán)境，在得到解集后對(duì)解集得到的裝載結(jié)果進(jìn)行進(jìn)一步啟發(fā)式設(shè)計(jì)。采用先越界后回歸的方法保證所有貨物不懸空，使最終裝載方案可以最大程度安全可靠。具體流程見(jiàn)圖2。

穩(wěn)定性移位操作將在算法產(chǎn)生初始解以及算法的每次評(píng)價(jià)重心位置前使用，提高解的質(zhì)量。保證初始解的高質(zhì)量可以加快優(yōu)化進(jìn)程，保證最終解的高質(zhì)量可以提高規(guī)劃結(jié)果的安全性，避免得到貨物懸空或貨物容易發(fā)生偏移的裝載規(guī)劃。

3 基于分組策略的三維裝箱算法

基于分組策略的三維裝箱算法首先使用分組規(guī)則配合擬人式構(gòu)造法生成初始解，然后利用多策略進(jìn)化算法對(duì)多種可行方案尋優(yōu)，最后得到多個(gè)目標(biāo)函數(shù)均優(yōu)的裝載布局方案，其流程如圖3所示。

3.1 編碼方式

圖2 穩(wěn)定性移位

圖3 多目標(biāo)裝箱算法裝載流程

圖4 貨物放置狀態(tài)示意圖

3.2 分組策略及規(guī)則設(shè)計(jì)

三維裝箱問(wèn)題的決策空間非常龐大，因此，設(shè)計(jì)一種適用于三維裝箱問(wèn)題的空間降維方法對(duì)可行解的搜索有較大幫助。分組策略是大規(guī)模多目標(biāo)優(yōu)化問(wèn)題經(jīng)典的降維策略，其優(yōu)點(diǎn)是可以大幅減少搜索空間大小，缺點(diǎn)是分組效果會(huì)影響算法運(yùn)行效果。由于三維裝箱問(wèn)題的編碼方式可以通過(guò)對(duì)分組效果進(jìn)行評(píng)價(jià)，因此三維裝箱問(wèn)題可以通過(guò)具有一定規(guī)則的分組策略，加快可行解的搜索速度。

三維裝箱問(wèn)題的分組過(guò)程：通過(guò)自適應(yīng)擴(kuò)展的虛擬集裝箱體進(jìn)行初步虛擬裝箱，再將虛擬集裝箱配載到所裝集裝箱內(nèi)的方法，構(gòu)建新的裝載空間，可以使裝載過(guò)程更能適應(yīng)所裝貨物的變化，增強(qiáng)了空間分配的魯棒性。根據(jù)實(shí)驗(yàn)所用箱體，設(shè)定規(guī)則如下：

1）以帶強(qiáng)約束條件的擬人裝箱算法為基礎(chǔ)進(jìn)行分組。

2）每組以較大貨物為基準(zhǔn)進(jìn)行擴(kuò)展虛擬集裝箱體。

3）每組至少裝3個(gè)貨物且虛擬集裝箱體總體積在900 dm3～5 000 dm3之間；

4）每個(gè)分組后貨物占其對(duì)應(yīng)虛擬集裝箱總體積90%以上。

貨物分組后的虛擬集裝箱體被視為新貨物添加到待裝貨物中，分組操作偽代碼如下。

輸入 未分組貨物數(shù)據(jù)CargoData

初始化 GroupData=Φ, CargNum=0，VVirtualMax=0, GroupItem=1，CargoDataPacking=CargoData, CargoDataPacked=Φ,

if(9000.9) then

更新未分組貨物數(shù)據(jù)CargoData=CargoData Packing;

else

if (Length(CargoDataPacking)> 0) then

刪除已裝貨物CargoDataPacking= CargoDataPackingi,CargoNum= CargoNum+1;;

else

break;

end if

end if

else

else

break;

end if

end if

else

end if

end while

分組操作示意圖如圖5所示，6個(gè)貨物分為一組，即在解空間中將=(1, 1, 1, 2, 1, 3, 3, 1, 5, 4, 1, 7, 5, 1, 9, 6, 1, 11)簡(jiǎn)化為=(1, 1, 1)，實(shí)現(xiàn)了較大程度地降維。

圖5 分組操作

3.3 裝箱算子及啟發(fā)式進(jìn)化設(shè)計(jì)

考慮到進(jìn)化算法的核心是進(jìn)化算子，在裝箱問(wèn)題中，部分匹配交叉、循環(huán)交叉以及順序交叉為3種常見(jiàn)交叉方法。通過(guò)實(shí)驗(yàn)驗(yàn)證可知，部分匹配交叉的結(jié)果更好，但往往進(jìn)化緩慢。組合優(yōu)化的優(yōu)化進(jìn)程與簡(jiǎn)單函數(shù)優(yōu)化不同，主要在于連續(xù)優(yōu)化可以取較優(yōu)解進(jìn)行均值優(yōu)化，而三維裝箱的決策變量與目標(biāo)函數(shù)的關(guān)聯(lián)性較弱，普通交叉算子或二項(xiàng)式交叉變異算子無(wú)法滿足均值優(yōu)化等優(yōu)化方法的基本需求，因此必須設(shè)計(jì)新型交叉變異算子，使其適應(yīng)三維裝箱優(yōu)化問(wèn)題。姿態(tài)近似情況如表2所示

表2 姿態(tài)近似規(guī)則

Tab.2 Attitude approximation rule

圖6 交叉算子

變異操作會(huì)加強(qiáng)種群的多樣性，采用多種變異策略以避免非成熟收斂情況的出現(xiàn)，同時(shí)可以避免因交叉操作引起的局部收斂。隨機(jī)變異策略，對(duì)相似解的少數(shù)相同變量進(jìn)行隨機(jī)替換，如圖7所示。單點(diǎn)變異，選取編碼段某隨機(jī)位置與隨機(jī)實(shí)數(shù)進(jìn)行替換，如圖8所示。順序逆轉(zhuǎn)變異，通過(guò)在父代中隨機(jī)選取2個(gè)點(diǎn)作為該變異的變異點(diǎn)，接下來(lái)在子代中以與父代中相反的順序選取2個(gè)點(diǎn)進(jìn)行重新排列，是一種仿生的變異方式，如圖9所示。在算法迭代期間，若算法陷入局部最優(yōu)，即解集某區(qū)域附近有較多次優(yōu)解時(shí)使用隨機(jī)變異策略，探索未知空間，其中次優(yōu)解指非支配排序中第2序列解。若解集某區(qū)域附近有最優(yōu)解且最優(yōu)解較少時(shí)使用單點(diǎn)變異策略，加快收斂速度，提高收斂程度；順序逆轉(zhuǎn)變異則在任意解集情況時(shí)按變異概率發(fā)生。

圖7 隨機(jī)變異策略

圖8 單點(diǎn)變異策略

圖9 順序逆轉(zhuǎn)變異策略

4 結(jié)果與分析

為檢驗(yàn)文中所提算法的適用性，采用文獻(xiàn)[15]中Bischoff & Ratcliff標(biāo)準(zhǔn)算例。算例分為十六大類(lèi)，BR0～BR7箱型種類(lèi)為3到20種，是一種弱異構(gòu)箱型；BR8～BR15箱型種類(lèi)為30到100種，是一種強(qiáng)異構(gòu)箱型。BR0～BR15異構(gòu)性依次增強(qiáng)，每種箱型有若干個(gè)待選箱體，進(jìn)行實(shí)驗(yàn)對(duì)比的集裝箱尺寸為587 cm× 233 cm× 220 cm。為了驗(yàn)證重心位置調(diào)整效果，為不同貨物設(shè)置了不同組的密度，使貨物存在一定質(zhì)量。以BR10算例為例展示部分貨物信息，如表3所示，從50組貨物中每組抽取2個(gè)貨物進(jìn)行分組，分組結(jié)果如表4所示。

表3 BR10算例信息

Tab.3 Cargo data of BR10

表4 分組結(jié)果

Tab.4 Grouping results

從表5可以得知，用弱異構(gòu)的BR0～BR7算例進(jìn)行測(cè)試，文獻(xiàn)[3]算法所得平均體積利用率為91.125%，碼垛的重心位置偏移距離為20.839 6cm，尤其是異構(gòu)性最弱的BR0、BR2的高度偏移在18 cm以上，有較大安全風(fēng)險(xiǎn)。文獻(xiàn)[11]算法所得平均體積利用率為85.880%，碼垛重心位置偏移距離為11.240 8 cm；本文所提算法所得平均體積利用率為90.3%，碼垛的重心位置偏移距離為3.655 cm。用強(qiáng)異構(gòu)的BR8～BR15算例進(jìn)行測(cè)試，文獻(xiàn)[3]算法所得平均體積利用率為84.175%，碼垛的重心位置偏移距離為17.932 5 cm；文獻(xiàn)[11]算法所得平均利用率為69.312%，碼垛的重心位置偏移距離為12.312 3 cm；本文所提算法所得平均體積利用率為92.0%，平均偏移距離為4.742 5 cm。本文算法在強(qiáng)異構(gòu)貨物的測(cè)試時(shí)，所得體積利用率與偏移距離均優(yōu)于文獻(xiàn)[3]和文獻(xiàn)[11]。

如圖10所示，某次裝載過(guò)程最優(yōu)解的收斂情況表明，該算法可以在250次迭代時(shí)接近近似最優(yōu)解，求解效率較高。另外，文獻(xiàn)[3]算法求解一次耗時(shí)51.81 s；本文算法的分組策略降低了90%以上的決策空間，求解一次平均耗時(shí)為13.73 s，求解時(shí)間比文獻(xiàn)[3]降低了73.5%。

表5 3種算法集裝箱體積利用率與重心位置比較

Tab.5 Comparison of container volume utilization rate and center of gravity position

圖10 算法性能對(duì)比

表6 航空貨物裝載結(jié)果

Tab.6 Air cargo loading results

圖11 較優(yōu)裝載規(guī)劃可視化

5 結(jié)語(yǔ)

針對(duì)現(xiàn)有的多目標(biāo)三維裝箱算法在求解強(qiáng)異構(gòu)貨物裝載問(wèn)題時(shí)尋優(yōu)能力弱的問(wèn)題，提出了一種基于分組策略的多目標(biāo)三維裝箱算法。算法以體積利用率和重心位置坐標(biāo)作為優(yōu)化目標(biāo)，通過(guò)貨物預(yù)分組策略和穩(wěn)定性移位設(shè)計(jì)降低問(wèn)題難度，設(shè)計(jì)自適應(yīng)選擇的裝箱進(jìn)化算子加快收斂，通過(guò)標(biāo)準(zhǔn)算例和真實(shí)航空貨物數(shù)據(jù)進(jìn)行實(shí)驗(yàn)對(duì)比。實(shí)驗(yàn)結(jié)果表明，該算法可以得到重心位置靠近箱體幾何中心的多種裝載規(guī)劃，在求解強(qiáng)異構(gòu)貨物時(shí)，算法的裝載規(guī)劃結(jié)果明顯優(yōu)于對(duì)比算法。將分組策略用于多目標(biāo)三維裝箱優(yōu)化問(wèn)題，極大地加快了該問(wèn)題的求解速度。本文分組規(guī)則仍然較為簡(jiǎn)單，制定更加合理的貨物分組規(guī)則或設(shè)計(jì)新型降維策略，是將來(lái)多目標(biāo)裝箱問(wèn)題的重要研究工作。

[1] 張長(zhǎng)勇, 翟一鳴. 面向不規(guī)則集裝箱的貨物裝載優(yōu)化問(wèn)題研究[J]. 計(jì)算機(jī)應(yīng)用與軟件, 2022, 39(11): 238-244.

ZHANG Chang-yong, ZHAI Yi-ming. Optimization of Cargo Loading for Irregular Containers[J]. Computer Applications and Software, 2022, 39(11): 238-244.

[2] JUNQUEIRA L, MORABITO R, YAMASHITA D. Three-Dimensional Container Loading Models with Cargo Stability and Load Bearing Constraints[J]. Computers & Operations Research, 2012, 39(1): 74-85.

[3] 朱賀. 考慮重心位置的飛機(jī)裝載優(yōu)化問(wèn)題的研究[D]. 北京: 北京交通大學(xué), 2018.

ZHU He. Research on Aircraft Loading Optimization Considering the Position of Center of Gravity[D]. Beijing: Beijing Jiaotong University, 2018.

[4] CHEN Shu-hao, SU Ya-ru, YE Yan-ming, et al. A Hybrid Chemical Reaction Optimization Algorithm for Solving 3D Packing Problem[J]. International Journal of Autonomous and Adaptive Communications Systems, 2021, 14(1/2): 117-131.

[5] Luo Q, Rao Y, Peng D. GA and GWO algorithm for the special bin packing problem encountered in field of aircraft arrangement[J]. Applied Soft Computing, 2022, 114: 108060.

[6] FU Yu, BANERJEE A. Heuristic/Meta-Heuristic Methods for Restricted Bin Packing Problem[J]. Journal of Heuristics, 2020, 26(1): 637-662.

[7] BORGULYA I. A Hybrid Evolutionary Algorithm for the Offline Bin Packing Problem[J]. Central European Journal of Operations Research, 2021, 29(2): 425-445.

[8] HE Kun, TOLE K, NI Fei, et al. Adaptive Large Neighborhood Search for Solving the Circle Bin Packing Problem[J]. Computers & Operations Research, 2021, 127(5): 105140.

[9] 張長(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.

[10] TRIVELLA A, PISINGER D. The Load-Balanced Multi-Dimensional Bin-Packing Problem[J]. Computers and Operations Research, 2016, 74: 152-164.

[11] ERBAYRAK S, ?ZKIR V, YILDIRIM U. Multi-Objective 3D Bin Packing Problem with Load Balance and Product Family Concerns[J]. Computers & Industrial Engineering, 2021, 159(19): 107518.

[12] 趙向領(lǐng), 李云飛, 李鵬飛. 基于改進(jìn)遺傳算法的航空器載重平衡[J]. 科學(xué)技術(shù)與工程, 2022, 22(33): 14951-14958.

ZHAO Xiang-ling, LI Yun-fei, LI Peng-fei. Aircraft Load Balance Based on Improved Genetic Algorithm[J]. Science Technology and Engineering, 2022, 22(33): 14951-14958.

[13] 鞏梨, 王文璨, 劉林忠. 多目標(biāo)一維裝箱問(wèn)題模型算法研究[J]. 計(jì)算機(jī)應(yīng)用研究, 2020, 37(S2): 144-146.

GONG Li, WANG Wen-jie, LIU Lin-zhong. Research on Model Algorithm of Multi-Objective One-Dimensional Packing Problem[J]. Application Research of Computers, 2020, 37(S2): 144-146.

[14] 侯瑩, 吳毅琳, 白星, 等. 數(shù)據(jù)驅(qū)動(dòng)選擇策略的多目標(biāo)差分進(jìn)化算法[J]. 控制與決策, 2022, 38(7): 1-9.

HOU Ying, WU Yi-lin, BAI Xing, et al. Multi-Objective Differential Evolution Algorithm with Data-Driven Selection Strategy[J]. Control and Decision, 2022, 39(7): 1-9.

[15] TAKAGI T, TAKADAMA K, SATO H. Weight Vector Arrange1ment Using Virtual Objective Vectors in Decomposition-Based MOEA[C]// 2021 IEEE Congress on Evolutionary Computation (CEC), IEEE, 2021: 1462-1469.

Multi-objective 3D Packing Algorithm Based on Grouping Strategy

ZHANG Chang-yong, WU Gang-xin

(School of Electronic Information and Automation, Civil Aviation University of China, Tianjin 300300, China)

The work aims to propose a multi-objective packing algorithm suitable for large-scale cargo loading to solve the problems of single optimization objective and low optimization efficiency of existing 3D packing algorithms, so as to improve the efficiency of packing planning and ensure the safety of cargo transportation. Firstly, considering five realistic constraints, a multi-objective cargo loading optimization model was established with the volume utilization and the shift of the center of gravity of the loading layout as the optimization objectives. Then, the cargoes were pre-grouped by anthropomorphic packing to reduce the decision space, and the initial solutions were generated by combining the grouping information with the packing algorithm; A data-driven cross operator was introduced to packing to improve the convergence of the algorithm; Multi-strategy mutation operators were designed to improve the diversity of algorithm results. With the public data set and real air cargo data as the experimental data, the experimental results showed that the average volume utilization rate of strongly heterogeneous cargoes in container loading reached 92.0%. The space offset of the center of gravity position was reduced from 20 cm to 7.5 cm. And the running time of the algorithm was reduced by 73.5% under various constraints. Therefore, the algorithm proposed in this paper is applied to solve the large-scale multi-objective three-dimensional packing problem, which improves the packing quality and efficiency, and can provide reference for the engineering application of the three-dimensional packing algorithm.

three-dimensional packing; multi-objective optimization; combinatorial optimization; multiple mutation strategy

TP301；TP311

A

1001-3563(2023)21-0204-10

10.19554/j.cnki.1001-3563.2023.21.025

2023-02-07

民航首臺(tái)（套）重點(diǎn)項(xiàng)目（3122023PY04）

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