顏建影，石麗娜

(上海工程技術(shù)大學(xué) 航空運(yùn)輸學(xué)院，上海 201620)

0 引 言

隨著中國經(jīng)濟(jì)持續(xù)穩(wěn)定的增長，對(duì)基礎(chǔ)設(shè)施的投資越來越大，使得人們的出行越發(fā)方便，越來越多的普通百姓把飛機(jī)作為一種交通方式的選擇，但隨著乘坐飛機(jī)旅客的持續(xù)增多，使得機(jī)場的運(yùn)行配置資源越發(fā)緊張，運(yùn)行管理變的越發(fā)重要。當(dāng)前，國內(nèi)開始不斷增建新機(jī)場或擴(kuò)建機(jī)場，這種方式雖可以解決燃眉之急，但要想根本的解決機(jī)場運(yùn)行資源緊張的局面，還要更加合理的使用運(yùn)行資源，并且隨著智能化、高效機(jī)場建設(shè)，對(duì)值機(jī)柜臺(tái)資源的動(dòng)態(tài)配置，提高服務(wù)效率變得更加重要。機(jī)場航站樓中運(yùn)行最為復(fù)雜的流程為值機(jī)流程，因此對(duì)于提高旅客滿意度，實(shí)現(xiàn)資源的高效利用具有重要作用[1]。因此，確定所需值機(jī)柜臺(tái)配置數(shù)量是機(jī)場和航空公司對(duì)于旅客到達(dá)機(jī)場航站樓所需解決的首要問題。

此前，關(guān)于值機(jī)柜臺(tái)資源分配問題，相關(guān)人員也進(jìn)行了多方面的研究。文獻(xiàn)[2]提出把值機(jī)柜臺(tái)的分配問題轉(zhuǎn)換成多維放置問題，即在空間有限的情況下，盡可能多的放置值機(jī)柜臺(tái)。但其中并沒考慮高峰期旅客排隊(duì)等候值機(jī)，在機(jī)場值機(jī)區(qū)域有限的情況下，每多放置一個(gè)柜臺(tái)旅客排隊(duì)等候值機(jī)的區(qū)域則會(huì)相應(yīng)減少，使得原本就擁擠的值機(jī)區(qū)域越發(fā)擁擠，反而使旅客滿意度降低。文獻(xiàn)[3]通過調(diào)查機(jī)場旅客到達(dá)時(shí)刻以及航班離港時(shí)間數(shù)據(jù)，建立值機(jī)柜臺(tái)的指派優(yōu)化模型，該模型采用計(jì)算機(jī)仿真軟件運(yùn)行模擬，并未涉及具體算法。文獻(xiàn)[4]提出了協(xié)助機(jī)場分配公用值機(jī)柜臺(tái)的整數(shù)規(guī)劃模型，但該模型考慮的參數(shù)過多，求解過于復(fù)雜，實(shí)際應(yīng)用困難。文獻(xiàn)[5]建立了在達(dá)到旅客滿意度的條件下，使人工成本最小的模型。該模型將值機(jī)和安檢都考慮在內(nèi)，并不是單純對(duì)值機(jī)成本的求解，且對(duì)旅客的到達(dá)過程假設(shè)為單純的指數(shù)分布，而實(shí)際中值機(jī)旅客的到達(dá)曲線往往為上下浮動(dòng)的曲線。同時(shí)，隨著自動(dòng)值機(jī)設(shè)備的發(fā)展，使用自助值機(jī)設(shè)備進(jìn)行值機(jī)的旅客也逐年增多。文獻(xiàn)[6]中以同時(shí)考慮租用柜臺(tái)成本和顧客時(shí)間成本為前提，將自助值機(jī)柜臺(tái)轉(zhuǎn)化為人工值機(jī)柜臺(tái)進(jìn)行分析，但在旅客值機(jī)的選擇時(shí)只是單純的將有行李的旅客分為人工值機(jī)，而無行李的旅客選擇自助值機(jī)。文獻(xiàn)[7]為求算最佳的值機(jī)柜臺(tái)排班策略，運(yùn)用派邇值機(jī)柜臺(tái)規(guī)劃實(shí)驗(yàn)系統(tǒng)，將人工值機(jī)柜臺(tái)和自助值機(jī)柜臺(tái)分開進(jìn)行分析，求解最小的人工值機(jī)柜臺(tái)成本。通過計(jì)算機(jī)對(duì)值機(jī)流程進(jìn)行仿真分析，沒有涉及到具體的算法且值機(jī)柜臺(tái)開放數(shù)量始終為一定值，而現(xiàn)實(shí)中各個(gè)時(shí)段開放的值機(jī)數(shù)都是變化的。文獻(xiàn)[8]將人工值機(jī)柜臺(tái)和自助值機(jī)柜臺(tái)資源共同分析研究，以所有旅客行走距離之和最短為優(yōu)化目標(biāo)，實(shí)現(xiàn)對(duì)自助值機(jī)柜臺(tái)和人工值機(jī)柜臺(tái)的合理分配，但文中并未考慮旅客的到達(dá)分布以及值機(jī)排隊(duì)等待時(shí)間。

