基于動態四叉樹搜索的民航行李車碼放算法

2023-01-12 11:47:38邢志偉侯翔開李彪張濤文濤

北京航空航天大學學報 2022年12期

邢志偉, 侯翔開, 李彪, 張濤, 文濤

(1. 中國民航大學航空工程學院, 天津 300300; 2. 中國民航大學電子信息與自動化學院, 天津 300300;3. 中國民用航空局第二研究所工程技術研究中心, 成都 610041)

航空行李裝卸與運輸是機場運行保障的重要環節之一。目前,中國機場行李碼放裝卸仍以人工作業為主,存在效率低、空間浪費大等問題;少數大型機場高價購買國外行李碼放系統,每年維護費用高昂。因此,民航行李碼放的智能化與自主化將是中國民航行李處理的發展趨勢。而行李系統的核心問題是其內部嵌入的碼放算法。

民航行李車碼放算法的本質某種程度來說可視為三維裝箱算法,是典型的NP-hard 問題,此類問題在Dyckhoff[1]與W?scher[2]等的關于切割和布局問題的綜述中有詳細的論述。在Bortfeldt 和W?scher[3]更詳細的分類中,行李車碼放算法可被具體分入SKP(single knapsack problem) 問題。Fanslau 和Bortfeldt[4]將其按解決方法類型分為3 類:①經典啟發式方法。具有代表性的為George 和Robinson[5]首次提出的砌墻算法及Crainic 等[6]提出的“關鍵點”算法。此類算法運算簡單、速度快,但空間利用率不夠理想,缺乏對穩定性的考慮,屬于早期算法,是之后絕大多數算法的基礎。 ②元啟發式算法。將模擬退火算法、遺傳算法等融入啟發式算法得以形成。文獻[7-9]中利用模擬退火算法通過不斷跳出局部最優改善碼放方案;文獻[10-13]利用遺傳算法找到組合最優解,其中,文獻[13]的在線裝箱算法更有利于解決現實問題;文獻[14]運用了禁忌搜索算法;文獻[15]運用了螢火蟲算法。此類算法結果利用率高,但往往迭代次數多,運算速度慢。③樹搜索算法。文獻[4,16-20]是基于樹搜索的三維裝箱問題求解算法,以樹搜索的思想選擇不同階段的碼放方案。此類算法計算速度快、空間利用率高,但容易在搜索過程中因選擇條件單一產生局部最優。

部分學者從現實應用的角度設計了相應的算法。例如,文獻[21]對施加方向約束的大型集裝箱裝載問題開展了研究,算法更側重于集重類貨物裝載;文獻[22]專注于解決物流中的打包問題;文獻[23]為港口集裝箱優化了配載方案。可見,即使是針對現實約束的三維裝箱算法,也大都集中于各類集裝箱或大型車輛的裝載,缺乏面向航空空間約束的民航行李運輸研究。

因此,本文提出了一種以民航行李車裝載為背景,結合四叉樹搜索、動態規劃與動態選擇算法的民航行李車碼放算法,并通過實際行李構型數據和同類算法的對比驗證了算法的實用性。

1 問題描述

1.1 數學模型

如圖1 所示,民航行李車的長、寬、高分別為L、W、H,體積為V。以民航行李車右后下點為原點,底面為xy平面,垂直底面向上方向為z軸建立坐標系。行李的長、寬、高分別為l、w、h,其體積為v,如圖2 所示。 (xi,yi,zi)、(x′i,y′i,z′i)為行李i右后下、左前上坐標。給定行李車和一批待裝入行李B={b1,b2,…,bn},ηi為判斷行李是否裝入的決策變量,若行李i已裝入行李車,則ηi=1。裝載要求為:在滿足實際約束的情況下,得到使行李車空間利用率最大的碼放方案。據此,目標函數如下:

圖1 民航行李車示意圖Fig.1 Schematic diagram of luggage cart for civil aviation

圖2 行李擺放姿態Fig.2 Luggage placement

1.2 假設條件

基于航空行李的實際裝載過程提出如下假設:

1) 形狀均為長方體。

2) 在最大承重范圍內可接受多層裝載。

3) 不考慮裝載過程中出現的擠壓變形。

4) 密度均勻,重心位于其幾何中心。

1.3 約束條件處理

