李 偉，楊超宇，孟祥瑞

(安徽理工大學 經濟與管理學院，安徽 淮南，232001)

貨物裝載是物流運輸中至關重要的一部分，高效的裝載不僅可以降低運輸成本還能縮短裝箱時間.從物流運輸業(yè)興起到現(xiàn)在，已有很多國內外學者利用各種方法研究三維裝箱問題.

Gon?alves[1]提出的有偏隨機密鑰遺傳算法，通過利用箱內的空閑空間提高了箱子的利用率；Yang等[2]和Hifi等[3]利用整數線性規(guī)劃的啟發(fā)式策略求解三維裝箱問題；Jonas等[4]在決策支持系統(tǒng)中應用兩級元啟發(fā)式方法縮短交貨時間和減少貨物損壞風險；張德富等[5]提出求解三維裝箱的混合模擬退火算法，提高了集裝箱的利用率；楊廣全等[6]基于遺傳算法原理，設計啟發(fā)式遺傳算法，實現(xiàn)集裝箱裝車配載的智能化；那日薩等[7]提出了一種基于“塊”和“空間”的啟發(fā)式搜索算法，在時間效率和體積利用率均有所提高；劉勝等[8]提出了啟發(fā)式二叉樹搜索算法，裝箱率有顯著提高；朱瑩等[9]提出一種結合啟發(fā)式算法和遺傳算法的混合遺傳算法；田維等[10]利用整數規(guī)劃方法對裝箱問題進行快速準確求解；張雅艦等[11]提出了一種改進的遺傳算法，使得到最優(yōu)解的概率更大；李俊等[12]基于兩階段分層求解思想設計SWO-HES兩階段算法，并驗證了該算法的有效性；廖星等[13]采用自適應權重法改進了粒子群優(yōu)化算法，大幅加快了計算速度；范霽月等[14]采用一種基于自適應細菌覓食算法提高了集裝箱利用率；鄭斐峰等[15-18]通過遺傳算法與貪婪策略對比得到遺傳算法在求解集裝箱裝載時結果更優(yōu)；李孫寸等[16]用多元優(yōu)化算法實現(xiàn)三維裝箱問題得到了理想的結果；尚正陽等[17]利用三維的剩余空間最優(yōu)化算法實現(xiàn)裝箱問題的快速求解.

現(xiàn)實生活中，人們的需求各有不同，這就涉及到多規(guī)格貨物的混合裝載問題.為了保證貨物的高效運輸，本文提出了一種啟發(fā)式隨機森林算法，旨在保證集裝箱利用率的同時，縮短集裝箱的裝載時間.

1 問題描述

多規(guī)格貨物裝載是指將尺寸不一的貨物裝載到同一集裝箱中的過程.為使本文研究目標更直觀，我們將目標描述如下：

給定一個集裝箱容器C和一系列待裝貨物的集合B，假設集裝箱和待裝貨物均為長方體.集裝箱的長為L，寬為W，高為H，體積V=LWH；每個待裝貨物bi的長為li，寬為wi，高為hi，體積vi=liwihi.我們的目標是利用集合B生成K個訓練集Bi，每個訓練集Bi的目標是在Bi中尋找一個子集F，使得集裝箱C的空間利用率最大.通過對訓練集的求解，可以得到K個集裝箱的空間利用率，對K個利用率進行求和平均來得到容器C在集合B情況下的利用率.即

maxfitness=VF/V=∑liwihi/V

{B1,B2,…,Bi}∈B

2 EFDT-HS隨機森林算法

本文算法是在隨機森林中CART樹構造部分融合了極快決策樹(Extremely Fast Decision Tree，簡稱EFDT)和啟發(fā)式搜索算法(Heuristically Search，簡稱HS)形成了基于EFDT-HS的隨機森林算法，此算法首先利用Bagging方法生成T個訓練集，對每個訓練集要求在特征集中隨機選取K個特征組成新的特征集，將新特征集中的最優(yōu)特征作為分割特征，利用分割特征計算并擇優(yōu)選取樣本信息熵，然后構建生成貨物裝箱決策樹模型，最后基于啟發(fā)式搜索方法對貨物裝載后的剩余空間進行合并再利用.

2.1 隨機森林算法

隨機森林是集成學習下的產物，是將許多棵決策樹整合成森林，用來預測最終結果.簡單來說，隨機森林= Bagging算法 + CART決策樹.

2.1.1 Bagging算法

Bagging算法是模型融合的方法，可以將弱分類器融合之后形成一個強分類器，且融合之后的效果會比最好的弱分類器更好.算法過程如下：

Step1.從原始數據集中抽取訓練集.每輪從原始數據集中有放回的隨機抽取n個訓練樣本.共進行T輪抽取，得到T個訓練集.

Step2.每次使用一個訓練集得到一個模型，T個訓練集得到T個模型.

2.1.2 融合EFDT的CART決策樹

本文在CART樹構建時引用極快決策樹的擇優(yōu)思想，在集裝箱裝載時，把每個數據集的裝載看做一棵樹的形成，把每個要放入的箱子看做一個葉節(jié)點，在滿足條件約束的情況下，選擇對應分割特征信息熵最大的箱子裝入.

