融合啟發(fā)式搜索的改進(jìn)極快決策樹算法在多規(guī)格貨物智能混合裝載中的應(yīng)用

李 偉, 楊超宇, 孟祥瑞

(安徽理工大學(xué)經(jīng)濟(jì)與管理學(xué)院， 淮南 232001)

在物流管理中，貨物裝載是一個(gè)極為重要的環(huán)節(jié)。貨物的裝載情況決定了物流配送的運(yùn)輸成本和訂單的時(shí)間成本。由于需求的貨物各不相同，即涉及多規(guī)格貨物的混合裝載問題。為了提高運(yùn)輸過程中集裝箱的利用率和貨物裝載效率，目前已有很多學(xué)者對(duì)其進(jìn)行了研究。

從提高集裝箱利用率出發(fā)，George等[1]最先提出了基于“層”概念的啟發(fā)式算法，提高了集裝箱的橫截面利用率；Gon?alves等[2]研究了有偏隨機(jī)密鑰遺傳算法，通過利用箱內(nèi)的空閑空間極大提高了箱子的利用率；Yang等[3]和Hifi等[4]提出了基于整數(shù)線性規(guī)劃啟發(fā)式的簡單策略求解三維裝箱問題。劉勝等[5]提出了啟發(fā)式樹搜索算法，顯著提高了集裝箱的利用率；那日薩等[6-7]利用了三維裝箱問題的多目標(biāo)混合整數(shù)規(guī)劃模型，給出了一種啟發(fā)式搜索算法的求解方法；朱瑩等[8-9]針對(duì)集裝箱船裝載提出了一種新型的混合遺傳算法，明顯提高了空間利用率；崔會(huì)芬等[10]提出了一種改進(jìn)的遺傳算法，提高了集裝箱的裝箱效率。

從提高裝箱效率出發(fā)，尚正陽等[11]通過剩余空間最優(yōu)化算法可以快速計(jì)算裝箱結(jié)果；鄭琰等[12]基于空間管理思想，將“砌墻”式建構(gòu)算法與一種四規(guī)則深度優(yōu)先搜索法相結(jié)合，在提高集裝箱利用率的同時(shí)縮短了計(jì)算時(shí)間；張雅艦等[13]針對(duì)現(xiàn)有遺傳算法求解裝箱收斂速度慢的問題，提出了一種改進(jìn)的遺傳算法，提高了計(jì)算速度；張鈞等[14]提出了混合遺傳模擬退火算法，對(duì)強(qiáng)異構(gòu)和弱異構(gòu)貨物都有很好的裝載效果；廖星等[15]采用自適應(yīng)權(quán)重法改進(jìn)了粒子群優(yōu)化算法，大幅加快了計(jì)算速度；崔雪蓮等[16]采用樹搜索策略，以空間切割、貨物組塊及裝載套數(shù)迭代法為基礎(chǔ)，構(gòu)建了一種啟發(fā)式搜索算法，提高了裝載效率和算法實(shí)用性。

現(xiàn)有的貨物裝載問題的研究方向大致是提高集裝箱利用率和提高裝箱效率兩個(gè)方面。針對(duì)這兩個(gè)方向提出了以極快決策樹為主，空間合并和裝載空間再利用為輔的啟發(fā)式搜索算法。在保證集裝箱利用率的前提下，提高貨物的裝載效率。

1 問題及目標(biāo)描述

1.1 問題描述

多規(guī)格貨物裝載是指將貨物大小、尺寸不同的待裝貨物裝載到固定尺寸的集裝箱內(nèi)。由于貨物的尺寸不同，每裝入一個(gè)箱子可能產(chǎn)生不同的剩余空間，若不考慮貨物裝載后產(chǎn)生的空間問題，很容易造成空間浪費(fèi)。在裝載過程既要保證集裝箱的利用率又要保證貨物裝載的高效性，相比單一貨物的裝載，其條件限制更多。

1.2 目標(biāo)描述

為使研究目標(biāo)更直觀，將目標(biāo)描述如下。

給定一個(gè)集裝箱C和一系列待裝貨物的集合B，假設(shè)集裝箱和待裝貨物均為長方體。集裝箱的長為L，寬為W，高為H，體積V=LWH；每個(gè)待裝貨物bi的長為li，寬為wi，高為hi，體積vi=liwihi。目標(biāo)是在集合B中尋找一個(gè)子集F，使得集裝箱C的空間利用率最大，即

