徐躍明 方錦明 劉哲賢 鄭 重 陶海旭

1紅云紅河煙草（集團）有限責(zé)任公司 昆明 650202 2昆船智能技術(shù)股份有限公司 昆明 650236 3清華大學(xué)精密儀器系 北京 100084

0 引言

隨著物流自動化的發(fā)展，智能立體倉儲和自動化分揀設(shè)備得到了廣泛應(yīng)用，但貨車運輸前的裝車過程卻仍然高度依賴人工，國內(nèi)目前暫無成熟的自動裝車系統(tǒng)。裝貨車依賴人工的主要缺點有：自動化、信息化程度低；成本高，管理難度大；效率低，很難長期保持高效率作業(yè)；缺少產(chǎn)品數(shù)據(jù)有效追溯；招工困難，愿意從事搬運行業(yè)的年輕人越來越少。除煙箱物流外，疫情之下的冷鏈物流行業(yè)對自動裝車系統(tǒng)也有同樣迫切的需求。

理論研究中把這類問題稱為集裝箱裝載問題（CLP）。集裝箱裝載問題是一個經(jīng)典的組合優(yōu)化問題：給定一些不同規(guī)格的三維箱子，將箱子的1個子集裝載進集裝箱，使得集裝箱的空間使用率最大。集裝箱裝載問題是一個NP -難的問題[1]：它是背包問題(Knapsack Problem)在三維空間上的擴展。由于背包問題本身是NP完全問題，故集裝箱裝載問題也不存在有多項式時間復(fù)雜度的算法。出于問題本身搜索空間的龐大，求解精確解的集裝箱裝載算法通常只能求解小規(guī)模的問題[2]。

Junqueira L等[3]在2012年使用混合整數(shù)線性規(guī)劃模型來求解集裝箱裝載矩形箱的最優(yōu)解，并考慮了貨物穩(wěn)定性和負(fù)載的約束。其使用優(yōu)化軟件對100多個隨機生成的實例進行了全面的性能分析[4]。計算結(jié)果驗證了這些模型，并表明它們只能夠處理中等規(guī)模的問題。該方法的問題在于計算量過大，無法適應(yīng)實際使用場景。Zhu W等[5]提出了一種分析框架來描述基于塊構(gòu)建的方法。該框架是基于大多數(shù)方法中存在的6個共同要素。(K1)容器中自由空間的表示；(K2)生成塊的機制；(K3)用于對自由空間進行排序的啟發(fā)式方法；(K4)用于對盒子進行排序的啟發(fā)式方法；(K5)用于決定如何將選定的塊放在選定的自由空間中的啟發(fā)式方法，以及(K6)整體搜索策略。Araya I等[6]在2014年基于塊構(gòu)建的方法，提出了BSG-CLP搜索策略。BSG-CLP是一種基于Beam搜索的算法，其使用基于Greedy的函數(shù)來評估搜索圖中的狀態(tài)。Beam搜索可被看作是對分支和邊界搜索的改編，在搜索圖的每一層只擴展最有希望的節(jié)點的子集[7]。綜上所述，針對成品煙箱自動裝車系統(tǒng)垛型算法選擇基于塊構(gòu)建的Beam搜索算法。

1 理論建模

針對實際煙箱碼垛問題進行數(shù)學(xué)建模，并對一些限制條件進行量化。整車廂為點集A，長寬高依次為L、W、H，鵝頸板尺寸依次為a、b、c。訂單順序為集合Sj。

Sj=（li，wi，hi，nj）

式中：j為第j個訂單；li，wi，hi為該品種煙箱長、寬、高；nj為數(shù)量。

操作集合為

式中：Vj，k為煙箱，1≤k≤nj；xj，k，yj，k，zj，k為左下頂點坐標(biāo)。

優(yōu)化目標(biāo)為

下面給出了5點垛型設(shè)計數(shù)學(xué)模型中最基本的限制條件：

1）任意2個煙箱不重疊，即有

2）不同種類的煙箱盡可能依照順序從里向外從下向上擺放，即有

3）煙箱包含在車內(nèi)，即有

4）一次碼放的煙箱只能在一橫排上。即有

5）碼放煙箱的平均時間小于閾值，即有

2 Beam Search算法

