顏建影,石麗娜
(上海工程技術(shù)大學(xué) 航空運輸學(xué)院,上海 201620)
隨著中國經(jīng)濟持續(xù)穩(wěn)定的增長,對基礎(chǔ)設(shè)施的投資越來越大,使得人們的出行越發(fā)方便,越來越多的普通百姓把飛機作為一種交通方式的選擇,但隨著乘坐飛機旅客的持續(xù)增多,使得機場的運行配置資源越發(fā)緊張,運行管理變的越發(fā)重要。當(dāng)前,國內(nèi)開始不斷增建新機場或擴建機場,這種方式雖可以解決燃眉之急,但要想根本的解決機場運行資源緊張的局面,還要更加合理的使用運行資源,并且隨著智能化、高效機場建設(shè),對值機柜臺資源的動態(tài)配置,提高服務(wù)效率變得更加重要。機場航站樓中運行最為復(fù)雜的流程為值機流程,因此對于提高旅客滿意度,實現(xiàn)資源的高效利用具有重要作用[1]。因此,確定所需值機柜臺配置數(shù)量是機場和航空公司對于旅客到達機場航站樓所需解決的首要問題。
此前,關(guān)于值機柜臺資源分配問題,相關(guān)人員也進行了多方面的研究。文獻[2]提出把值機柜臺的分配問題轉(zhuǎn)換成多維放置問題,即在空間有限的情況下,盡可能多的放置值機柜臺。但其中并沒考慮高峰期旅客排隊等候值機,在機場值機區(qū)域有限的情況下,每多放置一個柜臺旅客排隊等候值機的區(qū)域則會相應(yīng)減少,使得原本就擁擠的值機區(qū)域越發(fā)擁擠,反而使旅客滿意度降低。文獻[3]通過調(diào)查機場旅客到達時刻以及航班離港時間數(shù)據(jù),建立值機柜臺的指派優(yōu)化模型,該模型采用計算機仿真軟件運行模擬,并未涉及具體算法。文獻[4]提出了協(xié)助機場分配公用值機柜臺的整數(shù)規(guī)劃模型,但該模型考慮的參數(shù)過多,求解過于復(fù)雜,實際應(yīng)用困難。文獻[5]建立了在達到旅客滿意度的條件下,使人工成本最小的模型。該模型將值機和安檢都考慮在內(nèi),并不是單純對值機成本的求解,且對旅客的到達過程假設(shè)為單純的指數(shù)分布,而實際中值機旅客的到達曲線往往為上下浮動的曲線。同時,隨著自動值機設(shè)備的發(fā)展,使用自助值機設(shè)備進行值機的旅客也逐年增多。文獻[6]中以同時考慮租用柜臺成本和顧客時間成本為前提,將自助值機柜臺轉(zhuǎn)化為人工值機柜臺進行分析,但在旅客值機的選擇時只是單純的將有行李的旅客分為人工值機,而無行李的旅客選擇自助值機。文獻[7]為求算最佳的值機柜臺排班策略,運用派邇值機柜臺規(guī)劃實驗系統(tǒng),將人工值機柜臺和自助值機柜臺分開進行分析,求解最小的人工值機柜臺成本。通過計算機對值機流程進行仿真分析,沒有涉及到具體的算法且值機柜臺開放數(shù)量始終為一定值,而現(xiàn)實中各個時段開放的值機數(shù)都是變化的。文獻[8]將人工值機柜臺和自助值機柜臺資源共同分析研究,以所有旅客行走距離之和最短為優(yōu)化目標(biāo),實現(xiàn)對自助值機柜臺和人工值機柜臺的合理分配,但文中并未考慮旅客的到達分布以及值機排隊等待時間。
當(dāng)前機場值機柜臺的分配,越來越重視自助值機設(shè)備的使用。因此,本文在求解值機系統(tǒng)所得凈收益最大時,首先將滿足一定條件的旅客滿意度約束考慮進去,然后在分析人工值機柜臺時,將自助值機設(shè)備的使用情況也進行了分析,最后將自助值機設(shè)備使用產(chǎn)生的收益考慮進去。通過實例分析,最終得到相應(yīng)的動態(tài)值機柜臺分配數(shù)量,為機場航站樓值機系統(tǒng)柜臺的資源配置提供一定的參考。
旅客值機是機場離港流程中的一部分,分為人工值機和自助值機兩種方式。旅客到達機場航站樓值機大廳,根據(jù)個人喜好選擇人工值機或自助值機子系統(tǒng),同時根據(jù)各系統(tǒng)的排隊情況,選擇最短的隊列等候值機。
值機流程作為航站樓旅客流程的子系統(tǒng),其運行效率的高低,決定了旅客其它步驟的運行。其中,旅客到達的過程與航班時刻表、航班旅客人數(shù)以及旅客到達分布曲線有關(guān)。某一時刻t的旅客到達率γ(人/min)為各航班該時刻旅客到達率之和,如公式(1)。
(1)
式中,l表示t時刻內(nèi)航班的個數(shù),a={1,2,…,l}。
值機過程服從M/M/k的排隊模型排隊系統(tǒng)[9],有k個服務(wù)臺,各服務(wù)臺服務(wù)率等于u(人/min),總服務(wù)率為ku。因此,值機柜臺的服務(wù)強度為值機系統(tǒng)總到達率與總服務(wù)率之比,值機柜臺服務(wù)強度ρ應(yīng)小于1。
(2)
(3)
(4)
其中,式(2)為服務(wù)強度計算公式;式(3)為旅客值機排隊平均旅客數(shù);式(4)為值機排隊旅客平均排隊時間(min/人);k為開放的值機柜臺個數(shù)。
目前,機場一般要求航站樓的值機服務(wù)必須滿足一定指標(biāo)。見表1所列:中國民用航空局發(fā)布的民用運輸機場服務(wù)質(zhì)量標(biāo)準(zhǔn)[10]。因此,本文在求解值機柜臺開放數(shù)量時,應(yīng)以滿足機場值機排隊等待時間標(biāo)準(zhǔn)為前提。即:
Wt≤Wc
(5)
式中,Wc為某服務(wù)水平下,標(biāo)準(zhǔn)值機排隊等待時間。
根據(jù)以上對值機流程的分析,為便于計算,對值機過程進行以下假設(shè):
(1)機場到達旅客全部使用值機柜臺進行值機,即人工值機柜臺和一體化自助值機設(shè)備。
(2)值機過程滿足先到先服務(wù)的原則。
(3)值機排隊系統(tǒng)的各時段所需柜臺數(shù)為正整數(shù)。
(4)值機方式為公用柜臺,旅客到達時選擇最短隊列排隊。
(5)旅客全為經(jīng)濟艙旅客。
(6)人工值機柜臺配置服務(wù)人員,自助值機設(shè)備不配置服務(wù)人員。
由于旅客選擇值機方式具有很大的隨機性,旅客選擇偏好,受旅客個人特征、值機設(shè)備特征等影響[11]。根據(jù)文獻[12],得到某一機場早高峰時段值機排隊系統(tǒng)。旅客對于人工值機柜臺和自助值機柜臺的預(yù)測選擇偏好[12],其選擇比例見表2。
表2 旅客不同值機方式選擇比例
由表2可知,在值機的早高峰時段,人工值機方式仍占據(jù)主導(dǎo)作用,但自助值機的占比相比平峰時段在高峰時段明顯增大。說明高峰時段,由于旅客人數(shù)增多,值機排隊時間變長,選擇自助值機的旅客增多。因此,為了對機場繁忙時段值機柜臺分配進行分析,本文選擇早高峰時段的旅客到達進行問題分析。
2.3.1 模型中符號含義
t:值機時間按照一定時間間隔,平分為n個時間段,t≥1,t={1,2,…,n};
Xt:時間段t內(nèi),使用人工值機柜臺旅客所占比例,0≤Xt≤1;
Yt:時間段t內(nèi),使用自助值機柜臺旅客所占比例,0≤Yt≤1;
PU:人工值機柜臺服務(wù)一位旅客產(chǎn)生的收益;
PV:自助值機柜臺服務(wù)一位旅客產(chǎn)生的收益;
PW:開放一個值機柜臺單位時間成本。
2.3.2 目標(biāo)函數(shù)模型的確定
由上述分析可知,本文以滿足IATA(International Air Transport Association)C級旅客排隊等待時間為前提,以值機過程凈收益最大為目標(biāo)函數(shù),來優(yōu)化航站樓的值機柜臺資源分配問題。即在得到值機系統(tǒng)最大凈收益的同時,求得其分配的值機柜臺數(shù)量,凈收益越大表明值機系統(tǒng)的收益越高。
(6)
(7)
Wt≤Wc
(8)
kt≤C
(9)
式(7)表示值機工作人員的繁忙概率,應(yīng)控制在一個合理的范圍內(nèi)。太大,服務(wù)員容易疲勞出錯,導(dǎo)致效率下降;太小,值機工作效率降低,柜臺使用率不高。另外,其取值范圍應(yīng)該大一些,否則可能使問題解不可行,約束不滿足。
式(8)表示旅客值機排隊平均等待時間,應(yīng)滿足服務(wù)標(biāo)準(zhǔn)。本文選取國內(nèi)經(jīng)濟艙95%的旅客值機排隊等待時間不超過14 min。
式(9)表示開放的值機柜臺數(shù),該數(shù)值不可超過機場可開放最大值機柜臺數(shù)。其中C為可開放的最大值機柜臺個數(shù)。
通過上述函數(shù)模型,選取某機場早高峰8:00-11:30值機區(qū)域的所有航班的實際旅客到達作為實例分析,可開放值機柜臺總數(shù)C為30。
本文選取30 min作為時間間隔,如果間隔時間太短容易造成值機排班難度大,造成人員排班混亂[13]。根據(jù)實際旅客到達人數(shù),由公式(1)得到早高峰各時間段內(nèi)的旅客到達率,見表3。
表3 各時間間隔旅客到達率
由于人工和自助的值機服務(wù)時間沒有顯著差異[12],因此本文設(shè)定人工值機柜臺和自助值機柜臺旅客服務(wù)率相等,各柜臺的平均服務(wù)率u=23人/30 min。
首先,運用MATLAB對滿足約束條件的值機柜臺開放個數(shù)求解,得到各時段值機柜臺可開放數(shù)量(如圖1所示),以及與之對應(yīng)的值機人員繁忙概率(如圖2所示)。
圖1 各時間段值機柜臺可開放數(shù)量
圖2 值機柜臺可開放數(shù)量對應(yīng)值機人員繁忙概率
由圖2可知,值機人員繁忙概率最大達到了8.127 2,導(dǎo)致值機工作人員極度疲勞,最小卻僅為0.002 5,值機柜臺工作效率極其低下,資源浪費。因此,應(yīng)設(shè)定合理的取值范圍。同時為防止出現(xiàn)問題的不可行解,設(shè)定值機人員的繁忙概率取值為[0.25,0.91]。
模擬退火算法最早由Metropolis等[14]在1953年提出。其原理與固體的退火原理類似,如圖3所示。即將固體溫度加熱后,再使其緩緩降溫冷卻,最后在常溫時達到穩(wěn)定基態(tài)內(nèi)能最小。當(dāng)算法終止時,保存的最小解即為所求的最優(yōu)目標(biāo)函數(shù)值[15]。值機柜臺的分配問題,屬于NP難問題,若采用傳統(tǒng)方法,計算量和難度將會極大增加。因此,采用更加快速的方法來求解此類問題變得越發(fā)重要。1983年模擬退火算法第一次被引入優(yōu)化領(lǐng)域,由于能有效的近似求解具有NP復(fù)雜性的難題,克服其它優(yōu)化算法容易陷入局部最優(yōu)的缺陷,并對初值沒有強依賴關(guān)系。基于此,將設(shè)計模擬退火算法用來求解值機柜臺動態(tài)分配問題。
圖3 關(guān)系原理
4.2.1 初始解的生成
為擴大求解范圍,本文初始解以隨機數(shù)的方式產(chǎn)生。在MATLAB中運用隨機數(shù)生成程序,隨機生成一個一行七列取值為[1,29]的矩陣。
4.2.2 目標(biāo)函數(shù)的確定
本文值機柜臺分配問題的目標(biāo)函數(shù)S,是在滿足約束的前提下,得到的最大值機凈收益。進而得到各時段分配的值機柜臺數(shù)量,如公式(10)所示:
(10)
本文目標(biāo)函數(shù)求解為最大值,而模擬退火算法求解的是最小值。因此,在判斷是否接受新解時,改為當(dāng)新解大于舊解目標(biāo)函數(shù)時,則接受新解。
4.2.3 新解的產(chǎn)生
新解的產(chǎn)生應(yīng)簡單快速,以減少算法所用時間?;诖耍疚男陆獾纳赏ㄟ^交換的方式,以隨機概率的大小選擇以下兩種不同方式產(chǎn)生新解:
(1)二變換法
隨機選擇解中序號為u、v(設(shè)u 表4 二變換法 (2)三變換法 隨機選擇序號為u、v(設(shè)u 另外,由于目標(biāo)函數(shù)本身帶有約束條件,當(dāng)新解生成后,還要判斷是否滿足約束,如果滿足則進行算法下一步,否則根據(jù)新解服務(wù)強度的大小,進行相應(yīng)改變。(具體過程在算法步驟Step3中介紹) 4.2.4 Metropoils新解接受準(zhǔn)則 在模擬退火算法中,解的接受準(zhǔn)則為Metropoils準(zhǔn)則。因本文目標(biāo)函數(shù)為求最大值,即新解的接受條件為:若ΔS>0,則接受新解kj作為新的當(dāng)前解;如果ΔS<0,則新解kj按照接受概率P確定是否接受。如公式(11)、(12)所示。 ΔS=S(kj)-S(ki) (11) (12) 其中,ΔS為目標(biāo)函數(shù)差;1≤i 初始溫度T0:控制參數(shù)初始溫度T0=97。 衰減函數(shù)T:控制參數(shù)的衰減函數(shù)連續(xù)降溫表達式T=T×φ。φ是衰減函數(shù)的一個常數(shù),取值為[0.50,0.99]之間,本文取0.90。 終止溫度Tf:終止溫度即算法運行的停止準(zhǔn)則。一般終止溫度設(shè)為足夠小的正數(shù),取值為[0.01,5]之間,本文取3。 Markov鏈長度Lk:Lk即循環(huán)次數(shù),應(yīng)能在控制參數(shù)T的取值上達到平衡。取值一般為100 n,本文設(shè)Lk為700次。 根據(jù)前文設(shè)計,算法步驟如下: Step1令初始溫度T=T0,并按照上述所述方式生成一個初始解k0。 Step2令T等于冷卻進度表中的下一個值Ti。 Step3根據(jù)當(dāng)前解ki進行擾動,即進行交換操作,從而產(chǎn)生新解kj。判斷新解是否滿足柜臺分配的約束條件,如果滿足進行下一步,否則根據(jù)新解的服務(wù)強度ρ。如果ρ≥1,則kj進行加1操作,如果ρ<1,則kj=1,直到找到一個滿足約束條件的值機柜臺開放數(shù)量,并計算新解相應(yīng)的目標(biāo)函數(shù)值S(xj),進而得到ΔS。 Step5在溫度為Ti值下,重復(fù)進行Lk次擾動和接受循環(huán),即循環(huán)步驟3和4,直到滿足要求。 Step6判斷T是否達到終止標(biāo)準(zhǔn)。滿足,則停止運算輸出最優(yōu)目標(biāo)函數(shù)解,算法結(jié)束;否則,轉(zhuǎn)到步驟2繼續(xù)執(zhí)行。 算法流程如圖4所示。 圖4 模擬退火算法流程 設(shè)PU=10元/人、PV=5元/人、Pw=4元/min,通過MATLAB運用所設(shè)計的模擬退火算法求解目標(biāo)函數(shù),得到目標(biāo)函數(shù)(值機系統(tǒng))最大凈收益為265.92元。最優(yōu)利潤為1.27元/min。最終得到各時間段最大凈收益和配置的值機柜臺數(shù)量(如圖5所示),以及與之對應(yīng)的值機人員繁忙概率大小(如圖6所示)。 圖5 各時段最大凈收益與值機柜臺開放數(shù)量 圖6 各時間段值機人員最終繁忙概率 將本文采用模擬退火得到的值機柜臺分配數(shù)量,與以往采用啟發(fā)式和枚舉式相結(jié)合的方法對人工值機柜臺進行分配的結(jié)果進行對比,值機開放總數(shù)基本相同。說明了算法的有效性,但啟發(fā)與枚舉結(jié)合的方法,往往需要運算經(jīng)驗,并且人工運算需要大量時間,且相比本文所用算法,難以在機場實際應(yīng)用。同時本文計算在考慮使用自助值機設(shè)備的情況下,人工值機柜臺開放總數(shù)量為113個,相比以往只對人工值機分配數(shù)量,本文人工值機柜臺減少了18.7%的使用量,提高了值機系統(tǒng)資源的利用效率。同時,分配更加合理,為機場提供了不同的值機柜臺資源分配方案,見表5。 表5 不同時間段值機設(shè)備動態(tài)開放數(shù)量 本文為機場航站樓內(nèi)值機柜臺資源的配置研究,在滿足旅客滿意度約束標(biāo)準(zhǔn)的前提下,考慮值機員的繁忙程度,以系統(tǒng)凈收益最大為目標(biāo),通過設(shè)計的模擬退火算法,對值機柜臺資源進行動態(tài)配置求解。運用MATLAB進行實例分析,在P4,i5,1.19 GHz算法平均運行11 s,得到最大的系統(tǒng)凈收益,進而得到各時間段內(nèi)值機柜臺的分配數(shù)量。結(jié)果表明,相比只考慮對人工值機柜臺的配置及采用啟發(fā)式運算的方法,本文在考慮了自助值機柜臺分配方式下,各時間段使用的值機柜臺數(shù)量分配更加合理,同時運算所用時間大大減少,提高了值機系統(tǒng)運行效率和旅客滿意度,為機場值機柜臺的運行配置提供了可行參考。4.3 運行參數(shù)
4.4 模擬退火算法步驟
5 實例分析
6 結(jié)束語