max fitness=VF/V=∑liwihi/V

(1)

并且滿足以下約束：

(1)任何bi∈F在集裝箱C中都有一個(gè)裝載位置。

(2)F中的任意兩個(gè)箱子的裝載位置都不能重疊。

(3)所有bi∈F中的箱子都必須可以放入在C中。

(4)穩(wěn)定性約束，即每個(gè)被裝載的箱子必須有容器底部或者其他已經(jīng)裝載的箱子作為支撐。

2 融合啟發(fā)式搜索的改進(jìn)極快決策樹智能裝箱算法

本文算法是在極快決策樹(extremely fast decision tree，EFDT)上融合了啟發(fā)式搜索算法(heuristically search,HS)形成了融合啟發(fā)式搜索的改進(jìn)極快決策樹智能裝箱算法(EFDT-HS)，此算法首先計(jì)算并擇優(yōu)選取樣本信息熵，然后構(gòu)建生成貨物裝箱決策樹模型，最后基于啟發(fā)式搜索方法對(duì)貨物裝載后的剩余空間進(jìn)行合并再利用。

2.1 極快決策樹算法

極快決策樹是HATT(hoeffding anytime tree)的系統(tǒng)實(shí)現(xiàn)[17]。HATT是由HT(hoeffding tree)改進(jìn)得來的VFDT(very fast decision tree)發(fā)展而來[18]。追根溯源，HT與HATT的本質(zhì)都是決策樹。

2.1.1 度量標(biāo)準(zhǔn)

(1)信息熵。

在決策樹的生成中，獲得信息量的度量方法是從反方向來定義的。若一種劃分能使數(shù)據(jù)的“不確定性”減少的越多，意味著該劃分能獲得越多的信息。采用度量不確定性的方法是信息熵，即

(2)

對(duì)于具體的隨機(jī)變量y生成的數(shù)據(jù)集D={y1,y2,…,yN}而言，在實(shí)際操作中通常會(huì)利用經(jīng)驗(yàn)熵來估計(jì)真正的信息熵，即

(3)

這里假設(shè)隨機(jī)變量y的取值空間為{c1,c2,…,ck}，pk為y取ck的概率：pk=p(y=ck)；|ck|為有隨機(jī)變量y中的類別為ck的樣本個(gè)數(shù)；|D|為D的總樣本個(gè)數(shù)，即|D|=N。

(2)信息增益。

單一特征的情況(n=1)：設(shè)特征為A，數(shù)據(jù)集D={(A1,y1),(A2,y2),…,(AN,yN)}；此時(shí)所謂信息的增益，反映的就是特征A帶來的關(guān)于y的“信息量”的大小。

引入條件熵H(y|A)[式(4)]的概念來定義信息的增益。所謂條件熵，就是根據(jù)特征A的不同取值{a1,a2,…,am}對(duì)y進(jìn)行限制后，先對(duì)這些被限制的y分別計(jì)算信息熵，再把這些信息熵(一共有m個(gè))根據(jù)特征取值本身的概率加權(quán)求和，從而得到總的條件熵。換句話說，條件熵是指被A不同取值限制的各個(gè)部分的y不確定性并以取值本身的概率作為權(quán)重相加得到的。所以，條件熵H(y|A)越小，意味著y被A限制后的總的不確定性越小，從而更易做出決策。

(4)

其中：

log2p(y=ck|A=aj)

(5)

為經(jīng)驗(yàn)條件熵。

根據(jù)條件熵的直觀含義，信息的增益就可以定義為

g(y,A)=H(y)-H(y|A)

(6)

(3)霍夫丁邊界。

2.1.2 計(jì)算思想

(1)快速?zèng)Q策樹。

快速?zèng)Q策樹(very fast decision tree，VFDT)通過Hoeffding不等式實(shí)現(xiàn)從無限的樣本中通過有限的樣本在一定的置信度以內(nèi)找到符合條件的決策節(jié)點(diǎn)屬性。VFDT決策樹的生長是樣本通過葉子節(jié)點(diǎn)時(shí)，葉子節(jié)點(diǎn)保存樣本的屬性值，當(dāng)葉子節(jié)點(diǎn)內(nèi)的屬性值符合Hoeffding不等式的要求，也就是其中一個(gè)屬性的信息熵差值大于預(yù)先計(jì)算好的閾值，就可以判定該節(jié)點(diǎn)的屬性，從而葉子節(jié)點(diǎn)再繼續(xù)生長。樣本從根結(jié)點(diǎn)開始，根據(jù)其屬性不斷劃分遍歷直到葉子節(jié)點(diǎn)，葉子節(jié)點(diǎn)保存其屬性值用來判定。隨著數(shù)據(jù)流中的樣本在決策樹的各個(gè)節(jié)點(diǎn)的遍歷，葉子節(jié)點(diǎn)的屬性統(tǒng)計(jì)值不斷更新。