當(dāng)前機(jī)場值機(jī)柜臺(tái)的分配，越來越重視自助值機(jī)設(shè)備的使用。因此，本文在求解值機(jī)系統(tǒng)所得凈收益最大時(shí)，首先將滿足一定條件的旅客滿意度約束考慮進(jìn)去，然后在分析人工值機(jī)柜臺(tái)時(shí)，將自助值機(jī)設(shè)備的使用情況也進(jìn)行了分析，最后將自助值機(jī)設(shè)備使用產(chǎn)生的收益考慮進(jìn)去。通過實(shí)例分析，最終得到相應(yīng)的動(dòng)態(tài)值機(jī)柜臺(tái)分配數(shù)量，為機(jī)場航站樓值機(jī)系統(tǒng)柜臺(tái)的資源配置提供一定的參考。

1 機(jī)場值機(jī)流程的分析

旅客值機(jī)是機(jī)場離港流程中的一部分，分為人工值機(jī)和自助值機(jī)兩種方式。旅客到達(dá)機(jī)場航站樓值機(jī)大廳，根據(jù)個(gè)人喜好選擇人工值機(jī)或自助值機(jī)子系統(tǒng)，同時(shí)根據(jù)各系統(tǒng)的排隊(duì)情況，選擇最短的隊(duì)列等候值機(jī)。

1.1 值機(jī)流程排隊(duì)系統(tǒng)

值機(jī)流程作為航站樓旅客流程的子系統(tǒng)，其運(yùn)行效率的高低，決定了旅客其它步驟的運(yùn)行。其中，旅客到達(dá)的過程與航班時(shí)刻表、航班旅客人數(shù)以及旅客到達(dá)分布曲線有關(guān)。某一時(shí)刻t的旅客到達(dá)率γ(人/min)為各航班該時(shí)刻旅客到達(dá)率之和，如公式(1)。

(1)

式中，l表示t時(shí)刻內(nèi)航班的個(gè)數(shù)，a={1,2,…,l}。

值機(jī)過程服從M/M/k的排隊(duì)模型排隊(duì)系統(tǒng)[9]，有k個(gè)服務(wù)臺(tái)，各服務(wù)臺(tái)服務(wù)率等于u(人/min)，總服務(wù)率為ku。因此，值機(jī)柜臺(tái)的服務(wù)強(qiáng)度為值機(jī)系統(tǒng)總到達(dá)率與總服務(wù)率之比，值機(jī)柜臺(tái)服務(wù)強(qiáng)度ρ應(yīng)小于1。

(2)

(3)

(4)

其中，式(2)為服務(wù)強(qiáng)度計(jì)算公式；式(3)為旅客值機(jī)排隊(duì)平均旅客數(shù)；式(4)為值機(jī)排隊(duì)旅客平均排隊(duì)時(shí)間(min/人)；k為開放的值機(jī)柜臺(tái)個(gè)數(shù)。

1.2 基于服務(wù)標(biāo)準(zhǔn)的值機(jī)柜臺(tái)資源配置