航空行李裝載有其自身獨特的特點,如民航旅客行李平均價值高、對運輸損失的容忍度低、裝卸速度關系著旅客值機時間等。這些特點決定了行李裝載獨特的空間約束。因此,針對民航行李車碼放問題,可以定義為:在行李集合中選出一個子集碼放入行李車中,使行李車空間利用率最大,并滿足以下約束條件:

1) 邊界約束。碼放在行李車中的所有行李都必須完全包含在行李車內,即

2) 不重疊約束。所有行李不得與其他行李存在重疊的部分,即

或

式中:“∨”代表“或”或者并集。

3) 方向性約束。所有行李只可以以最短邊為垂直高度碼放,即

4) 穩定性約束。碼放的行李受到其他行李頂面或行李車底部完全支撐,即當行李i放置于行李j之上時滿足:

式中:“∧”代表“且”或者交集。

5) 完全切割約束。碼放后形成的碼放塊可以通過多個豎直的平面分割成多個豎層,每個豎層可以通過多個水平的平面分割為最終的行李。所有用于分割的豎直平面與水平平面不能與對應的碼放塊中的行李相交,即

不存在。

2 動態四叉樹搜索碼放算法

2.1 算法原理

算法以四叉樹為基本框架,在每層設計固定數量節點以提高搜索速度。算法碼放界限為民航行李車C,其包含行李車的三維屬性為長、寬、高,C= (L,W,H)。

算法搜索過程中的節點對應碼放方案con,每層n個。 con 中包含剩余空間F、剩余復合條集合S、所用復合層P等, con= (F,S,P)。剩余空間F是在碼放過程中對C完成碼放后的剩余空間,尺寸為x_free、y_free,F= (x_free,y_free)。四叉樹的頂點對應的碼放方案狀態為尚未開始碼放。碼放方案集合表示動態四叉樹中所有繼續搜索的節點,CON ={con1,con2,…,conn}。

以四叉樹頂點即空碼放方案為起始開始搜索,在碼放方案中添加一個復合層pi生成新碼放方案。pi是通過將復合條sj以相同的姿態沿x軸或y軸碼放生成的。pi的x、y方向尺寸為其底面的最小外包矩形對應尺寸,高度為H。復合條sj是將多個行李b以動態規劃的算法沿z軸碼放得到的行李組合,如圖3 所示。定義sj尺寸為其最小外包長方體尺寸,高度為H。sj=(Q,l_sj,w_sj)。其中,Q為包含b的集合,l_sj為sj的長,w_sj為sj的寬。行李bi包含行李的三維屬性長、寬、高,bi=(li,wi,hi)為碼放算法中的最小單元。

圖3 復合條生成示意圖Fig.3 Schematic diagram of compound bar generation

生成的sj以填充率fr_sj作為篩選的標準。fr_sj為sj內行李實際體積與定義體積的比值,計算公式如下:

式中:vs為復合條內行李的體積。

以所有行李生成復合條集合S= {s1,s2,…,sn},并通過動態規劃算法組合sj生成pi。定義d為復合層的形狀變量,代表不同復合層形狀,d=1,2,3,4,如圖4 所示。pi= (K,xl_pi,yl_pi,d),其中,K為包含的復合條集合,xl_pi為pi在x軸方向長度,yl_pi為pi在y軸方向長度。復合層集合P= {p1,p2,…,pn} 代表碼放方案中的已碼放結果。

圖4 四種復合層示意圖Fig.4 Schematic diagram of four types of composite layers

復合層填充率fr_pi是算法搜索過程中選擇新碼放方案的標準之一,是pi內行李的實際體積與定義體積的比值,計算公式如下:

式中:vb為b的體積。

將pi放入con 即得到待選碼放方案r。r與con 結構相同,包含剩余空間、剩余復合條集合、所用復合層等,r= (F,S,P)。con 添加的復合層有4 種,故r有4n個。在算法的搜索選擇過程中,r成為新一代碼放方案或被舍棄。

同一深度的con 生成的所有r放入待選碼放方案集合R= {r1,r2,…,r4n} 中等待動態選擇算法進行遍歷選擇,選出n個作為新一代碼放方案。

如此迭代直至某個con 在算法的迭代過程中無法繼續添加復合層或所有行李碼放完成,將此碼放方案稱為最終碼放方案,將其放入最終碼放方案集合FINCON 中。

在算法開始搜索前會將S中底面積最小的一部分復合條先取出擱置,組成小型復合條集合Sl,占比為整體的25%。當con 中已碼放的復合層占據空間超過C的一半時,將放入S中參與迭代,使用“填縫”的思想提升空間利用率。

