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

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

0 引言

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

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

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

1 理論建模

針對(duì)實(shí)際煙箱碼垛問(wèn)題進(jìn)行數(shù)學(xué)建模，并對(duì)一些限制條件進(jìn)行量化。整車(chē)廂為點(diǎn)集A，長(zhǎng)寬高依次為L(zhǎng)、W、H，鵝頸板尺寸依次為a、b、c。訂單順序?yàn)榧蟂j。

Sj=（li，wi，hi，nj）

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

操作集合為

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

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

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

1）任意2個(gè)煙箱不重疊，即有

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

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

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

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

2 Beam Search算法

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

圖1 Beam Search算法流程圖

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

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

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

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

圖2 簡(jiǎn)單算法垛型設(shè)計(jì)圖（無(wú)鵝頸板）

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

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

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

圖3 Empty Maximum Spaces示意

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

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

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

簡(jiǎn)單來(lái)說(shuō)，搜索過(guò)程中的狀態(tài)轉(zhuǎn)移過(guò)程是搭積木的過(guò)程，每次選擇1個(gè)空余空間、選擇由多個(gè)箱子組成的Block，然后將Block放入空余空間中并更新?tīng)顟B(tài)。

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

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

2.4 Beam Search算法狀態(tài)評(píng)價(jià)

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

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

2.5 垛型反推擺放順序

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

原則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：放入某個(gè)煙箱時(shí)，該煙箱下底面與其他煙箱或車(chē)廂底面的接觸面積之和應(yīng)大于下底面面積的90%；

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

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

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

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

2.6 研究結(jié)果分析

2.6.1 系統(tǒng)輸入

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

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

2.6.2 系統(tǒng)輸出

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)論

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