目前，機(jī)場一般要求航站樓的值機(jī)服務(wù)必須滿足一定指標(biāo)。見表1所列：中國民用航空局發(fā)布的民用運(yùn)輸機(jī)場服務(wù)質(zhì)量標(biāo)準(zhǔn)[10]。因此，本文在求解值機(jī)柜臺(tái)開放數(shù)量時(shí)，應(yīng)以滿足機(jī)場值機(jī)排隊(duì)等待時(shí)間標(biāo)準(zhǔn)為前提。即：

Wt≤Wc

(5)

式中，Wc為某服務(wù)水平下，標(biāo)準(zhǔn)值機(jī)排隊(duì)等待時(shí)間。

2 值機(jī)柜臺(tái)分配模型的建立

2.1 假設(shè)條件

根據(jù)以上對(duì)值機(jī)流程的分析，為便于計(jì)算，對(duì)值機(jī)過程進(jìn)行以下假設(shè)：

(1)機(jī)場到達(dá)旅客全部使用值機(jī)柜臺(tái)進(jìn)行值機(jī)，即人工值機(jī)柜臺(tái)和一體化自助值機(jī)設(shè)備。

(2)值機(jī)過程滿足先到先服務(wù)的原則。

(3)值機(jī)排隊(duì)系統(tǒng)的各時(shí)段所需柜臺(tái)數(shù)為正整數(shù)。

(4)值機(jī)方式為公用柜臺(tái)，旅客到達(dá)時(shí)選擇最短隊(duì)列排隊(duì)。

(5)旅客全為經(jīng)濟(jì)艙旅客。

(6)人工值機(jī)柜臺(tái)配置服務(wù)人員，自助值機(jī)設(shè)備不配置服務(wù)人員。

2.2 不同時(shí)間段值機(jī)方式的選擇

由于旅客選擇值機(jī)方式具有很大的隨機(jī)性，旅客選擇偏好，受旅客個(gè)人特征、值機(jī)設(shè)備特征等影響[11]。根據(jù)文獻(xiàn)[12]，得到某一機(jī)場早高峰時(shí)段值機(jī)排隊(duì)系統(tǒng)。旅客對(duì)于人工值機(jī)柜臺(tái)和自助值機(jī)柜臺(tái)的預(yù)測選擇偏好[12]，其選擇比例見表2。

表2 旅客不同值機(jī)方式選擇比例

由表2可知，在值機(jī)的早高峰時(shí)段，人工值機(jī)方式仍占據(jù)主導(dǎo)作用，但自助值機(jī)的占比相比平峰時(shí)段在高峰時(shí)段明顯增大。說明高峰時(shí)段，由于旅客人數(shù)增多，值機(jī)排隊(duì)時(shí)間變長，選擇自助值機(jī)的旅客增多。因此，為了對(duì)機(jī)場繁忙時(shí)段值機(jī)柜臺(tái)分配進(jìn)行分析，本文選擇早高峰時(shí)段的旅客到達(dá)進(jìn)行問題分析。

2.3 值機(jī)柜臺(tái)分配模型的建立

2.3.1 模型中符號(hào)含義

t：值機(jī)時(shí)間按照一定時(shí)間間隔，平分為n個(gè)時(shí)間段，t≥1,t={1,2,…,n}；

Xt：時(shí)間段t內(nèi)，使用人工值機(jī)柜臺(tái)旅客所占比例，0≤Xt≤1；

Yt：時(shí)間段t內(nèi)，使用自助值機(jī)柜臺(tái)旅客所占比例，0≤Yt≤1；

PU：人工值機(jī)柜臺(tái)服務(wù)一位旅客產(chǎn)生的收益；

PV：自助值機(jī)柜臺(tái)服務(wù)一位旅客產(chǎn)生的收益；

PW：開放一個(gè)值機(jī)柜臺(tái)單位時(shí)間成本。

2.3.2 目標(biāo)函數(shù)模型的確定