當算法中不存在可繼續搜索的碼放方案時,算法結束。取FINCON ={con1,con2,…,conk}中空間利用率最高者為算法的最終輸出結果。

2.2 算法流程

本文算法先將所有行李以動態規劃的算法沿z軸組合成s放入S中。然后,基于剩余空間生成4 種復合層,并構造四叉樹,如圖5 所示,根節點為尚未開始碼放的初始碼放方案。根據設計的動態選擇算法對四叉樹迭代搜索得到最終碼放方案。整個算法實現流程如圖6 所示,以下介紹內嵌算法。

圖5 四叉樹搜索Fig.5 Quadtree search

圖6 算法嵌套圖Fig.6 Nesting diagram of algorithm

算法1動態四叉樹搜索(dynamic quadtree search,DQS)算法。

算法為復合條生成和剩余空間裝載,得到最終碼放方案。

步驟1生成空的S、Sl、CON、R、FINCON。

步驟2調用復合條生成算法(算法5a 和5b),生成復合條并放入S中,取出其中底面積最小的前25%放入Sl。

步驟3調用剩余空間裝載算法(算法2),得到FINCON。

步驟4在FINCON 中選取空間利用率最大的碼放方案,算法結束。

算法2剩余空間裝載(loadspace)算法。

算法為迭代算法,最終得到FINCON。該算法在碼放后期利用Sl“填縫”更好地填充了剩余空間,如圖7 所示。

圖7 算法2 流程Fig.7 Flow chart of algorithm 2

算法3復合層生成算法。

根據不同碼放方案中剩余空間與剩余復合條集合的各項參數重新設定動態的最低空間利用率,提升整體利用率,保證運輸過程的穩定性(見圖8)。公式具體如下(以沿x軸碼放為例):

圖8 算法3 流程Fig.8 Flow chart of algorithm 3

式中:fr 為復合層的動態最低空間利用率;fr0為復合層最低空間利用率上限;δ為剩余復合條長度標準差;m為剩余復合條數目;ˉl為剩余復合條長度平均值;x_free 為剩余空間沿x軸方向的長度。

算法4動態選擇算法。

如圖9 所示,設計了一種基于剩余空間和剩余復合條集合雙重因子影響的動態選擇算法,并在每層選出n個繼續搜索的碼放方案。算法中存在2 個計算值,即實際浪費體積vact和潛在浪費體積vhide(見圖10)。

圖9 算法4 流程Fig.9 Flow chart of algorithm 4

圖10 兩種浪費體積示意圖Fig.10 Schematic diagram of two waste volumes

vact為r中沒能完全利用的空間體積之和,即定義體積與實際體積之差。

vhide為r中F與S匹配度不足而產生的潛在浪費空間,雖在當層的r中表現不直觀,卻深刻影響著整體利用率的高低。

計算方式如下:對r模擬新一輪的復合層生成,選取生成的4 種復合層中實際浪費體積最小者作為潛在浪費體積。

最終選擇vact與vhide之和vwaste最小的n個r作為新一輪四叉樹搜索的con。

算法5復合條生成算法。

算法包括算法5a 和算法5b。

算法5a 設定的復合條最低利用率略高于算法5b,將不滿足算法5a 行李放入算法5b 重新生成s。目的為生成更多的s以在搜索過程中增添更多組合,如圖11 所示。實驗證明,同時使用算法5a 和算法5b 比單一使用算法5a 效果更好。

圖11 算法5a 流程Fig.11 Flow chart of algorithm 5a

復合條生成算法2 與算法5a 流程相同,使用free_B代替B為總的行李集合。

算法6動態規劃算法。

利用動態規劃算法解決一維背包問題的原理,在生成復合條時將b0以上行李體積視為物品價值,高度視為物品質量,將高度H視為背包容量。用于復合層生成時與此同理,不再贅述。

3 計算實驗

