基于支持向量機(jī)模型的機(jī)場(chǎng)行李碼放策略

洪振宇 張 聰

(中國(guó)民航大學(xué) 天津 300300)

0 引 言

目前全球機(jī)場(chǎng)旅客運(yùn)輸量超過(guò)7千萬(wàn)的機(jī)場(chǎng)達(dá)到11家，其中，亞特蘭大國(guó)際機(jī)場(chǎng)和北京首都機(jī)場(chǎng)的旅客運(yùn)輸量已經(jīng)超過(guò)1億，平均每天運(yùn)送行李超過(guò)20萬(wàn)件，并且從近幾年的變化趨勢(shì)來(lái)看，旅客運(yùn)輸量仍在持續(xù)增長(zhǎng)，這對(duì)機(jī)場(chǎng)的高效、安全運(yùn)營(yíng)提出了挑戰(zhàn)。旅客行李轉(zhuǎn)運(yùn)效率是衡量機(jī)場(chǎng)運(yùn)行保障能力的關(guān)鍵指標(biāo)。機(jī)場(chǎng)離港旅客行李轉(zhuǎn)運(yùn)過(guò)程包括兩個(gè)階段，第一階段是在航站樓內(nèi)從旅客值機(jī)到行李分揀口；第二階段是在飛行區(qū)將行李從分揀口運(yùn)送至預(yù)定航班上。目前，行李處理的第一階段由自動(dòng)化的行李處理系統(tǒng)完成，該系統(tǒng)技術(shù)比較成熟，已經(jīng)實(shí)現(xiàn)了危險(xiǎn)行李自動(dòng)識(shí)別與分揀。而在行李轉(zhuǎn)運(yùn)過(guò)程的第二階段，完全依靠人工，這也成為行李轉(zhuǎn)運(yùn)效率和安全的瓶頸。采用機(jī)械手代替人工搬運(yùn)行李是提高機(jī)場(chǎng)行李轉(zhuǎn)運(yùn)效率的有效方法，而機(jī)械手的碼放策略又直接影響機(jī)場(chǎng)行李的轉(zhuǎn)運(yùn)效率，所以對(duì)機(jī)械手的碼放策略的研究是非常必要的。

機(jī)場(chǎng)行李轉(zhuǎn)運(yùn)要求機(jī)械手在無(wú)法提前預(yù)知行李尺寸的情況下，較短時(shí)間內(nèi)根據(jù)行李車內(nèi)布局給出行李的碼放位置，并使行李車得到較高的空間利用率。因此機(jī)場(chǎng)行李轉(zhuǎn)運(yùn)問(wèn)題不僅是三維裝箱問(wèn)題，而且還是一個(gè)復(fù)雜的在線決策問(wèn)題。三維裝箱問(wèn)題按照貨物的尺寸不同分為單構(gòu)型裝箱問(wèn)題和異構(gòu)型裝箱問(wèn)題，按照使用容器的不同分為單箱裝箱和多箱裝箱問(wèn)題，對(duì)于異構(gòu)型貨物的裝箱問(wèn)題在數(shù)學(xué)上屬于NP-hard[1]問(wèn)題，很難得到精確解，目前對(duì)于NP-hard問(wèn)題大多數(shù)學(xué)者采用的是啟發(fā)式算法，George等[2]提出采用基于“層”或“墻”的構(gòu)造性啟發(fā)算法；Bischoff[3]在George的基礎(chǔ)上提出了基于“完全層”的啟發(fā)式算法，將二維裝箱問(wèn)題應(yīng)用到三維空間；Fanslau等[4]進(jìn)一步擴(kuò)展了“塊”的概念，提出復(fù)合塊的思想，設(shè)計(jì)了一種有效的啟發(fā)式算法；張德富等[5-6]提出一種混合模擬退火算法,隨后又提出了三維裝箱問(wèn)題的組合啟發(fā)式算法；劉勝等[7]提出求解三維裝箱問(wèn)題的啟發(fā)式正交二叉樹搜索算法,該算法裝箱效率已有顯著提高，但當(dāng)箱子種類較少時(shí)，效果就會(huì)不理想。除此之外其他一些學(xué)者也取得了較好的研究成果[8-12]。

