多種貨物三維裝箱問題研究

丁紡，侯兆烽，趙凱芳

（天津大學(xué)仁愛學(xué)院，天津 301636）

集裝箱裝載一直被應(yīng)用于智能物流運(yùn)輸、加工調(diào)度、復(fù)雜系統(tǒng)等領(lǐng)域，同時(shí)，也是NP-hard問題，隨著全球經(jīng)濟(jì)迅猛發(fā)展，在現(xiàn)實(shí)生活中，自然災(zāi)害帶給我們的問題也不容小覷。問題背景源于2019年美國數(shù)學(xué)建模競賽B題“無人機(jī)發(fā)送：開發(fā)空中救災(zāi)響應(yīng)系統(tǒng)”。Grorge和Robinson首次提出了“層”的概念，再確定貨物裝載的優(yōu)先級(jí)得到較為突出的啟發(fā)式算法；Bischoff和Ratcliff提出了一種以計(jì)算加載范圍由下而上分層建立為主要特征的啟發(fā)式方法來解決裝載不相同物品的問題，這種方式產(chǎn)生的布局結(jié)構(gòu)更加穩(wěn)定，將運(yùn)輸平穩(wěn)性與包裝效率有效結(jié)合起來。后來，Taylor等人將混合整數(shù)規(guī)劃公式與動(dòng)態(tài)規(guī)劃啟發(fā)式算法相結(jié)合得到可行解。

不過，與之前研究的有所不同，在救災(zāi)響應(yīng)系統(tǒng)中，不僅僅要在滿足集裝箱承重約束、尺寸約束時(shí)使集裝箱的體積利用率最大，而且還要滿足裝載貨物數(shù)量比例的要求，保證讓災(zāi)區(qū)人民迅速得到救治，快速了解現(xiàn)場環(huán)境，對(duì)合理安排戰(zhàn)略性部署具有很強(qiáng)的現(xiàn)實(shí)意義。

1 三維裝箱建模

1.1 問題描述

三維裝箱問題定義為：已知有i個(gè)長寬高分別為Li、Wi、Hi的集裝箱和j種長寬高分別為li、wj、hj的貨物，經(jīng)一系列約束后使得集裝箱的利用率最大。

1.2 模型假設(shè)

（1）集裝箱形狀為長方體；

（2）所有貨物同樣均為長方體且質(zhì)量分布均勻；

（3）所有貨物均有外殼不會(huì)由于堆積而變形。

1.3 數(shù)學(xué)模型建立

式中，Z表示集裝箱裝載貨物的體積利用率；V表示集裝箱的體積；vi表示第i件貨物的體積。

貨物集裝三維尺寸長寬高約束：

2 基于啟發(fā)式三空間分割算法的模型求解

2.1 對(duì)啟發(fā)式三空間分割算法做幾點(diǎn)說明

（1）定序規(guī)則。在實(shí)際應(yīng)用中，不僅需要讓集裝箱的體積利用率最大，而且要在保證體積利用率最優(yōu)的情況下，讓貨物的數(shù)量符合一定要求保證裝載質(zhì)量。

（2）空間分割規(guī)則。空間分割是指在集裝箱裝入貨物后對(duì)剩余空間的有效劃分，避免因?yàn)椴煌瑒澐址绞綄?duì)剩余空間的利用率造成負(fù)面影響，而且隨著貨物裝載不斷進(jìn)行，集裝箱內(nèi)部裝載情況復(fù)雜嚴(yán)峻。這采用了三空間分割規(guī)則對(duì)集裝箱進(jìn)行空間劃分，即每當(dāng)有一個(gè)貨物裝入集裝箱時(shí)，在該貨物的前、右、上三個(gè)空間進(jìn)行分割，不斷生成一系列子空間，直至剩余空間不能滿足裝載條件。

（3）空間合并規(guī)則。啟發(fā)式算法中的空間分割只是讓集裝箱的貨物布局更加明朗，實(shí)際操作中，肯定會(huì)存在一些零散剩余子空間，所以，一定要對(duì)這些可以利用的剩余子空間進(jìn)行有效整合。這樣一來，就會(huì)有更大的剩余空間裝載貨物，提高集裝箱的體積利用率。

2.2 啟發(fā)式三空間分割算法分為以下步驟

Step1：導(dǎo)入集裝箱和貨物的尺寸信息，確定待裝貨物的種類、需求量以及不同貨物被允許的擺放方向。初始化待裝空間，表示為readyspace=（i,0,0,0,L,W,H），其中i表示為貨物的種類；O=(0,0,0)表示初始空間坐標(biāo)；Q=(L,W,H)表示可裝剩余空間坐標(biāo)。

Step2：根據(jù)空間大小和貨物需求量篩選貨物，確定準(zhǔn)備裝入集裝箱的貨物種類和方向組合，根據(jù)約定好的貨物裝載優(yōu)先級(jí)Si對(duì)待裝貨物進(jìn)行排序，生成W種裝載組合，其中W依賴于選擇的貨物種類d和貨物的方向組合p。

Step3：選擇第Wj（j=1）種裝載組合，對(duì)待裝入集裝箱的貨物進(jìn)行三維尺寸約束和體積約束條件進(jìn)行判斷，滿足貨物的長寬高和體積小于集裝箱的長寬高和體積。

Step4：判斷第Wj（j=1）種裝載組合是否滿足貨物裝載優(yōu)先級(jí)S，記錄產(chǎn)生的貨物種類di和貨物的方向組合pi。

Step5：當(dāng)滿足以上條件時(shí)，即有效裝箱后在剩余空間中劃分前、右、上三個(gè)空間的子空間，并且根據(jù)空間合并規(guī)則對(duì)剩余空間進(jìn)行整合，等待后續(xù)裝箱。

Step6：跳轉(zhuǎn)Step3，令j=j+1，選取新的裝載組合，對(duì)約束條件進(jìn)行判斷，重復(fù)迭代此循環(huán)直至j=W，結(jié)束循環(huán)。記錄其中產(chǎn)生的最優(yōu)解：包括貨物裝載的種類、數(shù)量和擺放方向。

Step7：結(jié)束裝箱，計(jì)算體積利用率，導(dǎo)出關(guān)于解的信息。

3 實(shí)驗(yàn)與結(jié)果

3.1 集裝箱和裝載貨物的尺寸信息

集裝箱采用國際標(biāo)準(zhǔn)ISO集裝箱，尺寸為231×92×94（單位：英尺）。貨物基本信息如表1所示。

表1 貨物的尺寸數(shù)據(jù)信息

3.2 實(shí)驗(yàn)結(jié)果與分析

通過計(jì)算得到，各種情況下裝載結(jié)果，如表2所示。

表2 計(jì)算結(jié)果

四種情況下的裝載效果圖如圖1～4所示。

圖1 情況1裝載示意圖

圖2 情況2裝載示意圖

圖3 情況3裝載示意圖

圖4 情況四裝載示意圖

3.3 模型優(yōu)化及推廣

通過生成標(biāo)準(zhǔn)ISO集裝箱裝載模型用戶界面，在輸入框內(nèi)輸入四種貨物的長寬高尺寸信息，經(jīng)過模型求解，便會(huì)在輸出框內(nèi)產(chǎn)生相對(duì)應(yīng)貨物的數(shù)量以及裝載貨物所用的體積利用率。圖5為輸入不同于上述四種貨物長寬高尺寸信息所產(chǎn)生的裝載模型界面。

圖5 標(biāo)準(zhǔn)ISO集裝箱裝載模型效果圖