(2)極快決策樹。

EFDT作為HATT的系統(tǒng)實(shí)現(xiàn)，是通過Hoeffding不等式來確定在最佳屬性上進(jìn)行拆分的信息熵是否超過沒有拆分的信息熵，或者當(dāng)前拆分屬性的優(yōu)點(diǎn)。在實(shí)踐中，如果一個(gè)節(jié)點(diǎn)上不存在分裂屬性，那么當(dāng)最優(yōu)候選屬性的性能超過次優(yōu)候選屬性時(shí)，HATT將在最優(yōu)候選屬性帶來的信息增益為非零且具有所需的置信度時(shí)進(jìn)行拆分，而不是只在最優(yōu)候選屬性的性能優(yōu)于次優(yōu)候選屬性時(shí)進(jìn)行拆分。且當(dāng)前最優(yōu)屬性和當(dāng)前拆分屬性之間的信息增益差異非零時(shí)，HATT將進(jìn)行分割，并假設(shè)這比沒有分割要好。

總而言之，VFDT是通過設(shè)定一個(gè)閾值，選取信息熵大于這個(gè)閾值的節(jié)點(diǎn)作為葉節(jié)點(diǎn)；EFDT是通過計(jì)算樣本數(shù)據(jù)中每個(gè)樣本的信息值，在滿足Hoeffding不等式的前提下選擇相對(duì)上一節(jié)點(diǎn)信息增益不為零且在樣本中信息增益最大的節(jié)點(diǎn)為葉節(jié)點(diǎn)，即擇優(yōu)選取。

引用極快決策樹的擇優(yōu)思想。在集裝箱裝載時(shí)，把每一層的裝載看作一棵樹的形成，把每個(gè)要放入的箱子看作一個(gè)葉節(jié)點(diǎn)，在滿足條件約束的情況下，選擇體積最大的箱子裝入。

2.2 啟發(fā)式算法

啟發(fā)式算法是人們?cè)诮鉀Q問題時(shí)所采取的一種根據(jù)經(jīng)驗(yàn)規(guī)則來處理問題的方法。其特點(diǎn)是在解決問題時(shí)，利用過去的經(jīng)驗(yàn)，選擇已經(jīng)行之有效的方法去尋求答案。

啟發(fā)式算法的設(shè)計(jì)具有很大的隨意性和創(chuàng)造性，而且一般缺少嚴(yán)格的理論推導(dǎo)和數(shù)學(xué)證明，因此，一般也只能通過大量的試驗(yàn)數(shù)據(jù)來檢驗(yàn)算法的性能好壞。由于對(duì)于完全類的組合優(yōu)化問題，目前缺少一般的算法來求解，精確算法又太耗時(shí)，因此啟發(fā)式算法被越來越多的應(yīng)用到這些問題的求解中[19]。對(duì)于裝箱問題也是如此，自從該問題被提出以來，學(xué)者提出了很多應(yīng)用于裝箱問題的啟發(fā)式算法。車玉馨[20]的三維塊生成算法是將Zhu等[21]提出的塊生成算法中的塊分為簡易塊和通用塊，使兩種塊相互組合生成新的更符合裝載空間的長方體。

貨物裝載過程中存在不同的情況，一種是貨物裝載過程中可以把兩種不同類型貨物完美組合，使空間利用率達(dá)到100%；另一種是貨物裝載過程中兩種類型貨物組合后仍有剩余空間，于是在待裝貨物中尋找符合剩余空間的貨物塊，三種或多種類型貨物塊的相互組合，使空間得到充分利用。在利用右圖思想的同時(shí)考慮到放入的貨物的寬度和高度會(huì)小于上一裝載的貨物，于是在貨物裝箱過程中考慮了“空間合并”和“裝載空間再利用”的啟發(fā)式算法。

2.2.1 空間合并