雖然啟發(fā)式算法在解決三維裝箱問(wèn)題取得了顯著成果，卻不能解決碼放過(guò)程中的在線決策問(wèn)題，為了解決這一問(wèn)題我們引入支持向量機(jī)模型(Support Vector Machine，SVM)，支持向量機(jī)是機(jī)器學(xué)習(xí)[14]重要算法之一，由Cortes等[13]于1995年提出，在解決樣本數(shù)量少、非線性及高維度的分類問(wèn)題[14-15]時(shí)表現(xiàn)出許多特有的優(yōu)勢(shì)，將稀疏化理論[16]與最小二乘支持向量機(jī)模型(Least Squares Support Vector Machine， LSSVM)結(jié)合的多層訓(xùn)練網(wǎng)絡(luò)近年來(lái)也得到了廣泛應(yīng)用[17]。

為了同時(shí)解決機(jī)場(chǎng)行李轉(zhuǎn)運(yùn)過(guò)程中存在的NP-hard問(wèn)題和在線碼放問(wèn)題，本文提出基于空間離散算法的機(jī)場(chǎng)行李碼放策略，通過(guò)行李車與行李空間離散化，將行李車連續(xù)空間的無(wú)數(shù)個(gè)可碼放位置轉(zhuǎn)化為空間單元節(jié)點(diǎn)個(gè)數(shù)種有限個(gè)可碼放位置，使系統(tǒng)的運(yùn)算速度更快、效率更高。同時(shí)使用深度稀疏最小二乘支持向量機(jī)模型訓(xùn)練，學(xué)習(xí)工人的碼放經(jīng)驗(yàn)，使算法在最短的時(shí)間內(nèi)計(jì)算出行李最佳碼放位置，并且在碼放結(jié)束時(shí)可以得到接近人工碼放的空間利用率，滿足機(jī)場(chǎng)的需求。

1 碼放策略

在機(jī)場(chǎng)行李運(yùn)輸?shù)倪^(guò)程中，行李由分揀系統(tǒng)傳送帶依次有序運(yùn)送至分揀口，由機(jī)械手完成碼放，行李按照先來(lái)先放的順序進(jìn)行碼放，盡可能地實(shí)現(xiàn)使用行李車數(shù)量最少并且每個(gè)行李車的空間利用率達(dá)到最高，因此當(dāng)一個(gè)行李進(jìn)入碼放區(qū)域時(shí)需要機(jī)械手在較短時(shí)間內(nèi)給出合理的碼放策略，決定行李碼放位置，而且機(jī)場(chǎng)行李尺寸大小不一，無(wú)法提前獲得，需要一個(gè)有效的評(píng)價(jià)方案用來(lái)評(píng)價(jià)該位置的優(yōu)劣，為了便于對(duì)碼放位置的評(píng)價(jià)，將行李車和行李空間離散化。

1.1 評(píng)價(jià)方法

公設(shè)行李車的長(zhǎng)、寬、高分別為L(zhǎng)、W、H；行李的長(zhǎng)、寬、高分別為lj、wj、hj，(j表示第j種類型的行李)，采用笛卡爾坐標(biāo)系將行李車的左下角設(shè)為坐標(biāo)原點(diǎn)，行李車的長(zhǎng)度方向?yàn)閤軸，寬度方向?yàn)閥軸，高度方向?yàn)閦軸，本文提出的空間離散算法的概念，將機(jī)場(chǎng)行李車和行李離散為由各單元組成的計(jì)算模型，離散后的單元與單元之間采用單元節(jié)點(diǎn)連接如圖1和圖2所示，單元節(jié)點(diǎn)可以記錄空間的狀態(tài)信息。

圖1 行李車三維空間離散示意圖

圖2 行李三維空間離散示意圖

