洪振宇 張 聰
(中國民航大學(xué) 天津 300300)
目前全球機場旅客運輸量超過7千萬的機場達到11家,其中,亞特蘭大國際機場和北京首都機場的旅客運輸量已經(jīng)超過1億,平均每天運送行李超過20萬件,并且從近幾年的變化趨勢來看,旅客運輸量仍在持續(xù)增長,這對機場的高效、安全運營提出了挑戰(zhàn)。旅客行李轉(zhuǎn)運效率是衡量機場運行保障能力的關(guān)鍵指標(biāo)。機場離港旅客行李轉(zhuǎn)運過程包括兩個階段,第一階段是在航站樓內(nèi)從旅客值機到行李分揀口;第二階段是在飛行區(qū)將行李從分揀口運送至預(yù)定航班上。目前,行李處理的第一階段由自動化的行李處理系統(tǒng)完成,該系統(tǒng)技術(shù)比較成熟,已經(jīng)實現(xiàn)了危險行李自動識別與分揀。而在行李轉(zhuǎn)運過程的第二階段,完全依靠人工,這也成為行李轉(zhuǎn)運效率和安全的瓶頸。采用機械手代替人工搬運行李是提高機場行李轉(zhuǎn)運效率的有效方法,而機械手的碼放策略又直接影響機場行李的轉(zhuǎn)運效率,所以對機械手的碼放策略的研究是非常必要的。
機場行李轉(zhuǎn)運要求機械手在無法提前預(yù)知行李尺寸的情況下,較短時間內(nèi)根據(jù)行李車內(nèi)布局給出行李的碼放位置,并使行李車得到較高的空間利用率。因此機場行李轉(zhuǎn)運問題不僅是三維裝箱問題,而且還是一個復(fù)雜的在線決策問題。三維裝箱問題按照貨物的尺寸不同分為單構(gòu)型裝箱問題和異構(gòu)型裝箱問題,按照使用容器的不同分為單箱裝箱和多箱裝箱問題,對于異構(gòu)型貨物的裝箱問題在數(shù)學(xué)上屬于NP-hard[1]問題,很難得到精確解,目前對于NP-hard問題大多數(shù)學(xué)者采用的是啟發(fā)式算法,George等[2]提出采用基于“層”或“墻”的構(gòu)造性啟發(fā)算法;Bischoff[3]在George的基礎(chǔ)上提出了基于“完全層”的啟發(fā)式算法,將二維裝箱問題應(yīng)用到三維空間;Fanslau等[4]進一步擴展了“塊”的概念,提出復(fù)合塊的思想,設(shè)計了一種有效的啟發(fā)式算法;張德富等[5-6]提出一種混合模擬退火算法,隨后又提出了三維裝箱問題的組合啟發(fā)式算法;劉勝等[7]提出求解三維裝箱問題的啟發(fā)式正交二叉樹搜索算法,該算法裝箱效率已有顯著提高,但當(dāng)箱子種類較少時,效果就會不理想。除此之外其他一些學(xué)者也取得了較好的研究成果[8-12]。
雖然啟發(fā)式算法在解決三維裝箱問題取得了顯著成果,卻不能解決碼放過程中的在線決策問題,為了解決這一問題我們引入支持向量機模型(Support Vector Machine,SVM),支持向量機是機器學(xué)習(xí)[14]重要算法之一,由Cortes等[13]于1995年提出,在解決樣本數(shù)量少、非線性及高維度的分類問題[14-15]時表現(xiàn)出許多特有的優(yōu)勢,將稀疏化理論[16]與最小二乘支持向量機模型(Least Squares Support Vector Machine, LSSVM)結(jié)合的多層訓(xùn)練網(wǎng)絡(luò)近年來也得到了廣泛應(yīng)用[17]。
為了同時解決機場行李轉(zhuǎn)運過程中存在的NP-hard問題和在線碼放問題,本文提出基于空間離散算法的機場行李碼放策略,通過行李車與行李空間離散化,將行李車連續(xù)空間的無數(shù)個可碼放位置轉(zhuǎn)化為空間單元節(jié)點個數(shù)種有限個可碼放位置,使系統(tǒng)的運算速度更快、效率更高。同時使用深度稀疏最小二乘支持向量機模型訓(xùn)練,學(xué)習(xí)工人的碼放經(jīng)驗,使算法在最短的時間內(nèi)計算出行李最佳碼放位置,并且在碼放結(jié)束時可以得到接近人工碼放的空間利用率,滿足機場的需求。
在機場行李運輸?shù)倪^程中,行李由分揀系統(tǒng)傳送帶依次有序運送至分揀口,由機械手完成碼放,行李按照先來先放的順序進行碼放,盡可能地實現(xiàn)使用行李車數(shù)量最少并且每個行李車的空間利用率達到最高,因此當(dāng)一個行李進入碼放區(qū)域時需要機械手在較短時間內(nèi)給出合理的碼放策略,決定行李碼放位置,而且機場行李尺寸大小不一,無法提前獲得,需要一個有效的評價方案用來評價該位置的優(yōu)劣,為了便于對碼放位置的評價,將行李車和行李空間離散化。
公設(shè)行李車的長、寬、高分別為L、W、H;行李的長、寬、高分別為lj、wj、hj,(j表示第j種類型的行李),采用笛卡爾坐標(biāo)系將行李車的左下角設(shè)為坐標(biāo)原點,行李車的長度方向為x軸,寬度方向為y軸,高度方向為z軸,本文提出的空間離散算法的概念,將機場行李車和行李離散為由各單元組成的計算模型,離散后的單元與單元之間采用單元節(jié)點連接如圖1和圖2所示,單元節(jié)點可以記錄空間的狀態(tài)信息。
圖1 行李車三維空間離散示意圖
圖2 行李三維空間離散示意圖
考慮到三維裝箱問題的復(fù)雜性,我們將三維裝箱問題轉(zhuǎn)化為二維平面問題,將行李車和行李的z軸忽略,將其轉(zhuǎn)化為平面問題,如圖3和圖4所示。
圖3 行李車二維平面離散示意圖
圖4 行李二維平面離散示意圖
在二維平面內(nèi),將行李車和行李空間離散化,沿長和寬方向等距劃分為大小相等的單元網(wǎng)格,網(wǎng)格的交點為單元節(jié)點,在行李進行碼放時,行李的單元網(wǎng)格必須與行李車的單元網(wǎng)格重合。行李可放位置由連續(xù)體內(nèi)的無限種可能轉(zhuǎn)換為單元節(jié)點個數(shù)種可能,降低了問題的復(fù)雜程度,使計算過程更加簡單快速。
在行李進行碼放時需要對當(dāng)前所有可能碼放的位置進行評價,根據(jù)評價的結(jié)果,選擇最佳位置,評價方案的好壞直接影響碼放結(jié)果和工作效率,因此針對行李碼放策略,需要根據(jù)實際情況進行分析,確定評價方案。
(1) 當(dāng)一個行李放入行李車時,該行李在二維平面內(nèi)與行李車的邊或者與其他行李之間接觸越多,其剩余空間可能被利用的機會就會越大,這樣的碼放是對最終的空間利用率有利的。
(2) 當(dāng)一個行李擺放后,最終整體的高度會有怎樣的變化,顯然高度越低,最終的效果越好,當(dāng)有兩個位置可選擇擺放時,應(yīng)該優(yōu)先放置在比較低的位置上。
(3) 當(dāng)一個行李擺放后,每一行的空的單元數(shù)量越多,對最終的空間利用率越不利。
(4) 行李車上擺放的行李個數(shù)越多則空間利用率越大。
以上是對評估局面需要考慮的參數(shù)的一般性描述,我們需要將其抽象為五個影響空間利用率結(jié)果的屬性:
(1) 底邊距:指行李在放置后,放置點距離行李車x軸垂直距離,用L表示。
(2) 行變換:對于離散后的行李車空間,在x軸方向上,從無行李放置區(qū)域到有行李放置區(qū)域是一種“變換”,從有行李放置區(qū)域到無行李放置區(qū)域也是一種“變換”,這個屬性是各行中“變換”次數(shù)之和,用字母R表示。
(3) 列變換:對于離散后的行李車空間,在y軸方向上,從無行李放置區(qū)域到有行李放置區(qū)域是一種“變換”,從有行李放置區(qū)域到無行李放置區(qū)域也是一種“變換”,這個屬性是各列中“變換”次數(shù)之和,用字母C表示。
(4) 空格:擺放后的空格數(shù)量之和用字母B表示,如圖5所示。
圖5 “空格”與“井”示意圖
(5) 井:在行李擺放后,兩個行李中間,未被行李填充的單元格個數(shù)的連加和,用字母W表示。
在行李裝載過程中,需要根據(jù)實際情況考慮行李裝載過程中的約束條件,根據(jù)機場的實際調(diào)研,引入以下五種約束條件:
(1) 行李方向約束:在實際裝載的過程中,行李的方向約束一般分為三種,即任意方向旋轉(zhuǎn)、水平旋轉(zhuǎn)、不能旋轉(zhuǎn)。根據(jù)行李的設(shè)計特點,行李只能沿水平方向旋轉(zhuǎn)。
(2) 穩(wěn)定性約束:行李在裝載過程中必須得到行李車底部或者其他行李的完全支撐,不得懸空。
(3) 重心約束:在裝載完畢后,行李車的重心應(yīng)該在行李車的幾何中心附近,有利于運輸過程的穩(wěn)定性。
(4) 行李最大碼放層數(shù)約束:考慮運輸過程中的穩(wěn)定性以及最下端行李的承載能力,要對行李允許的最大碼放層數(shù)限制,行李碼放高度不應(yīng)該超出行李車圍欄的最高高度。
(5) 行李車最大載重、最大容積約束:行李車本身承載重量和最大容積的限制,已裝行李的總重量不得超過行李車的最大載重量,總體積不得超過行李車的容積。
在碼放過程中,在滿足約束條件的情況下,第一個行李的碼放通常按照“貼邊”“占角”的規(guī)則進行碼放,當(dāng)?shù)趎個行李的位置確定后,第n+1個行李的可能碼放位置就會有多種選擇,在多個位置選擇中選擇最佳的一個位置作為行李的放置位置,這樣將碼放位置選擇問題轉(zhuǎn)換為二分類問題,即最佳碼放位置為一類,其他位置為一類。在機場的實際工作過程中,一個有經(jīng)驗的裝載工人會根據(jù)多年的工作經(jīng)驗合理選擇下一個行李的碼放位置,并且能得到較高空間利用率,因此在最佳位置選擇時,根據(jù)裝載工人的經(jīng)驗選擇最佳位置,在不同布局的情況下每個可放位置的五個位置評價參數(shù)各不相同,而工人在選擇最佳位置后將其單獨作為最佳碼放位置的類別,這樣便將工人的經(jīng)驗映射到位置評價參數(shù)的分類選擇中。例如:在圖6所示情況下,深顏色為已放行李區(qū)域,淺顏色為可放位置,計算所有可放位置的評估參數(shù),并將評估參數(shù)記錄,如表1所示。根據(jù)裝載工人的經(jīng)驗,選擇最佳位置H將其標(biāo)記為1,其他位置標(biāo)記為-1。將其作為機器學(xué)習(xí)分類數(shù)據(jù)集進行訓(xùn)練,成功地將工人碼放經(jīng)驗映射到行李參數(shù)中。
圖6 第n+1個行李可放位置示意圖
表1 不同碼放位置各參數(shù)取值
在模型訓(xùn)練過程中,根據(jù)裝載工人的經(jīng)驗,對可放位置進行標(biāo)記,將可放位置分為兩類,將選擇最佳位置作為機器學(xué)習(xí)的輸出,這樣行李位置的選擇問題轉(zhuǎn)化為二分類問題,針對二分類問題,支持向量機模型得到廣泛應(yīng)用,并且可以得到較高的分類準(zhǔn)確率。
(1)
根據(jù)最小優(yōu)化原則可以求得優(yōu)化目標(biāo)α,所以得到分類函數(shù):
(2)
深度支持向量機(Deep Support Vector Machine, DSVM)由輸入層、中間層和輸出層組成,每層都是一個完整的支持向量機,其中間層的數(shù)量為l層,結(jié)構(gòu)如圖7所示。訓(xùn)練樣本通過上一層的訓(xùn)練得到支持向量,并將每次訓(xùn)練結(jié)果經(jīng)過處理作為下一層訓(xùn)練的輸入,從而構(gòu)建一層新的訓(xùn)練模型。
圖7 深度支持向量機模型
g(i)=ysviaiκ(xvi,x)+bi=1,2,…,Q
(3)
式中:svi為支持向量;ai為對應(yīng)的拉格朗日因子;ysvi為支持向量對應(yīng)的標(biāo)簽;b為偏置。
在經(jīng)過降維處理后可以得到的樣本可以表示為:
ysvQaQκ(svQ,xi)+b}
(4)
對于測試樣本集,也使用照降維公式逐層對其映射,其分類判別函數(shù)為:
(5)
DSVM方法與傳統(tǒng)SVM方法比較,在對碼放行李參數(shù)訓(xùn)練時,雖然能夠得到較高的準(zhǔn)確率,但是隨著訓(xùn)練層數(shù)的增加,訓(xùn)練過程中計算的復(fù)雜程度和訓(xùn)練時間也隨之增加。最小二乘法支持向量機模型可以將不等式約束轉(zhuǎn)換為等式約束,降低計算的復(fù)雜程度,但是在求解的過程中模型會對每個樣本進行訓(xùn)練,缺少稀疏性,因此,提出深度稀疏最小二乘支持向量機模型來解決此問題。通過求解樣本數(shù)據(jù)高維特征空間近似最大線性無關(guān)向量組的方法對其進行稀疏化處理,在保證分類準(zhǔn)確率的同時,增加了訓(xùn)練樣本的稀疏性,提高了計算效率。
在對最小二乘支持向量機稀疏化的過程中主要包括兩個步驟。
(1) 尋找高維空間的一組近似線性無關(guān)向量,構(gòu)造線性向量組,對位置參數(shù)樣本進行稀疏表示。
首先尋找碼放位置參數(shù)樣本的特征子集B={(xj,yj)}j∈s?D,m=|S|≤N,使所有的樣本可以表示成該特征子集在特征空間的線性組合:
(6)
所以可得:
(7)
因此,分類判別函數(shù)表示為:
(8)
通過選擇參數(shù)v來去除特征空間中的近似相關(guān)向量,同時也可以控制子集B與樣本的逼近程度,稀疏化的流程如圖8所示。
圖8 稀疏化流程
(2) 利用稀疏樣本求解最優(yōu)分類判別函數(shù)。將式(7)、式(8)代入最小二乘支持向量優(yōu)化目標(biāo)函數(shù)中,可得:
(9)
式(9)是關(guān)于β和b的凸二次規(guī)劃問題,其中:β=[βS1,βS2,…,βSm];ym=[yS1,yS2,…,ySm]∈Rm;D(ym)為以ym元素為對角元素構(gòu)成的對角矩陣;(Kmm)i,j∈S=κ(xi,xj)=Φ(xi)TΦ(xj);yN=[y1,y2,…,yN]∈RN;D(yN)為以yN為對角元素構(gòu)成的對角矩陣;KNm=[km(x1),km(x2),…,km(xN)]T;km(xj)=[κ(xi,xS1),κ(xi,xS2),…,κ(xi,xSm)]T;1為元素全為1的單位列向量。最優(yōu)解可以通過以下條件求得:
(10)
對其求解可得關(guān)于β和b的方程組:
(11)
在算法實現(xiàn)過程中,只需將深度支持向量機中的每一層替換為SLSSVM即可,實現(xiàn)多層最小二乘支持向量機的疊加,訓(xùn)練過程與DSVM相同,首先使用SLSSVM的輸入層對初始樣本進行訓(xùn)練,然后使用降維公式對輸出層的結(jié)果進行處理,并將處理結(jié)果作為第二層的輸入進行訓(xùn)練,而DSLSSVM利用SLSSVM的系數(shù)β與向量組B構(gòu)造降維公式,這里降維公式可以表示為:
g(i)=ysvjβiκ(xj,x)+bj∈S
(12)
隨后逐層訓(xùn)練,直至輸出結(jié)果。通過DSLSSVM深層結(jié)構(gòu)對細(xì)膩碼放位置參數(shù)進行訓(xùn)練,對其內(nèi)在規(guī)律進行學(xué)習(xí),既可以得到較高的識別準(zhǔn)確率,又可以減少運算時間。
本實驗使用計算機主要硬件配置如表2所示。
表2 計算機主要硬件配置
仿真實驗使用計算機運行的操作系統(tǒng)為Microsoft Windows 7,本實驗中的算法均使用Python語言進行編寫,在機器學(xué)習(xí)方面使用scikit-learn模塊來實現(xiàn),使用pandas和numpy數(shù)據(jù)庫對數(shù)據(jù)進行處理。
根據(jù)國際航空運輸協(xié)會(International Air Transport Association,IATA)規(guī)定,隨身登機箱尺寸三邊之和不得超過115 cm,托運行李箱尺寸不得超過158 cm,所以20英寸及以下的行李箱可以隨身帶入機艙,28英寸及以下的行李箱可以進行托運,現(xiàn)假設(shè)行李的類型為4種,分別為22英寸(60 cm×35 cm×22 cm)、24英寸(65 cm×40 cm×26 cm)、26英寸(70 cm×45 cm×28 cm)和28英寸(75 cm×50 cm×32 cm);根據(jù)調(diào)研,目前機場采用的行李拖車大多數(shù)為三面護欄式行李拖車全車尺寸為300 cm×175 cm×100 cm。
在仿真實驗中,我們將仿真過程分為兩個階段,即訓(xùn)練階段和工作階段。在訓(xùn)練階段,數(shù)據(jù)集由計算機自動生成,首先系統(tǒng)會隨機生成要碼放行李類別,計算機根據(jù)當(dāng)前行李車布局情況,沿x軸方向依次遍歷所有可放位置并計算每個位置評估參數(shù)數(shù)值,每個位置生成一組數(shù)據(jù),有經(jīng)驗的碼放工人根據(jù)多年工作經(jīng)驗選擇最佳位置進行碼放,計算機將此位置進行標(biāo)記,完成一個行李的碼放,重復(fù)以上過程直至整個行李車被裝滿,生成訓(xùn)練數(shù)據(jù)集。
為了驗證本文使用的DSLSSVM分類模型優(yōu)于其他模型分類準(zhǔn)確率,分別使用DSLSSVM、SVM、決策樹分類模型和樸素貝葉斯分類模型進行對比實驗。使用三組不同的行李碼放位置參數(shù)作為樣本進行實驗,每組實驗包括5 000組數(shù)據(jù),分別使用不同算法進行實驗,實驗結(jié)果如表3所示。
表3 準(zhǔn)確率統(tǒng)計表(%)
續(xù)表3
可以看出,在本文的分類實驗中, DSLSSVM分類準(zhǔn)確率最高,達到97.77%以上,比SVM分類模型的分類精度高3.73百分點,比樸樹貝葉斯分類模型高12.15百分點,所以DSLSSVM分類算法模型適用于本文的空間離散算法,并且可以滿足精度要求。
在確定了DSLSSVM分類模型的可行性后,將訓(xùn)練數(shù)據(jù)集定為8 000組,使用10折交叉驗證法對DSLSSVM分類模型進行訓(xùn)練,并將訓(xùn)練好的模型保存。在利用率對比實驗中,使用訓(xùn)練好的模型進行仿真實驗,圖9分別給出使用人工經(jīng)驗碼放、基于機器學(xué)習(xí)的空間離散算法碼放、依次橫放、依次豎放和傳統(tǒng)的啟發(fā)式算法五種不同的碼放方法下得到的二維裝箱效果圖。
(a) 人工經(jīng)驗碼放仿真圖
使用人工經(jīng)驗進行碼放仿真時,通過Python語言進行編寫程序,使用計算機輸入設(shè)備鍵盤的方向鍵控制行李在行李車網(wǎng)格空間中的位置,模擬工人裝載的過程,通過工人日常積累的經(jīng)驗根據(jù)行李的大小和行李車的布局情況調(diào)整行李碼放位置,將行李放在當(dāng)前布局情況下最佳碼放位置,完成一次碼放。
傳統(tǒng)的啟發(fā)式算法在解決裝箱問題時大多采用“分層”和“分塊”的概念,本文在進行仿真實驗時根據(jù)文獻[18]提出的基于“塊”和“空間”的啟發(fā)式算法,對其算法進行復(fù)現(xiàn),作為對照進行仿真實驗。
在實驗過程中,分別使用人工經(jīng)驗碼放、基于空間離散算法的碼放策略、行李依次橫放、行李依次豎放和傳統(tǒng)啟發(fā)式算法的方式進行碼放實驗,每種碼放方式進行三組實驗,每組實驗各碼放十次,統(tǒng)計其利用率如表4所示。
表4 利用率統(tǒng)計表(%)
通過與工人經(jīng)驗碼放的對比實驗可以看出,本文提出的空間離散的概念可以有效地將工人經(jīng)驗映射到評價參數(shù)中,同時證明了本文提出的基于深度稀疏最小二乘支持向量機分類模型可以實現(xiàn)對行李參數(shù)的準(zhǔn)確分類,適用于空間離散算法。使用空間離散算法得到的空間利用率達到87.24%,接近有經(jīng)驗的工人的碼放水平。與其他碼放方式進行對比可以看出,比傳統(tǒng)啟發(fā)式算法得到的仿真結(jié)果高4.58百分比,比行李依次豎放利用率提高了12.07百分比,比依次橫放利用率提高了13.58百分比。綜上所述,該算法可以代替機場工人實現(xiàn)行李的自動化裝載,并且可以達到與人工碼放行李較為接近的水平,與其他碼放方式相比可以得到較大的空間利用率,滿足機場高效運輸?shù)幕疽蟆?/p>
在機場實際裝載的過程中,除了滿足空間利用率最大原則外還要考慮算法計算速度盡可能快,滿足在線碼放的要求。傳統(tǒng)的基于“塊”和“空間”的啟發(fā)式算法在進行碼放位置的選擇時,采用啟發(fā)式搜索的方法遍歷所有可能碼放的位置,同時還將剩余的空間進行選擇、劃分、合并,更是增加了可放位置的選擇,使得算法計算更加復(fù)雜,耗費大量時間。
使用本文提出的基于空間離散的機場行李碼放策略與基于“塊”和“空間”的啟發(fā)式算法的碼放方法在相同的情況下進行行李碼放作業(yè),統(tǒng)計兩種不同算法裝入行李個數(shù)如表5所示。
表5 相同時間下裝入行李個數(shù)統(tǒng)計表
可以看出,在本文提出的基于空間離散算法的機場行李碼放策略在相同時間碼放行李個數(shù)遠大于基于“塊”和“空間”的啟發(fā)式算法碼放的行李個數(shù),并且對行李車的空間利用率較高,所以與傳統(tǒng)基于“塊”和“空間”的啟發(fā)式算法相比,本文算法更適合機場高速、高效率的要求。
為了解決機場行李在轉(zhuǎn)運過程中存在的裝箱問題,提出一種基于空間離散算法的機場行李碼放方法。通過分析機場行李碼放特點,定義行李碼放位置的評價參數(shù),模擬有經(jīng)驗工人的碼放過程,構(gòu)建訓(xùn)練樣本,使用DSLSSVM模型學(xué)習(xí)工人經(jīng)驗,得到訓(xùn)練模型。在實際工作中,系統(tǒng)根據(jù)行里車內(nèi)不同局面給出不同的碼放方案,完成行李在線實時碼放。
仿真實驗結(jié)果表明,通過該方法碼放的行李在空間利用率和效率方面可以達到與人工碼放行李比較接近的水平,可以滿足機場行李運輸?shù)囊?。并且相比于基于“塊”和“空間”的傳統(tǒng)啟發(fā)式算法,該方法在實現(xiàn)過程中減少了算法計算時間,提高了機場行李裝載效率,具有較強的實用性。