由上述分析可知，本文以滿足IATA(International Air Transport Association)C級(jí)旅客排隊(duì)等待時(shí)間為前提，以值機(jī)過程凈收益最大為目標(biāo)函數(shù)，來優(yōu)化航站樓的值機(jī)柜臺(tái)資源分配問題。即在得到值機(jī)系統(tǒng)最大凈收益的同時(shí)，求得其分配的值機(jī)柜臺(tái)數(shù)量，凈收益越大表明值機(jī)系統(tǒng)的收益越高。

(6)

(7)

Wt≤Wc

(8)

kt≤C

(9)

式(7)表示值機(jī)工作人員的繁忙概率，應(yīng)控制在一個(gè)合理的范圍內(nèi)。太大，服務(wù)員容易疲勞出錯(cuò)，導(dǎo)致效率下降；太小，值機(jī)工作效率降低，柜臺(tái)使用率不高。另外，其取值范圍應(yīng)該大一些，否則可能使問題解不可行，約束不滿足。

式(8)表示旅客值機(jī)排隊(duì)平均等待時(shí)間，應(yīng)滿足服務(wù)標(biāo)準(zhǔn)。本文選取國內(nèi)經(jīng)濟(jì)艙95%的旅客值機(jī)排隊(duì)等待時(shí)間不超過14 min。

式(9)表示開放的值機(jī)柜臺(tái)數(shù)，該數(shù)值不可超過機(jī)場可開放最大值機(jī)柜臺(tái)數(shù)。其中C為可開放的最大值機(jī)柜臺(tái)個(gè)數(shù)。

3 值機(jī)柜臺(tái)動(dòng)態(tài)分配參數(shù)設(shè)定

通過上述函數(shù)模型，選取某機(jī)場早高峰8：00-11：30值機(jī)區(qū)域的所有航班的實(shí)際旅客到達(dá)作為實(shí)例分析，可開放值機(jī)柜臺(tái)總數(shù)C為30。

3.1 旅客到達(dá)率的確定

本文選取30 min作為時(shí)間間隔，如果間隔時(shí)間太短容易造成值機(jī)排班難度大，造成人員排班混亂[13]。根據(jù)實(shí)際旅客到達(dá)人數(shù)，由公式(1)得到早高峰各時(shí)間段內(nèi)的旅客到達(dá)率，見表3。

表3 各時(shí)間間隔旅客到達(dá)率

3.2 值機(jī)工作人員繁忙概率取值區(qū)間的確定

由于人工和自助的值機(jī)服務(wù)時(shí)間沒有顯著差異[12]，因此本文設(shè)定人工值機(jī)柜臺(tái)和自助值機(jī)柜臺(tái)旅客服務(wù)率相等，各柜臺(tái)的平均服務(wù)率u=23人/30 min。

首先，運(yùn)用MATLAB對(duì)滿足約束條件的值機(jī)柜臺(tái)開放個(gè)數(shù)求解，得到各時(shí)段值機(jī)柜臺(tái)可開放數(shù)量(如圖1所示)，以及與之對(duì)應(yīng)的值機(jī)人員繁忙概率(如圖2所示)。

圖1 各時(shí)間段值機(jī)柜臺(tái)可開放數(shù)量

圖2 值機(jī)柜臺(tái)可開放數(shù)量對(duì)應(yīng)值機(jī)人員繁忙概率

由圖2可知，值機(jī)人員繁忙概率最大達(dá)到了8.127 2，導(dǎo)致值機(jī)工作人員極度疲勞，最小卻僅為0.002 5，值機(jī)柜臺(tái)工作效率極其低下，資源浪費(fèi)。因此，應(yīng)設(shè)定合理的取值范圍。同時(shí)為防止出現(xiàn)問題的不可行解，設(shè)定值機(jī)人員的繁忙概率取值為[0.25,0.91]。

4 值機(jī)柜臺(tái)動(dòng)態(tài)配置的模擬退火算法設(shè)計(jì)

4.1 分配問題的模擬退火算法