考慮到三維裝箱問(wèn)題的復(fù)雜性，我們將三維裝箱問(wèn)題轉(zhuǎn)化為二維平面問(wèn)題，將行李車和行李的z軸忽略，將其轉(zhuǎn)化為平面問(wèn)題，如圖3和圖4所示。

圖3 行李車二維平面離散示意圖

圖4 行李二維平面離散示意圖

在二維平面內(nèi)，將行李車和行李空間離散化，沿長(zhǎng)和寬方向等距劃分為大小相等的單元網(wǎng)格，網(wǎng)格的交點(diǎn)為單元節(jié)點(diǎn)，在行李進(jìn)行碼放時(shí)，行李的單元網(wǎng)格必須與行李車的單元網(wǎng)格重合。行李可放位置由連續(xù)體內(nèi)的無(wú)限種可能轉(zhuǎn)換為單元節(jié)點(diǎn)個(gè)數(shù)種可能，降低了問(wèn)題的復(fù)雜程度，使計(jì)算過(guò)程更加簡(jiǎn)單快速。

在行李進(jìn)行碼放時(shí)需要對(duì)當(dāng)前所有可能碼放的位置進(jìn)行評(píng)價(jià)，根據(jù)評(píng)價(jià)的結(jié)果，選擇最佳位置，評(píng)價(jià)方案的好壞直接影響碼放結(jié)果和工作效率，因此針對(duì)行李碼放策略，需要根據(jù)實(shí)際情況進(jìn)行分析，確定評(píng)價(jià)方案。

(1) 當(dāng)一個(gè)行李放入行李車時(shí)，該行李在二維平面內(nèi)與行李車的邊或者與其他行李之間接觸越多，其剩余空間可能被利用的機(jī)會(huì)就會(huì)越大，這樣的碼放是對(duì)最終的空間利用率有利的。

(2) 當(dāng)一個(gè)行李擺放后，最終整體的高度會(huì)有怎樣的變化，顯然高度越低，最終的效果越好，當(dāng)有兩個(gè)位置可選擇擺放時(shí)，應(yīng)該優(yōu)先放置在比較低的位置上。

(3) 當(dāng)一個(gè)行李擺放后，每一行的空的單元數(shù)量越多，對(duì)最終的空間利用率越不利。

(4) 行李車上擺放的行李個(gè)數(shù)越多則空間利用率越大。

以上是對(duì)評(píng)估局面需要考慮的參數(shù)的一般性描述，我們需要將其抽象為五個(gè)影響空間利用率結(jié)果的屬性：

(1) 底邊距：指行李在放置后，放置點(diǎn)距離行李車x軸垂直距離，用L表示。

(2) 行變換：對(duì)于離散后的行李車空間，在x軸方向上，從無(wú)行李放置區(qū)域到有行李放置區(qū)域是一種“變換”，從有行李放置區(qū)域到無(wú)行李放置區(qū)域也是一種“變換”，這個(gè)屬性是各行中“變換”次數(shù)之和，用字母R表示。

(3) 列變換：對(duì)于離散后的行李車空間，在y軸方向上，從無(wú)行李放置區(qū)域到有行李放置區(qū)域是一種“變換”，從有行李放置區(qū)域到無(wú)行李放置區(qū)域也是一種“變換”，這個(gè)屬性是各列中“變換”次數(shù)之和，用字母C表示。

(4) 空格：擺放后的空格數(shù)量之和用字母B表示，如圖5所示。

圖5 “空格”與“井”示意圖

(5) 井：在行李擺放后，兩個(gè)行李中間，未被行李填充的單元格個(gè)數(shù)的連加和，用字母W表示。

1.2 決策過(guò)程

在行李裝載過(guò)程中，需要根據(jù)實(shí)際情況考慮行李裝載過(guò)程中的約束條件，根據(jù)機(jī)場(chǎng)的實(shí)際調(diào)研，引入以下五種約束條件：