在上一節(jié)提到要將每一層的裝載看作一棵樹的形成，在每一層的裝載中都可能會(huì)有剩余的長度，為了充分利用每一層的剩余長度，采用了上下剩余空間合并的方法。上下空間合并分為如圖1所示三種情況。

圖1 上下空間合并Fig.1 Upper and lower space merge

(1)當(dāng)前裝載層的剩余長度大于上一裝載層的剩余長度，如圖1(a)所示。在這種情況下，以較短的上一裝載層的剩余長度為剩余空間的最大長度，以這一裝載列最底層根節(jié)點(diǎn)的寬度為最大寬度，以要合并的兩層裝載空間根節(jié)點(diǎn)的高度之和為最大高度。在待裝貨物中判斷是否有符合此空間的貨物。

(2)當(dāng)前裝載層的剩余高度小于上一裝載層的剩余長度，即圖1(b)所示。在這種情況下，以較短的當(dāng)前裝載的剩余長度為剩余空間的最大長度，以這一裝載列最底層根節(jié)點(diǎn)的寬度為最大寬度，以要合并的兩層裝載空間根節(jié)點(diǎn)的高度之和為最大高度。在待裝貨物中判斷是否有符合此空間的貨物。

(3)當(dāng)前裝載層的剩余高度等于上一裝載層的剩余長度，即如圖1(c)所示。在這種情況下，以較短的當(dāng)前裝載的剩余長度為剩余空間的最大長度，以這一裝載列最底層根節(jié)點(diǎn)的寬度為最大寬度，以要合并的兩層裝載空間根節(jié)點(diǎn)的高度之和為最大高度。在待裝貨物中判斷是否有符合此空間的貨物。

2.2.2 裝載空間再利用

由于是多規(guī)格貨物裝載，很有可能出現(xiàn)上一個(gè)裝載貨物要比下一個(gè)裝載貨物寬或者高，于是提出了裝載空間再利用的想法，目的是盡可能地把空閑空間利用起來。裝載空間再利用分為如圖2所示兩種情況。

圖2 上部剩余空間利用、平行剩余空間利用Fig.2 Upper residual space utilization, parallel residual space utilization

(1)當(dāng)前裝入的貨物高度小于上一裝載貨物的高度，即圖2(a)所示，在這種情況下，以當(dāng)前放入貨物的長度為最大長度，以當(dāng)前裝載層根節(jié)點(diǎn)的寬度為最大寬度，以當(dāng)前裝載層根節(jié)點(diǎn)與當(dāng)前放入貨物的高度差作為待利用空間的最大高度。在待裝貨物中判斷是否有符合該利用空間的貨物。

(2)當(dāng)前裝入的貨物寬度小于上一裝載貨物的寬度，即圖2(b)所示，在這種情況下，以當(dāng)前裝載層根節(jié)點(diǎn)與當(dāng)前裝入的貨物的寬度差作為最大寬度，以當(dāng)前裝入貨物的長度作為最大長度，以當(dāng)前裝載層根節(jié)點(diǎn)的高度作為最大高度。在待裝貨物中判斷是否有符合該利用空間的貨物。

2.3 融合啟發(fā)式搜索的改進(jìn)極快決策樹智能算法在裝箱問題的應(yīng)用

在集裝箱中把每一個(gè)裝載層的裝載過程看作一棵樹的創(chuàng)建過程。

將集裝箱看作三維坐標(biāo)系，假設(shè)x軸為集裝箱的長，y軸為集裝箱大的高，z軸為集裝箱大的寬，從最里面靠左開始裝載，先沿x-y面進(jìn)行裝載，x-y面裝載完成后再沿z軸增加一列繼續(xù)沿x-y面進(jìn)行裝載。

在對(duì)貨物進(jìn)行裝載時(shí)，把裝載情況分為兩種：底層裝載和非底層裝載。

2.3.1 底層裝載函數(shù)

底層裝載，即此時(shí)裝載層的長度占用為0，高度占用也為0的情況，反映到坐標(biāo)系中即為x=0，y=0的情況。底層裝載函數(shù)步驟如下：

步驟1初始裝箱，選取待裝貨物中體積最大的貨物作為裝入的第一個(gè)貨物，作為根節(jié)點(diǎn)。讀取此貨物的長寬高，計(jì)算當(dāng)前裝載層的剩余長度、最大寬度、最大高度、剩余寬度。