1)最優(yōu)特征選擇方法

線性回歸損失函數是以最小化離差平方和的形式給出的，回歸樹使用的度量標準也是一樣的，通過最小化殘差平方和作為判斷標準，公式如下：

Yi為樣本目標變量的真實值，R1,R2為被劃分的兩個子集，C1,C2為R1,R2子集的樣本均值，j為當前的樣本特征，s為劃分點.

2)極快決策樹節(jié)點選擇

極快決策樹是HATT(Hoeffding AnyTime Tree)的系統(tǒng)實現(xiàn)[19].HATT使用Hoeffding不等式來確定在最佳屬性上進行拆分的優(yōu)點是否超過沒有拆分的優(yōu)點，或者當前拆分屬性的優(yōu)點.在實踐中，如果一個節(jié)點上不存在分裂屬性，那么當最優(yōu)候選屬性的性能超過次優(yōu)候選屬性時，HATT將在最優(yōu)候選屬性帶來的信息增益為非零且具有所需的置信度時進行拆分，而不是只在最優(yōu)候選屬性的性能優(yōu)于次優(yōu)候選屬性時進行拆分.且當當前最優(yōu)屬性和當前拆分屬性之間的信息增益差異非零時，HATT將進行分割，并假設這比沒有分割要好.

總而言之，EFDT是通過計算樣本數據中每個樣本的信息值，在滿足Hoeffding不等式的前提下選擇相對上一節(jié)點信息增益不為零且在樣本中信息增益最大的節(jié)點為葉節(jié)點，即擇優(yōu)選取.

2.2 啟發(fā)式算法

本文在利用多種貨物相互組合使空間利用達到最優(yōu)思想的同時，考慮到放入的貨物的寬度和高度會小于上一裝載的貨物，于是在貨物裝箱過程中考慮了“空間合并”和“裝載空間再利用”的啟發(fā)式算法.

2.2.1 空間合并

上文提到要將每一層的裝載看作一棵樹的形成，在每一層的裝載中都可能會有剩余的長度，為了充分利用每一層的剩余長度，本文采用了上下剩余空間合并的方法.

如圖1所示，上下空間合并分為三種情況：

圖1 上下空間合并

1)當前裝載層的剩余長度大于上一裝載層的剩余長度，即圖1第一個圖.在這種情況下，我們以較短的上一裝載層的剩余長度為剩余空間的最大長度，以這一裝載列最底層根節(jié)點的寬度為最大寬度，以要合并的兩層裝載空間根節(jié)點的高度之和為最大高度.

2)當前裝載層的剩余高度小于等于上一裝載層的剩余長度，即圖1第二個、第三個圖.在這種情況下，我們以較短的當前裝載的剩余長度為剩余空間的最大長度，以這一裝載列最底層根節(jié)點的寬度為最大寬度，以要合并的兩層裝載空間根節(jié)點的高度之和為最大高度.

2.2.2 裝載空間再利用

由于是多規(guī)格貨物裝載，很有可能出現(xiàn)上一個裝載貨物要比下一個裝載貨物寬或者高，于是本文提出了裝載空間再利用的想法，目的是盡可能的把空閑空間利用起來.

如圖2所示，裝載空間再利用分為兩種情況：

圖2 上部剩余空間利用、平行剩余空間利用

1)當前裝入的貨物高度小于上一裝載貨物的高度，即圖2左圖所示，在這種情況下，我們以當前放入貨物的長度為最大長度，以當前裝載層根節(jié)點的寬度為最大寬度，以當前裝載層根節(jié)點與當前放入貨物的高度差作為待利用空間的最大高度.

2)當前裝入的貨物寬度小于上一裝載貨物的寬度，即圖2右圖所示，在這種情況下，以當前裝載層根節(jié)點與當前裝入的貨物的寬度差作為最大寬度，以當前裝入貨物的長度作為最大長度，以當前裝載層根節(jié)點的高度作為最大高度.

2.3 EFDT-HS隨機森林算法在多規(guī)格貨物裝載中的應用

將集裝箱看做三維坐標系，假設x軸為集裝箱的長，y軸為集裝箱的寬，z軸為集裝箱的高，從集裝箱最里面靠左開始裝載，先沿x-z面進行裝載，x-z面裝載完成后再沿y軸增加一列繼續(xù)沿x-z面進行裝載.每個裝載函數的決策樹節(jié)點選取時都選擇劃分特征對應信息增益最大的貨物.以底層裝載函數為例.

2.3.1 底層裝載函數

底層裝載，即此時裝載層的長度占用為0，高度占用也為0的情況，反映到坐標系中即為X=0，Z=0的情況.底層裝載函數步驟如下：

Step 1.初始裝箱，選取待裝貨物中最優(yōu)特征值最大的貨物作為裝入的第一個貨物，作為根節(jié)點.讀取此貨物的長寬高，計算當前裝載層的剩余長度、最大寬度、最大高度、剩余寬度.