模擬退火算法最早由Metropolis等[14]在1953年提出。其原理與固體的退火原理類似，如圖3所示。即將固體溫度加熱后，再使其緩緩降溫冷卻，最后在常溫時(shí)達(dá)到穩(wěn)定基態(tài)內(nèi)能最小。當(dāng)算法終止時(shí)，保存的最小解即為所求的最優(yōu)目標(biāo)函數(shù)值[15]。值機(jī)柜臺(tái)的分配問題，屬于NP難問題，若采用傳統(tǒng)方法，計(jì)算量和難度將會(huì)極大增加。因此，采用更加快速的方法來求解此類問題變得越發(fā)重要。1983年模擬退火算法第一次被引入優(yōu)化領(lǐng)域，由于能有效的近似求解具有NP復(fù)雜性的難題，克服其它優(yōu)化算法容易陷入局部最優(yōu)的缺陷，并對(duì)初值沒有強(qiáng)依賴關(guān)系?；诖耍瑢⒃O(shè)計(jì)模擬退火算法用來求解值機(jī)柜臺(tái)動(dòng)態(tài)分配問題。

圖3 關(guān)系原理

4.2 模擬退火算法實(shí)現(xiàn)

4.2.1 初始解的生成

為擴(kuò)大求解范圍，本文初始解以隨機(jī)數(shù)的方式產(chǎn)生。在MATLAB中運(yùn)用隨機(jī)數(shù)生成程序，隨機(jī)生成一個(gè)一行七列取值為[1,29]的矩陣。

4.2.2 目標(biāo)函數(shù)的確定

本文值機(jī)柜臺(tái)分配問題的目標(biāo)函數(shù)S，是在滿足約束的前提下，得到的最大值機(jī)凈收益。進(jìn)而得到各時(shí)段分配的值機(jī)柜臺(tái)數(shù)量，如公式(10)所示：

(10)

本文目標(biāo)函數(shù)求解為最大值，而模擬退火算法求解的是最小值。因此，在判斷是否接受新解時(shí)，改為當(dāng)新解大于舊解目標(biāo)函數(shù)時(shí)，則接受新解。

4.2.3 新解的產(chǎn)生

新解的產(chǎn)生應(yīng)簡單快速，以減少算法所用時(shí)間?；诖?，本文新解的生成通過交換的方式，以隨機(jī)概率的大小選擇以下兩種不同方式產(chǎn)生新解：

(1)二變換法