動態四叉樹搜索算法實現了最終碼放方案可視化,并使用ABB 公司IRB6700 型號機械手實現現實環境驗證。算例驗證數據選取原則如下:行李車數據選取國內民航機場常規行李車尺寸,為260 cm ×135 cm ×80 cm;參照國內單航班行李處理情況,確定同一航班下70 個不同尺寸的行李箱為碼放方案輸入,各尺寸所占比例的設定依據為國內某樞紐機場自助行李托運設備信息采集系統導出的歷史尺寸數據統計分布。其中,行李箱尺寸型號判定依據為其三邊之和(如24 寸行李箱定義為三邊之和不超過136 cm,將三邊之和范圍在128 ～136 cm 之間的行李箱劃分為24 寸行李箱,1 寸=0.033 m),具體劃分比例如表1 所示,行李數量及各尺寸型號所占比例能夠在某種程度上代表機場行李車碼放輸入的常態。由于存在同尺寸行李箱的三邊長度也并不完全一致的情況,表1 給出的是各行李箱尺寸范圍。考慮到現實碼放環境中存在做工誤差、檢測誤差及行李膨脹等影響行李箱尺寸的因素,因此,為行李箱尺寸添加隨機數以反映以上因素對行李箱尺寸的影響。重復30 次實驗以驗證本文算法穩定性。隨機數區間如下:長度為[ -1,1]cm,寬度為[ -1,1]cm,高度為[ -1,3]cm。

表1 航空行李實驗數據Table 1 Experimental data of air luggage

3.1 算法對比測試

選取滿足同樣現實約束的算法對以上測試算例開展比較驗證實驗,文獻[17]的算法可滿足同樣的嚴格現實約束,故選取其中的HOBTS 算法與本文DQS 算法進行對比。

經多次實驗,DQS 算法中各項參數修正后設定如表2 所示。完成30 次碼放后,DQS 算法和HOBTS 算法的空間利用率如圖12 所示,其各項統計參數如表3 所示,其中4 次碼放方案結果如圖13 所示。

圖12 DQS 算法與HOBTS 算法結果對比Fig.12 Comparison of results between DQS and HOBTS algorithms

圖13 DQS 算法碼放的4 個結果Fig.13 Four results of DQS algorithm stacking

表2 DQS 算法參數Table 2 Parameters in DQS algorithm

表3 DQS 算法30 次運算結果Table 3 30 operation results in DQS algorithm

使用HOBTS 算法完成30 次標準民航行李車碼放后得到的空間利用率如圖12 所示,其各項統計參數如表4 所示,其中4 次碼放方案結果如圖14所示。

圖14 HOBTS 算法碼放的4 個結果Fig.14 Four results of HOBTS algorithm stacking

3.2 算法對比分析

結合圖12 與表3、表4 對比分析可知,DQS算法在本文算例中生成的碼放結果平均空間利用率為91.63%,高出HOBTS 算法16.83%,相比于目前僅50%空間利用率的人工碼放方案也表現出了足夠的優秀性。比人工碼放高的空間利用率是機場行李碼放自動化與智能化的保障,利用率越高,處理相同數目的行李箱時使用的行李車數量越少,為機場節省更多的行李車資源,提升機場資源利用率和效益。在算法穩定性的表現上,從四分位數來看DQS 算法的實驗結果更為集中,因隨機數添加所導致的結果波動更小,0.010 557 的利用率標準差低于HOBTS 算法的0.046 709,算法穩定性更好。現實碼放往往存在多種擾動使得算法無法發揮出應有的性能,優秀的算法穩定性可以使算法更好地適應復雜的現實碼放環境,從而降低擾動對算法的負面影響。

表4 HOBTS 算法30 次運算結果Table 4 30 operations results of HOBTS algorithm

DQS 算法最大的優勢在于:有針對性地根據民航行李車的碼放環境設計了算法,實現了對剩余空間更大化的利用,優化了樹搜索中局部最優的弊端。具體而言,在行李車碼放的環境中,單個行李的體積相對于整個行李車占比較大,能夠放入行李車的行李較少。因此,剩余空間能否被更有效的利用是決定整體利用率的關鍵之處。而大多數啟發式裝箱算法的結果是通過將多個碼放序列循環演化后選取最優者而得到的,演化過程往往是以隨機改變序列中的值代表的隨機性和根據算法中自帶的演化公式生成新序列代表的方向性相結合,而演化公式的意義往往與裝箱問題無關,并非是根據箱子剩余空間設計的公式,因此演化過程存在一定的盲目性,最終得到的最優解一定程度上是因為產生了足夠多不同的序列,得到了較好的結果。而DQS 碼放序列的生成是基于剩余空間的,在碼放過程中動態地分析剩余空間,并根據剩余空間與尚未碼放的行李箱匹配程度確定了當下的序列內容,每完成一次碼放重新分析一次,因此當完成碼放后的剩余空間對整體影響較大時,DQS 算法優勢明顯。以HOBTS 算法為例,其在三維裝箱算法的標準測試集中表現優秀,可以達到90%的空間利用率,然而在本文測試中只有75%的空間利用率。主要原因在于:標準測試集中箱子體積相對于整個容器較小,一個容器中可裝入約100 個箱子;碼放完成后無法繼續碼放的空間相對較小,剩余空間對整體的空間利用率影響很小。而在行李車的環境中,行李箱體積相對較大,行李車只能裝入約30 個行李箱且只能正放,完成碼放后無法繼續碼放的剩余空間對整體空間利用率的影響極大,即使剩余空間中多碼放一組行李也將極大地提高整體利用率。因此,標準測試集中結果與本文測試算例所得結果不具有相比性。