(1) 行李方向約束：在實(shí)際裝載的過(guò)程中，行李的方向約束一般分為三種，即任意方向旋轉(zhuǎn)、水平旋轉(zhuǎn)、不能旋轉(zhuǎn)。根據(jù)行李的設(shè)計(jì)特點(diǎn)，行李只能沿水平方向旋轉(zhuǎn)。

(2) 穩(wěn)定性約束：行李在裝載過(guò)程中必須得到行李車底部或者其他行李的完全支撐，不得懸空。

(3) 重心約束：在裝載完畢后，行李車的重心應(yīng)該在行李車的幾何中心附近，有利于運(yùn)輸過(guò)程的穩(wěn)定性。

(4) 行李最大碼放層數(shù)約束：考慮運(yùn)輸過(guò)程中的穩(wěn)定性以及最下端行李的承載能力，要對(duì)行李允許的最大碼放層數(shù)限制，行李碼放高度不應(yīng)該超出行李車圍欄的最高高度。

(5) 行李車最大載重、最大容積約束：行李車本身承載重量和最大容積的限制，已裝行李的總重量不得超過(guò)行李車的最大載重量，總體積不得超過(guò)行李車的容積。

在碼放過(guò)程中，在滿足約束條件的情況下，第一個(gè)行李的碼放通常按照“貼邊”“占角”的規(guī)則進(jìn)行碼放，當(dāng)?shù)趎個(gè)行李的位置確定后，第n+1個(gè)行李的可能碼放位置就會(huì)有多種選擇，在多個(gè)位置選擇中選擇最佳的一個(gè)位置作為行李的放置位置，這樣將碼放位置選擇問(wèn)題轉(zhuǎn)換為二分類問(wèn)題，即最佳碼放位置為一類，其他位置為一類。在機(jī)場(chǎng)的實(shí)際工作過(guò)程中，一個(gè)有經(jīng)驗(yàn)的裝載工人會(huì)根據(jù)多年的工作經(jīng)驗(yàn)合理選擇下一個(gè)行李的碼放位置，并且能得到較高空間利用率，因此在最佳位置選擇時(shí)，根據(jù)裝載工人的經(jīng)驗(yàn)選擇最佳位置，在不同布局的情況下每個(gè)可放位置的五個(gè)位置評(píng)價(jià)參數(shù)各不相同，而工人在選擇最佳位置后將其單獨(dú)作為最佳碼放位置的類別，這樣便將工人的經(jīng)驗(yàn)映射到位置評(píng)價(jià)參數(shù)的分類選擇中。例如：在圖6所示情況下，深顏色為已放行李區(qū)域，淺顏色為可放位置，計(jì)算所有可放位置的評(píng)估參數(shù)，并將評(píng)估參數(shù)記錄，如表1所示。根據(jù)裝載工人的經(jīng)驗(yàn)，選擇最佳位置H將其標(biāo)記為1，其他位置標(biāo)記為-1。將其作為機(jī)器學(xué)習(xí)分類數(shù)據(jù)集進(jìn)行訓(xùn)練，成功地將工人碼放經(jīng)驗(yàn)映射到行李參數(shù)中。

圖6 第n+1個(gè)行李可放位置示意圖

表1 不同碼放位置各參數(shù)取值

2 學(xué)習(xí)算法

在模型訓(xùn)練過(guò)程中，根據(jù)裝載工人的經(jīng)驗(yàn)，對(duì)可放位置進(jìn)行標(biāo)記，將可放位置分為兩類，將選擇最佳位置作為機(jī)器學(xué)習(xí)的輸出，這樣行李位置的選擇問(wèn)題轉(zhuǎn)化為二分類問(wèn)題，針對(duì)二分類問(wèn)題，支持向量機(jī)模型得到廣泛應(yīng)用，并且可以得到較高的分類準(zhǔn)確率。

2.1 支持向量機(jī)模型

(1)

根據(jù)最小優(yōu)化原則可以求得優(yōu)化目標(biāo)α，所以得到分類函數(shù)：

(2)