一般的搜索過程中，每一個狀態(tài)都會拓展出很多個新狀態(tài)，新狀態(tài)又會拓展新的狀態(tài)。如果采用全局搜索的方法，計算開銷和狀態(tài)的存儲開銷非常大。而采用Beam Search的算法，例如在搜索寬度是2的情況下，對初始狀態(tài)拓展出2×2=4個新的狀態(tài)，對這4個新狀態(tài)分別做出評價，然后取評價最高的2個狀態(tài)，分別各拓展出2個新狀態(tài)；再對4個新狀態(tài)進行評價，以此類推。因此，Beam Search的計算量遠(yuǎn)小于全局搜索，且通過調(diào)整搜索寬度又可保證一定的搜索空間，通過狀態(tài)評價來盡可能地趨近較優(yōu)解。Beam Search算法流程圖如圖1所示。

圖1 Beam Search算法流程圖

2.1 利用簡單算法對人工碼垛的復(fù)現(xiàn)

為了顯示Beam Search算法的結(jié)果并驗證其正確性，需完成1套簡單的垛型仿真平臺，在算法之外實現(xiàn)對車廂空間的還原。首先對人工碼垛的思路進行復(fù)現(xiàn)，然后再嘗試使用Beam Search等方法。

簡單算法參考人工碼垛時的經(jīng)驗，采取“碼墻”的辦法，即由內(nèi)至外一面墻一面墻的進行碼垛。具體每一面墻碼放方式為：首先將相同尺寸、相同姿態(tài)的煙箱從車廂的左下角開始盡可能地放入墻中，直到不能繼續(xù)放入。此時車廂右側(cè)或上方還可能留有部分空余空間，再將該煙箱調(diào)整姿態(tài)，盡可能地放入車廂空余空間中，直到不能繼續(xù)放入。如果該類煙箱仍有剩余，則開始下一面墻的碼放，方式同上。如果該類煙箱在上述擺放過程中就已經(jīng)放完，則開始下一品規(guī)煙箱的擺放，方式同上。依次類推，直到將車廂擺滿或者煙箱被全部放入。當(dāng)同一面墻中擺入了不同品規(guī)的煙箱時，其不同位置處的厚度不一樣，取每面墻的最大厚度為該面墻厚度。下一面墻將從最大厚度處開始碼放，故墻與墻之間可能會存在空余空間。

通過實際訂單情況的檢驗，簡單算法在設(shè)計平板車垛型時一般也能達(dá)到較高的空間利用率，且簡單算法所設(shè)計出的垛型結(jié)構(gòu)簡單，易于裝車。但由于墻與墻之間可能存在一定的空余空間（見圖2），運輸過程中垛型容易發(fā)生滑移甚至部分倒塌，其穩(wěn)定性不夠。且無法針對鵝頸板長度調(diào)整垛型設(shè)計，難以適應(yīng)鵝頸板車的情況。故嘗試使用Beam搜索的方式來設(shè)計垛型。

圖2 簡單算法垛型設(shè)計圖（無鵝頸板）

2.2 Beam Search算法狀態(tài)表示

搜索過程中的狀態(tài)由4個基本部分組成：1）剩余箱子的集合Remaining Boxes，即還有哪些箱子需要被放入車廂；2）空余空間的集合 Empty Spaces，即還有哪些地方可以放箱子；3）當(dāng)前可選的煙箱塊Available Blocks；4）已經(jīng)碼放完成的箱子順序和位置的記錄Moves。最難表示的是空余空間集合。

如圖3所示，把1個立方體放入空的立方體空間后，剩余的空間是不規(guī)則的立體圖形。使用重疊的長方體集合（Empty Maximum Spaces）：對每個箱子，以其1個面為分界面，向空的方向最大延伸的長方體。如圖3a中的空余空間可由圖3b～圖3d中3個透明空間表示。

圖3 Empty Maximum Spaces示意

具體到算法中，圖4中的紫色透明長方體就是從已經(jīng)碼放好的箱子的面上向外延伸的最大的空長方體。

圖4 實際狀態(tài)中的剩余空間表示

2.3 Beam Search算法狀態(tài)拓展

簡單來說，搜索過程中的狀態(tài)轉(zhuǎn)移過程是搭積木的過程，每次選擇1個空余空間、選擇由多個箱子組成的Block，然后將Block放入空余空間中并更新狀態(tài)。