Step 2.在剩余待裝貨物中取出符合剩余長度、最大寬度、最大高度的箱子，計算這些箱子的最優(yōu)特征值，并按照箱子編號和對應最優(yōu)特征值降序排列.取最優(yōu)特征值最大的箱子裝入.在裝入每層非第一個箱子后，都判斷裝入箱子的上部空余空間和平行剩余空間是否還能放入箱子.(箱子可旋轉)

Step 3.更新此裝載層的剩余長度，重復步驟Step2，直到沒有滿足的箱子.

Step 4.返回裝箱結果、待裝貨物、此裝載層的最大寬度、剩余空間的長度、集裝箱剩余高度、集裝箱的剩余寬度.

2.3.2 算法的綜合應用

Step 1.讀取待裝貨物數據，將其轉化為要求的格式.

Step 2.利用Bagging方法在原始數據中有放回的隨機抽取組數據集，每組個數與原始數據個數相同.

Step 3.讀取特征集D，將其轉化為要求的格式.

Step 4.讀取Step 2生成的數據集Ti，i=1,2,…,T,并在步驟Step 3讀取的特征集中隨機不重復的選取K個特征，K

Step 5.對于數據集Ti根據最優(yōu)特征選擇相應的裝載方法，形成一棵決策樹Mi.

Step 6.重復Step 4、Step 5T次，得到T棵決策樹.聚合這T棵決策樹，得到預測結果：

3 實例計算與結果分析

本文基于Python程序實現(xiàn)了該算法，為驗證本文提出方法的有效性，采取OR-Library[20]中BR1～BR10十個算例數據進行測試，十個算例中每個算例包含100個子算例且每個子算例箱子種類數分別為3、5、8、10、12、15、20、30、40、50，異構性從弱到強，實例計算中所用集裝箱為國際標準集裝箱，尺寸為587 cm×233 cm×220 cm.通過Python程序分別對十組算例進行計算，算例結果如表1所示.

由表1可知，隨著貨物異構性不斷增強，集裝箱的空間利用率不斷增加，同時，隨著決策樹個數的增加，算法的計算時間也在緩慢增長.

表1 BR1～BR10計算結果

對于BR1～BR10這1 000個算例，許多國內外學者對其進行過測試，本文對文獻[21]提出的貪心隨機自適應搜索算法(GRASP)、文獻[22]提出的貪心隨機自適應搜索算法(Maximal-space)、文獻[5]提出的禁忌搜索算法(HSA)、文獻[23]提出的貪心隨機自適應搜索算法(CLTRS)、文獻[24]提出的提出的多層啟發(fā)式搜索算法(MLHS)、文獻[25]提出的FDA算法、文獻[16]提出的多元優(yōu)化算法(MOA)等比較經典的算法得到的裝箱結果進行比較分析，集裝箱利用率比較結果如表2所示.

表2 各種算法的集裝箱利用率比較

各算法集裝箱利用率對比圖如圖3所示.

圖3 各算法集裝箱利用率比較

從圖3和表2可知，各算法隨著貨物種類的增加，集裝箱的利用率呈下降趨勢，而本文算法的集裝箱利用率成上升趨勢，且一直保持較高狀態(tài)，由此可見，本文算法在求解多規(guī)格貨物裝載中具有一定優(yōu)勢.

時間對比圖如圖4所示.

各種算法的計算時間對比如表3所示.

由圖4和表3可知，隨著待裝貨物種類的增加，各算法的計算時間大幅度增加，而本文算法的計算時間呈緩慢增長趨勢，在各算法的計算時間中一直保持最低狀態(tài).由此可見，該算法可以有效縮短計算時間，進而減少貨物的裝載時間，減少時間成本.

圖4 各算法計算時間對比

表3 各算法的計算時間結果比較

4 結 語

隨著裝箱問題的深入研究，集裝箱的利用率不斷升高，算法的計算時間也不斷延長，如何在保證較高集裝箱利用率同時，縮短計算時間受到大家越來越多的關注.本文通過改進隨機森林算法中CART樹的構造方法，將極快決策樹思想融合進CART樹中.在決策樹的構造過程中保證每個節(jié)點劃分特征對應的信息增益值最大，在每個貨物裝載后利用啟發(fā)式搜索算法對剩余空間進行再利用，有效解決了空間浪費的問題.利用隨機森林算法集合多棵不同裝載方法下的決策樹，更能保證集裝箱利用率的準確性.通過對算例BR1～BR10的計算比較，雖然本文算法在弱異構貨物中的集裝箱利用率不占優(yōu)勢，但在強異構貨物裝載過程中，相較于MOA算法，BR10的集裝箱利用率為91%只比本文算法高出1%，而本文算法卻將其平均求解時間由1 380.62 s降低到76 s.

從實際情況來看，人們的需求不斷增多，需要運輸的貨物種類也在不增加，本文提出的啟發(fā)式隨機森林算法主要針對多規(guī)格強異構貨物的裝載，符合現(xiàn)實生活的發(fā)展趨勢.