2.2 深度支持向量機(jī)模型

深度支持向量機(jī)(Deep Support Vector Machine， DSVM)由輸入層、中間層和輸出層組成，每層都是一個(gè)完整的支持向量機(jī)，其中間層的數(shù)量為l層，結(jié)構(gòu)如圖7所示。訓(xùn)練樣本通過(guò)上一層的訓(xùn)練得到支持向量，并將每次訓(xùn)練結(jié)果經(jīng)過(guò)處理作為下一層訓(xùn)練的輸入，從而構(gòu)建一層新的訓(xùn)練模型。

圖7 深度支持向量機(jī)模型

g(i)=ysviaiκ(xvi,x)+bi=1,2,…,Q

(3)

式中：svi為支持向量；ai為對(duì)應(yīng)的拉格朗日因子；ysvi為支持向量對(duì)應(yīng)的標(biāo)簽；b為偏置。

在經(jīng)過(guò)降維處理后可以得到的樣本可以表示為：

ysvQaQκ(svQ,xi)+b}

(4)

對(duì)于測(cè)試樣本集，也使用照降維公式逐層對(duì)其映射，其分類判別函數(shù)為：

(5)

2.3 深度稀疏最小二乘支持向量機(jī)

DSVM方法與傳統(tǒng)SVM方法比較，在對(duì)碼放行李參數(shù)訓(xùn)練時(shí)，雖然能夠得到較高的準(zhǔn)確率，但是隨著訓(xùn)練層數(shù)的增加，訓(xùn)練過(guò)程中計(jì)算的復(fù)雜程度和訓(xùn)練時(shí)間也隨之增加。最小二乘法支持向量機(jī)模型可以將不等式約束轉(zhuǎn)換為等式約束，降低計(jì)算的復(fù)雜程度，但是在求解的過(guò)程中模型會(huì)對(duì)每個(gè)樣本進(jìn)行訓(xùn)練，缺少稀疏性，因此，提出深度稀疏最小二乘支持向量機(jī)模型來(lái)解決此問(wèn)題。通過(guò)求解樣本數(shù)據(jù)高維特征空間近似最大線性無(wú)關(guān)向量組的方法對(duì)其進(jìn)行稀疏化處理，在保證分類準(zhǔn)確率的同時(shí)，增加了訓(xùn)練樣本的稀疏性，提高了計(jì)算效率。

在對(duì)最小二乘支持向量機(jī)稀疏化的過(guò)程中主要包括兩個(gè)步驟。

(1) 尋找高維空間的一組近似線性無(wú)關(guān)向量，構(gòu)造線性向量組，對(duì)位置參數(shù)樣本進(jìn)行稀疏表示。

首先尋找碼放位置參數(shù)樣本的特征子集B={(xj,yj)}j∈s?D,m=|S|≤N，使所有的樣本可以表示成該特征子集在特征空間的線性組合：

(6)

所以可得：

(7)

因此，分類判別函數(shù)表示為：

(8)

通過(guò)選擇參數(shù)v來(lái)去除特征空間中的近似相關(guān)向量，同時(shí)也可以控制子集B與樣本的逼近程度，稀疏化的流程如圖8所示。

圖8 稀疏化流程

(2) 利用稀疏樣本求解最優(yōu)分類判別函數(shù)。將式(7)、式(8)代入最小二乘支持向量?jī)?yōu)化目標(biāo)函數(shù)中，可得：

(9)

式(9)是關(guān)于β和b的凸二次規(guī)劃問(wèn)題，其中：β=[βS1,βS2,…,βSm]；ym=[yS1,yS2,…,ySm]∈Rm；D(ym)為以ym元素為對(duì)角元素構(gòu)成的對(duì)角矩陣；(Kmm)i,j∈S=κ(xi,xj)=Φ(xi)TΦ(xj)；yN=[y1,y2,…,yN]∈RN；D(yN)為以yN為對(duì)角元素構(gòu)成的對(duì)角矩陣；KNm=[km(x1),km(x2),…,km(xN)]T；km(xj)=[κ(xi,xS1),κ(xi,xS2),…,κ(xi,xSm)]T；1為元素全為1的單位列向量。最優(yōu)解可以通過(guò)以下條件求得：