在選擇空余空間時采用加權(quán)曼哈頓距離對可選空間進行評價排序，取出優(yōu)先級最高的空間。加權(quán)曼哈頓距離為：distance=w_1X+Z+w_2Y；其中，w_1

在選定待放入煙箱和空余空間后需要對狀態(tài)進行更新。從剩余箱子的集合中減去Block包含的箱子，從空余空間集合中刪掉放入箱子的空間，并加入新產(chǎn)生的空間，其中需要處理空間相互包含的情況，同時如果前面選擇了空余空間后遍歷所有塊都無法放入，則刪除該空間，如果煙箱塊需要的煙箱數(shù)量大于剩余煙箱，則在可選的煙箱塊集合中刪除該塊，最后在Moves中記錄下這步操作，完成狀態(tài)拓展過程。

2.4 Beam Search算法狀態(tài)評價

在Beam Search的過程中，每拓展一些新狀態(tài)，就要對新狀態(tài)進行一次評價，以挑選出當(dāng)前認(rèn)為最好的幾個狀態(tài)。采用的評價過程為：使用貪心算法來得到完整解，即從當(dāng)前狀態(tài)出發(fā)進行搜索寬度為1的搜索，不斷拓展?fàn)顟B(tài)直到車廂被放滿。然后使用該完整解的空間利用率作為當(dāng)前狀態(tài)的評價。

該方法可在搜索算法全部完成前就先得到完整解，多數(shù)情況貪心算法得到的完整解效果也能滿足實際需求。

2.5 垛型反推擺放順序

在設(shè)計完成垛型后，算法還需指導(dǎo)自動裝車完成碼垛工作，故需根據(jù)垛型來反推不同位置煙箱的碼放順序與位置。碼放順序原則為：

原則1：煙箱1左下坐標(biāo)（x1，y1，z1），煙箱2左下坐標(biāo)（x2，y2，z2）。若x1＜x2，則煙箱1先于煙箱2碼放；若x1=x2，z1＜z2，則煙箱1先于煙箱2碼放；若x1=x2，z1=z2，y1＜y2，則煙箱1先于煙箱2碼放。

原則2：放入某個煙箱時，該煙箱下底面與其他煙箱或車廂底面的接觸面積之和應(yīng)大于下底面面積的90%；

原則1保證了已放入的煙箱不會對機械裝置發(fā)生干涉，原則2保證了裝入的煙箱具有足夠的支撐。此外，由于自動裝車的設(shè)計為每次可放入1排若干個煙箱，為了提高裝車效率，應(yīng)盡可能每次將處在同一排的煙箱一起放入。算法流程如下：

1）先將垛型中所有煙箱按照原則1排定擺放順序，從先到后編號為1～N；

2）i=1～N，依次考慮第i個煙箱時，依據(jù)原則2判斷能否放入，若不能放入則進入等待序列；若能放入則進入擺放序列，并將等待序列中重新滿足原則2的煙箱進入擺放序列。

上述流程可滿足擺放要求，但會出現(xiàn)處于同一層的可一次性放入的煙箱順序被分散在擺放序列中。為了提高效率，在上述流程的第二步中，加入重新考慮等待序列的前提條件：當(dāng)自動裝車恰好可以一次性放入其能力極限的煙箱個數(shù)時，再考慮等待序列中的煙箱能否進入擺放序列。

2.6 研究結(jié)果分析

2.6.1 系統(tǒng)輸入

系統(tǒng)輸入為裝有煙箱訂單數(shù)據(jù)的Excel表格，如表1所示。

表1 訂單數(shù)據(jù)表

2.6.2 系統(tǒng)輸出

根據(jù)車輛有無鵝頸板及訂單中煙箱總量是否超出單車裝載能力，系統(tǒng)的輸出可分為多種情況。圖5～圖8展示的4種垛型效果圖為：車輛無鵝頸板且訂單中煙箱總量超出單車裝載能力；車輛有鵝頸板且訂單中煙箱總量超出單車裝載能力；車輛無鵝頸板且訂單中煙箱總量小于單車裝載能力；車輛有鵝頸板且同品規(guī)煙箱集中放置。

圖5 垛型效果圖（無鵝頸板、訂單中煙箱總量超出單車裝載能力）