隨機(jī)選擇解中序號(hào)為u、v(設(shè)u

表4 二變換法

(2)三變換法

隨機(jī)選擇序號(hào)為u、v(設(shè)u

另外，由于目標(biāo)函數(shù)本身帶有約束條件，當(dāng)新解生成后，還要判斷是否滿足約束，如果滿足則進(jìn)行算法下一步，否則根據(jù)新解服務(wù)強(qiáng)度的大小，進(jìn)行相應(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

4.3 運(yùn)行參數(shù)

初始溫度T0：控制參數(shù)初始溫度T0=97。

衰減函數(shù)T：控制參數(shù)的衰減函數(shù)連續(xù)降溫表達(dá)式T=T×φ。φ是衰減函數(shù)的一個(gè)常數(shù)，取值為[0.50,0.99]之間，本文取0.90。

終止溫度Tf：終止溫度即算法運(yùn)行的停止準(zhǔn)則。一般終止溫度設(shè)為足夠小的正數(shù)，取值為[0.01,5]之間，本文取3。

Markov鏈長度Lk：Lk即循環(huán)次數(shù)，應(yīng)能在控制參數(shù)T的取值上達(dá)到平衡。取值一般為100 n，本文設(shè)Lk為700次。

4.4 模擬退火算法步驟

根據(jù)前文設(shè)計(jì)，算法步驟如下：

Step1令初始溫度T=T0，并按照上述所述方式生成一個(gè)初始解k0。

Step2令T等于冷卻進(jìn)度表中的下一個(gè)值Ti。

Step3根據(jù)當(dāng)前解ki進(jìn)行擾動(dòng)，即進(jìn)行交換操作，從而產(chǎn)生新解kj。判斷新解是否滿足柜臺(tái)分配的約束條件，如果滿足進(jìn)行下一步，否則根據(jù)新解的服務(wù)強(qiáng)度ρ。如果ρ≥1，則kj進(jìn)行加1操作，如果ρ<1，則kj=1，直到找到一個(gè)滿足約束條件的值機(jī)柜臺(tái)開放數(shù)量，并計(jì)算新解相應(yīng)的目標(biāo)函數(shù)值S(xj)，進(jìn)而得到ΔS。

Step5在溫度為Ti值下，重復(fù)進(jìn)行Lk次擾動(dòng)和接受循環(huán)，即循環(huán)步驟3和4，直到滿足要求。

Step6判斷T是否達(dá)到終止標(biāo)準(zhǔn)。滿足，則停止運(yùn)算輸出最優(yōu)目標(biāo)函數(shù)解，算法結(jié)束；否則，轉(zhuǎn)到步驟2繼續(xù)執(zhí)行。

算法流程如圖4所示。

圖4 模擬退火算法流程

5 實(shí)例分析

設(shè)PU=10元/人、PV=5元/人、Pw=4元/min，通過MATLAB運(yùn)用所設(shè)計(jì)的模擬退火算法求解目標(biāo)函數(shù)，得到目標(biāo)函數(shù)(值機(jī)系統(tǒng))最大凈收益為265.92元。最優(yōu)利潤為1.27元/min。最終得到各時(shí)間段最大凈收益和配置的值機(jī)柜臺(tái)數(shù)量(如圖5所示)，以及與之對(duì)應(yīng)的值機(jī)人員繁忙概率大小(如圖6所示)。

圖5 各時(shí)段最大凈收益與值機(jī)柜臺(tái)開放數(shù)量

圖6 各時(shí)間段值機(jī)人員最終繁忙概率

將本文采用模擬退火得到的值機(jī)柜臺(tái)分配數(shù)量，與以往采用啟發(fā)式和枚舉式相結(jié)合的方法對(duì)人工值機(jī)柜臺(tái)進(jìn)行分配的結(jié)果進(jìn)行對(duì)比，值機(jī)開放總數(shù)基本相同。說明了算法的有效性，但啟發(fā)與枚舉結(jié)合的方法，往往需要運(yùn)算經(jīng)驗(yàn)，并且人工運(yùn)算需要大量時(shí)間，且相比本文所用算法，難以在機(jī)場實(shí)際應(yīng)用。同時(shí)本文計(jì)算在考慮使用自助值機(jī)設(shè)備的情況下，人工值機(jī)柜臺(tái)開放總數(shù)量為113個(gè)，相比以往只對(duì)人工值機(jī)分配數(shù)量，本文人工值機(jī)柜臺(tái)減少了18.7%的使用量，提高了值機(jī)系統(tǒng)資源的利用效率。同時(shí)，分配更加合理，為機(jī)場提供了不同的值機(jī)柜臺(tái)資源分配方案，見表5。

表5 不同時(shí)間段值機(jī)設(shè)備動(dòng)態(tài)開放數(shù)量

6 結(jié)束語

本文為機(jī)場航站樓內(nèi)值機(jī)柜臺(tái)資源的配置研究，在滿足旅客滿意度約束標(biāo)準(zhǔn)的前提下，考慮值機(jī)員的繁忙程度，以系統(tǒng)凈收益最大為目標(biāo)，通過設(shè)計(jì)的模擬退火算法，對(duì)值機(jī)柜臺(tái)資源進(jìn)行動(dòng)態(tài)配置求解。運(yùn)用MATLAB進(jìn)行實(shí)例分析，在P4，i5,1.19 GHz算法平均運(yùn)行11 s，得到最大的系統(tǒng)凈收益，進(jìn)而得到各時(shí)間段內(nèi)值機(jī)柜臺(tái)的分配數(shù)量。結(jié)果表明，相比只考慮對(duì)人工值機(jī)柜臺(tái)的配置及采用啟發(fā)式運(yùn)算的方法，本文在考慮了自助值機(jī)柜臺(tái)分配方式下，各時(shí)間段使用的值機(jī)柜臺(tái)數(shù)量分配更加合理，同時(shí)運(yùn)算所用時(shí)間大大減少，提高了值機(jī)系統(tǒng)運(yùn)行效率和旅客滿意度，為機(jī)場值機(jī)柜臺(tái)的運(yùn)行配置提供了可行參考。