(10)

對(duì)其求解可得關(guān)于β和b的方程組：

(11)

2.4 算法實(shí)現(xiàn)

在算法實(shí)現(xiàn)過(guò)程中，只需將深度支持向量機(jī)中的每一層替換為SLSSVM即可，實(shí)現(xiàn)多層最小二乘支持向量機(jī)的疊加，訓(xùn)練過(guò)程與DSVM相同，首先使用SLSSVM的輸入層對(duì)初始樣本進(jìn)行訓(xùn)練，然后使用降維公式對(duì)輸出層的結(jié)果進(jìn)行處理，并將處理結(jié)果作為第二層的輸入進(jìn)行訓(xùn)練，而DSLSSVM利用SLSSVM的系數(shù)β與向量組B構(gòu)造降維公式，這里降維公式可以表示為：

g(i)=ysvjβiκ(xj,x)+bj∈S

(12)

隨后逐層訓(xùn)練，直至輸出結(jié)果。通過(guò)DSLSSVM深層結(jié)構(gòu)對(duì)細(xì)膩碼放位置參數(shù)進(jìn)行訓(xùn)練，對(duì)其內(nèi)在規(guī)律進(jìn)行學(xué)習(xí)，既可以得到較高的識(shí)別準(zhǔn)確率，又可以減少運(yùn)算時(shí)間。

3 仿真實(shí)驗(yàn)

3.1 實(shí)驗(yàn)配置

本實(shí)驗(yàn)使用計(jì)算機(jī)主要硬件配置如表2所示。

表2 計(jì)算機(jī)主要硬件配置

仿真實(shí)驗(yàn)使用計(jì)算機(jī)運(yùn)行的操作系統(tǒng)為Microsoft Windows 7，本實(shí)驗(yàn)中的算法均使用Python語(yǔ)言進(jìn)行編寫，在機(jī)器學(xué)習(xí)方面使用scikit-learn模塊來(lái)實(shí)現(xiàn)，使用pandas和numpy數(shù)據(jù)庫(kù)對(duì)數(shù)據(jù)進(jìn)行處理。

3.2 訓(xùn)練數(shù)據(jù)

根據(jù)國(guó)際航空運(yùn)輸協(xié)會(huì)(International Air Transport Association，IATA)規(guī)定，隨身登機(jī)箱尺寸三邊之和不得超過(guò)115 cm，托運(yùn)行李箱尺寸不得超過(guò)158 cm，所以20英寸及以下的行李箱可以隨身帶入機(jī)艙，28英寸及以下的行李箱可以進(jìn)行托運(yùn)，現(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)研，目前機(jī)場(chǎng)采用的行李拖車大多數(shù)為三面護(hù)欄式行李拖車全車尺寸為300 cm×175 cm×100 cm。

在仿真實(shí)驗(yàn)中，我們將仿真過(guò)程分為兩個(gè)階段，即訓(xùn)練階段和工作階段。在訓(xùn)練階段，數(shù)據(jù)集由計(jì)算機(jī)自動(dòng)生成，首先系統(tǒng)會(huì)隨機(jī)生成要碼放行李類別，計(jì)算機(jī)根據(jù)當(dāng)前行李車布局情況，沿x軸方向依次遍歷所有可放位置并計(jì)算每個(gè)位置評(píng)估參數(shù)數(shù)值，每個(gè)位置生成一組數(shù)據(jù)，有經(jīng)驗(yàn)的碼放工人根據(jù)多年工作經(jīng)驗(yàn)選擇最佳位置進(jìn)行碼放，計(jì)算機(jī)將此位置進(jìn)行標(biāo)記，完成一個(gè)行李的碼放，重復(fù)以上過(guò)程直至整個(gè)行李車被裝滿，生成訓(xùn)練數(shù)據(jù)集。