步驟2在剩余待裝貨物中取出符合剩余長度、最大寬度、最大高度的箱子，計(jì)算這些箱子的體積，并按照箱子編號(hào)和對(duì)應(yīng)體積降序排列。取體積最大的箱子裝入。在裝入每層非第一個(gè)箱子后，都判斷裝入箱子的上部空余空間和平行剩余空間是否還能放入箱子(箱子可旋轉(zhuǎn))。

步驟3更新此裝載層的剩余長度，重復(fù)步驟2，直到?jīng)]有滿足的箱子。

步驟4返回裝箱結(jié)果、待裝貨物、此裝載層的最大寬度、剩余空間的長度、集裝箱剩余高度、集裝箱的剩余寬度。

2.3.2 非底層裝載函數(shù)

非底層裝載，即此時(shí)裝載層長度占用為0，高度占用不為0的情況，反映到坐標(biāo)系中即為x=0，y≠0的情況。非底層裝載函數(shù)步驟如下:

步驟1取出符合剩余高度、最大寬度的箱子，并計(jì)算這些箱子的體積，按照箱子編號(hào)和對(duì)應(yīng)的體積降序排列。取體積最大的箱子裝入，作為根節(jié)點(diǎn)。

步驟2讀取根節(jié)點(diǎn)貨物的長度和高度，即為當(dāng)前裝載層的最大高度，計(jì)算此裝載層的剩余長度、集裝箱此列的剩余高度。

步驟3在剩余待裝貨物中取出符合剩余長度、最大寬度、最大高度的箱子，計(jì)算這些箱子的體積，并按照箱子編號(hào)和對(duì)應(yīng)體積降序排列。取體積最大的箱子裝入。在裝入每層非第一個(gè)箱子后，判斷裝入箱子的上部空余空間和平行剩余空間是否還能放入箱子(箱子可旋轉(zhuǎn))。

步驟4更新此裝載層的剩余長度，重復(fù)步驟3，直到?jīng)]有滿足的箱子。

步驟5讀取此裝載層的剩余長度，若上一步裝載層的剩余長度大于0，則合并上下兩層的高度，得到一個(gè)新的空間，返回新空間的長寬高，遍歷剩余裝箱貨物，若有符合合并空間的貨物則取體積最大的一個(gè)放入，并將此裝載層的剩余長度重置為0。(箱子可旋轉(zhuǎn))

步驟6返回裝箱結(jié)果、待裝貨物、此裝載層的最大寬度、剩余空間的長度、集裝箱剩余高度。

2.3.3 函數(shù)的應(yīng)用

在集裝箱剩余寬度不為零且待裝貨物中有符合條件的箱子時(shí)：

步驟1執(zhí)行底層裝載函數(shù)

步驟2執(zhí)行非底層裝箱函數(shù)，在剩余高度大于0的前提下，循環(huán)執(zhí)行非底層裝箱函數(shù)，直到?jīng)]有符合剩余高度的箱子為止。

步驟3沿y軸增加一列，繼續(xù)執(zhí)行步驟1、步驟2，直到?jīng)]有符合y軸剩余寬度的箱子為止。

3 實(shí)例計(jì)算與結(jié)果分析

基于Python程序、Django框架和JavaScript實(shí)現(xiàn)了該算法并可對(duì)裝載結(jié)果進(jìn)行三維展示。為驗(yàn)證提出方法的有效性，采取OR-Library[22]中BR1～BR7算例數(shù)據(jù)進(jìn)行測試，7個(gè)算例中每個(gè)算例包含100個(gè)子算例且每個(gè)子算例箱子種類數(shù)分別為3、5、8、10、12、15、20，異構(gòu)性從弱到強(qiáng)，實(shí)例計(jì)算中所用集裝箱尺寸為587 cm×233 cm×220 cm。通過Python程序分別對(duì)7組算例進(jìn)行計(jì)算，算例結(jié)果如表1所示。

由表1對(duì)比可知，異構(gòu)性逐漸增強(qiáng)，體積利用率也不斷增加，且計(jì)算時(shí)間較短并基本保持不變。

表1 BR1～BR7計(jì)算結(jié)果