圖5最外側(cè)大長方體代表1個車廂，單個小立方體代表單個煙箱，同種顏色的小立方體代表同一訂單中同一品規(guī)的煙箱，圖6中左下角深藍(lán)色部分和圖8中右下角白色部分代表車輛鵝頸板。當(dāng)訂單中煙箱總量超出單車裝載能力時，系統(tǒng)會以車廂空間利用率盡可能高為目標(biāo)進行垛型設(shè)計。當(dāng)訂單中煙箱總量低于單車裝載能力時，系統(tǒng)會在保證訂單中煙箱全部裝入車廂的基礎(chǔ)上考慮垛型在運輸過程中的穩(wěn)定性，如圖7所示。

圖6 垛型效果圖（有鵝頸板、訂單中煙箱總量超出單車裝載能力）

圖7 垛型效果圖（無鵝頸板、訂單中煙箱總量小于單車裝載能力）

圖8 垛型效果圖（有鵝頸板、同品規(guī)集中放置）

3 參數(shù)測試與系統(tǒng)穩(wěn)定性測試

3.1 系統(tǒng)參數(shù)測試

系統(tǒng)的評價函數(shù)中有許多超參數(shù)，例如評價過程中各影響部分的權(quán)重值，需要通過實驗確定其最佳取值。

表2和表3為評價函數(shù)中各參量不同取值對實驗結(jié)果的影響。其中a1為相鄰面積權(quán)重，a2為單個Block中煙箱個數(shù)權(quán)重，p為計算相鄰面積時的距離系數(shù)，Search width為搜索寬度。

表2 參數(shù)取值對結(jié)果的影響

表3 參數(shù)取值對結(jié)果的影響

從實驗結(jié)果中可知，當(dāng)a1=3，a2=0.04，p=0.04時，相同情況下車廂的空間利用率最高。

3.2 系統(tǒng)穩(wěn)定性測試

對于不同的訂單數(shù)據(jù)，程序運行結(jié)果呈現(xiàn)出一定的差異性，總體來看，程序?qū)Σ煌唵屋斎攵加休^好的效果，能滿足實際需求。從表2和表3可知，程序在不同數(shù)據(jù)輸入的情況下運行240 s左右設(shè)計出的垛型能達(dá)到92.5%以上的空間利用率。同時根據(jù)實際需求，一般要求裝車垛型至少達(dá)到90%的空間利用率，通過表4和表5可知，程序在不同數(shù)據(jù)輸入的情況下最長需要134 s達(dá)到該標(biāo)準(zhǔn)，對于某些特定訂單只需60 s左右即可滿足要求。表6展示了當(dāng)空間利用率要求提高至93%時程序?qū)τ诓煌唵螖?shù)據(jù)所需要的運行時間。

表4 程序在相同參數(shù)下對不同訂單數(shù)據(jù)運行240 s左右結(jié)果（有鵝頸板）

表5 程序在對不同訂單數(shù)據(jù)達(dá)到90%空間利用率所需最短時間（有鵝頸板）

表6 程序?qū)Σ煌唵螖?shù)據(jù)達(dá)到93%空間利用率所需最短時間（有鵝頸板）

圖9和圖10依次展示了程序在不同搜索寬度下的垛型空間利用率隨時間變化曲線和程序?qū)τ诓煌唵屋斎胂碌亩庑涂臻g利用率隨時間變化曲線。

圖9 無鵝頸板不同搜索寬度下空間利用率隨時間變化曲線

圖10 不同訂單數(shù)據(jù)空間利用率隨時間變化曲線

由圖可知，不同搜索寬度下程序運行結(jié)果存在較大差異，當(dāng)Search width取值大于3時總體效果較好。同時對于不同訂單信息輸入，程序的運行結(jié)果也存在一定的差異，但都能夠滿足90%空間利用率以上。

4 結(jié)論

基于Beam Search算法建立成品煙箱自動裝車系統(tǒng)算法的數(shù)學(xué)模型，通過簡單算法的仿真平臺顯示Beam Search算法的結(jié)果并驗證其正確性。通過參數(shù)測試得出當(dāng)a1=3，a2=0.04，p=0.04時，相同情況下車廂的空間利用率最高。通過系統(tǒng)穩(wěn)定性測試得出，不同搜索寬度下程序運行結(jié)果存在較大差異，當(dāng)Search width取值大于3時總體效果較好。同時對于不同訂單信息輸入，程序的運行結(jié)果也存在一定的差異，但都能夠滿足90%空間利用率以上。