3.3 不同分類模型對(duì)比實(shí)驗(yàn)

為了驗(yàn)證本文使用的DSLSSVM分類模型優(yōu)于其他模型分類準(zhǔn)確率，分別使用DSLSSVM、SVM、決策樹分類模型和樸素貝葉斯分類模型進(jìn)行對(duì)比實(shí)驗(yàn)。使用三組不同的行李碼放位置參數(shù)作為樣本進(jìn)行實(shí)驗(yàn)，每組實(shí)驗(yàn)包括5 000組數(shù)據(jù)，分別使用不同算法進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如表3所示。

表3 準(zhǔn)確率統(tǒng)計(jì)表(%)

續(xù)表3

可以看出，在本文的分類實(shí)驗(yàn)中， DSLSSVM分類準(zhǔn)確率最高，達(dá)到97.77%以上，比SVM分類模型的分類精度高3.73百分點(diǎn)，比樸樹貝葉斯分類模型高12.15百分點(diǎn)，所以DSLSSVM分類算法模型適用于本文的空間離散算法，并且可以滿足精度要求。

3.4 利用率對(duì)比實(shí)驗(yàn)

在確定了DSLSSVM分類模型的可行性后，將訓(xùn)練數(shù)據(jù)集定為8 000組，使用10折交叉驗(yàn)證法對(duì)DSLSSVM分類模型進(jìn)行訓(xùn)練，并將訓(xùn)練好的模型保存。在利用率對(duì)比實(shí)驗(yàn)中，使用訓(xùn)練好的模型進(jìn)行仿真實(shí)驗(yàn)，圖9分別給出使用人工經(jīng)驗(yàn)碼放、基于機(jī)器學(xué)習(xí)的空間離散算法碼放、依次橫放、依次豎放和傳統(tǒng)的啟發(fā)式算法五種不同的碼放方法下得到的二維裝箱效果圖。

(a) 人工經(jīng)驗(yàn)碼放仿真圖

使用人工經(jīng)驗(yàn)進(jìn)行碼放仿真時(shí)，通過(guò)Python語(yǔ)言進(jìn)行編寫程序，使用計(jì)算機(jī)輸入設(shè)備鍵盤的方向鍵控制行李在行李車網(wǎng)格空間中的位置，模擬工人裝載的過(guò)程，通過(guò)工人日常積累的經(jīng)驗(yàn)根據(jù)行李的大小和行李車的布局情況調(diào)整行李碼放位置，將行李放在當(dāng)前布局情況下最佳碼放位置，完成一次碼放。

傳統(tǒng)的啟發(fā)式算法在解決裝箱問(wèn)題時(shí)大多采用“分層”和“分塊”的概念，本文在進(jìn)行仿真實(shí)驗(yàn)時(shí)根據(jù)文獻(xiàn)[18]提出的基于“塊”和“空間”的啟發(fā)式算法，對(duì)其算法進(jìn)行復(fù)現(xiàn)，作為對(duì)照進(jìn)行仿真實(shí)驗(yàn)。

在實(shí)驗(yàn)過(guò)程中，分別使用人工經(jīng)驗(yàn)碼放、基于空間離散算法的碼放策略、行李依次橫放、行李依次豎放和傳統(tǒng)啟發(fā)式算法的方式進(jìn)行碼放實(shí)驗(yàn)，每種碼放方式進(jìn)行三組實(shí)驗(yàn)，每組實(shí)驗(yàn)各碼放十次，統(tǒng)計(jì)其利用率如表4所示。

表4 利用率統(tǒng)計(jì)表(%)