對(duì)于OR-Library(http://people.brunel.ac.uk/～mastjjb/jeb/or-lib/thpackinfo.html)中國際裝箱數(shù)據(jù)的700個(gè)算例，許多學(xué)者也對(duì)其進(jìn)行過測試。比較的算法包括混合模擬退火算法(hybrid simulated annealing，HSA)[22]、可變鄰域搜索算法(variable neighborhood search，VNS)[23]、最新的基于整數(shù)拆分的樹狀搜索算法(container loading by tree search，CLTRS)[24]、FDA(fit degree algorithm)算法[25]以及多層啟發(fā)式算法(multi-layer heuristic search，MLHS)[26]。上述不同算法計(jì)算了BR1～BR7貨物裝入集裝箱的集裝箱體積利用率。自適應(yīng)權(quán)重POS算法(adaptive weighting particle swarm optimization，AWPOS)、標(biāo)準(zhǔn)POS(particle swarm optimization，POS)、遺傳算法(genetic algorithm，GA)[15]以及混合模擬退火算法(HSA)[22]計(jì)算了BR1～BR7的貨物裝入集裝箱的集裝箱體積利用率和計(jì)算時(shí)間。表2與表3分別為各算法BR1～BR7裝入集裝箱的集裝箱利用率比較和利用率與計(jì)算時(shí)間比較，如圖3所示為各算法對(duì)BR1～BR7的計(jì)算時(shí)間對(duì)比。

從表2可以看出，EFDT-HS的利用率雖然沒有達(dá)到最優(yōu)但始終保持增加的良好趨勢(shì)。

由表3對(duì)比可知，本算法利用率在保持良好狀態(tài)下，時(shí)間大幅度縮減。可見，本算法在保證貨物裝載率的情況下，實(shí)現(xiàn)了快速裝箱。

表2 各算法BR1～BR7的集裝箱利用率比較

表3 各算法BR1～BR7集裝箱利用率及計(jì)算時(shí)間比較

圖3 計(jì)算時(shí)間對(duì)比Fig.3 Caculate time comparison

從圖3可知，本算法需要的時(shí)間比起自適應(yīng)權(quán)重POS算法(AWPOS)、標(biāo)準(zhǔn)POS(POS)、遺傳算法(GA)以及混合模擬退火算法(HSA)這四種算法所需的時(shí)間幾乎可以忽略不計(jì)，已經(jīng)達(dá)到目前裝箱效率最優(yōu)。

通過不同算法對(duì)7組數(shù)據(jù)的比較結(jié)果來看，本文算法的利用率雖沒有達(dá)到最優(yōu)但一直保持較高狀態(tài)且呈現(xiàn)增長趨勢(shì)；在利用率與計(jì)算時(shí)間對(duì)比情況下，各算法隨著貨物異構(gòu)性的不斷增強(qiáng)計(jì)算時(shí)間不斷增加，集裝箱利用率也有所減少，而本文算法隨著異構(gòu)性的增強(qiáng)，利用率逐漸增加，計(jì)算時(shí)間一直保持在零點(diǎn)幾秒，實(shí)現(xiàn)了貨物的快速裝載，并且本算法可以對(duì)裝載結(jié)果進(jìn)行三維展示，對(duì)貨物進(jìn)行裝載后能夠看到每個(gè)貨物的裝載位置。由于實(shí)驗(yàn)數(shù)據(jù)較多，只列出BR6及BR7算例中貨物的集裝箱裝載結(jié)果圖。圖4(a)為BR6的裝載結(jié)果圖，圖4(b)為BR7裝載結(jié)果圖。

圖4 BR6及BR7裝載結(jié)果圖Fig.4 Loading result of BR6 and BR7

4 結(jié)論

極快決策樹與啟發(fā)式搜索算法的結(jié)合使用，保證了每個(gè)裝載層放入的貨物體積最大，同時(shí)實(shí)現(xiàn)了對(duì)裝入貨物后的剩余空間進(jìn)行再利用。經(jīng)過對(duì)多種不同規(guī)格貨物的測試，該算法在較短時(shí)間內(nèi)取得了良好的裝箱效果，證明了算法的有效性和可行性。本文算法中的空間合并和裝載空間再利用方法模擬了人工裝箱的過程，并通過具體的編程方法利用貨物的裝載順序確定貨物的裝載位置，實(shí)現(xiàn)了集裝箱裝載結(jié)果3D展示和動(dòng)態(tài)查看每個(gè)貨物的裝載位置的功能，為裝載過程提供了智能化方案。多規(guī)格貨物裝載的特征主要是貨物尺寸不同，不管是相鄰放入的貨物還是相鄰兩列的裝載貨物都會(huì)有類似間隙浪費(fèi)等諸多復(fù)雜的情況，更多復(fù)雜情況有待進(jìn)一步研究。