DQS 算法相對于HOBTS 算法在本文算例中的優勢及提升具體值分析如下:

1) 設計了動態選擇算法。 DQS 算法在碼放時,考慮了已碼放結果和未碼放空間雙重因素,既考慮了完成碼放部分的空間利用率,還考慮了剩余未碼放空間中是否仍能繼續保持高利用率碼放,從整體的角度選擇碼放方案。基于此,DQS算法所得方案剩余空間小于HOBTS 算法,DQS方案大多碼放復合條為12 組,而HOBTS 方案大多為10、11 組,如圖13、圖14 所示。以算例中最多的24、26 寸箱子計算可得,動態選擇算法可提升7.5% ～18.0%的空間利用率。

2) 設計了動態的最低空間利用率公式。DQS 算法在復合層的生成中可以根據剩余空間改變最低空間利用率,使得生成的復合層總體空間利用率更高且更均衡,提升空間利用率。 DQS算法中復合層空間利用率平均約為95%,HOBTS算法中空間利用率為91%,可提升約4%。

將圖13(b)的碼放方案在現實環境中碼放實驗,結果如圖15 所示。可見,在民航行李車中碼放行李的表現上,DQS 算法是有效的。

圖15 現實碼放結果Fig.15 Real-world stack result

3.3 多樣性數據實驗與分析

為進一步驗證DQS 算法的穩定性與實用性,將其應用于更多樣化的行李箱數據集合,以異構程度劃分,運算結果如表5 所示。將DQS 算法應用于三維裝箱算法的標準測試集BR1 ～BR7,并與其他約束相近算法做對比進一步驗證DQS 算法的適應性,碼放結果如表6 所示。

表5 多樣性數據集運算結果Table 5 Operation results of diverse dataset

由表5 可得,同異構等級下,隨著數據集中大尺寸行李箱的加入,平均填充率有所降低,如異構等級2 數據集中,當28、32 寸行李占比較大時,填充率顯著降低,因此該算法對中小尺寸行李箱(22、24 寸行李箱)的碼放更具優勢;隨著數據集異構性的增強,平均填充率并未降低。而當大型號行李箱的數量較少時,平均填充率反而有所提高,如異構等級4 的第3 組平均填充率為91.3%,該數據集大尺寸行李箱較少,平均填充率高于異構等級1、2、3 中大部分同樣大尺寸行李箱較少的數據集。因此,該算法對較強異構的行李集合碼放更具優勢。經分析原因在于:小尺寸行李箱可被該算法中的“填縫算法”更好的利用,較強異構的行李集合可以生成更多的組合供該算法中“動態選擇算法”加以選擇,因此,DQS 算法更適合中小尺寸強異構性的行李集合碼放。根據多樣性數據集實驗結果可得,算法的平均填充率保持在84.3% ～93.5%,算法穩定性較好。

DQS 算法在三維裝箱標準測試集中與其他算法的結果對比如表6 所示。箱子種類數分別為3、5、8、10、12、15、20,異構性由弱到強,其他算法結果均是在滿足C1 與C2 約束條件下所得,DQS算法滿足C1、C2、C3 約束。在多出的C3 與民航行李箱自身只允許正放的嚴格約束下,DQS 算法表現與其他算法相差不大,甚至在BR2 測試集的結果中以95. 1% 的填充率高于所有其他算法。然而,由于DQS 算法的約束更嚴格,在除BR2 的其他測試集下結果仍小于大部分其他算法。但隨著測試集異構性的增強,差距也在不斷縮小,最終在BR6 中以92. 8% 的填充率超過了HSA 算法(92.7%),在BR7 中以92. 2% 的填充率超過了HAS 算法(92.0%),印證了上文由多樣性數據集得出的DQS 算法對強異構集合更為適應的結論。