通過(guò)與工人經(jīng)驗(yàn)碼放的對(duì)比實(shí)驗(yàn)可以看出，本文提出的空間離散的概念可以有效地將工人經(jīng)驗(yàn)映射到評(píng)價(jià)參數(shù)中，同時(shí)證明了本文提出的基于深度稀疏最小二乘支持向量機(jī)分類模型可以實(shí)現(xiàn)對(duì)行李參數(shù)的準(zhǔn)確分類，適用于空間離散算法。使用空間離散算法得到的空間利用率達(dá)到87.24%，接近有經(jīng)驗(yàn)的工人的碼放水平。與其他碼放方式進(jìn)行對(duì)比可以看出，比傳統(tǒng)啟發(fā)式算法得到的仿真結(jié)果高4.58百分比，比行李依次豎放利用率提高了12.07百分比，比依次橫放利用率提高了13.58百分比。綜上所述，該算法可以代替機(jī)場(chǎng)工人實(shí)現(xiàn)行李的自動(dòng)化裝載，并且可以達(dá)到與人工碼放行李較為接近的水平，與其他碼放方式相比可以得到較大的空間利用率，滿足機(jī)場(chǎng)高效運(yùn)輸?shù)幕疽蟆?/p>

3.5 運(yùn)算時(shí)間對(duì)比實(shí)驗(yàn)

在機(jī)場(chǎng)實(shí)際裝載的過(guò)程中，除了滿足空間利用率最大原則外還要考慮算法計(jì)算速度盡可能快，滿足在線碼放的要求。傳統(tǒng)的基于“塊”和“空間”的啟發(fā)式算法在進(jìn)行碼放位置的選擇時(shí)，采用啟發(fā)式搜索的方法遍歷所有可能碼放的位置，同時(shí)還將剩余的空間進(jìn)行選擇、劃分、合并，更是增加了可放位置的選擇，使得算法計(jì)算更加復(fù)雜，耗費(fèi)大量時(shí)間。

使用本文提出的基于空間離散的機(jī)場(chǎng)行李碼放策略與基于“塊”和“空間”的啟發(fā)式算法的碼放方法在相同的情況下進(jìn)行行李碼放作業(yè)，統(tǒng)計(jì)兩種不同算法裝入行李個(gè)數(shù)如表5所示。

表5 相同時(shí)間下裝入行李個(gè)數(shù)統(tǒng)計(jì)表

可以看出，在本文提出的基于空間離散算法的機(jī)場(chǎng)行李碼放策略在相同時(shí)間碼放行李個(gè)數(shù)遠(yuǎn)大于基于“塊”和“空間”的啟發(fā)式算法碼放的行李個(gè)數(shù)，并且對(duì)行李車的空間利用率較高，所以與傳統(tǒng)基于“塊”和“空間”的啟發(fā)式算法相比，本文算法更適合機(jī)場(chǎng)高速、高效率的要求。

4 結(jié) 語(yǔ)

為了解決機(jī)場(chǎng)行李在轉(zhuǎn)運(yùn)過(guò)程中存在的裝箱問(wèn)題，提出一種基于空間離散算法的機(jī)場(chǎng)行李碼放方法。通過(guò)分析機(jī)場(chǎng)行李碼放特點(diǎn)，定義行李碼放位置的評(píng)價(jià)參數(shù)，模擬有經(jīng)驗(yàn)工人的碼放過(guò)程，構(gòu)建訓(xùn)練樣本，使用DSLSSVM模型學(xué)習(xí)工人經(jīng)驗(yàn)，得到訓(xùn)練模型。在實(shí)際工作中，系統(tǒng)根據(jù)行里車內(nèi)不同局面給出不同的碼放方案，完成行李在線實(shí)時(shí)碼放。

仿真實(shí)驗(yàn)結(jié)果表明，通過(guò)該方法碼放的行李在空間利用率和效率方面可以達(dá)到與人工碼放行李比較接近的水平，可以滿足機(jī)場(chǎng)行李運(yùn)輸?shù)囊蟆２⑶蚁啾扔诨凇皦K”和“空間”的傳統(tǒng)啟發(fā)式算法，該方法在實(shí)現(xiàn)過(guò)程中減少了算法計(jì)算時(shí)間，提高了機(jī)場(chǎng)行李裝載效率，具有較強(qiáng)的實(shí)用性。