任新惠，焦 陽，徐小冰

(1.中國民航大學(xué)經(jīng)濟(jì)與管理學(xué)院，天津300300；2.天津中科智能技術(shù)研究院，天津300300；3.長沙南方職業(yè)學(xué)院，長沙410000)

0 引 言

登機(jī)時(shí)間是旅客周轉(zhuǎn)時(shí)間中的重要組成部分，據(jù)Nyquist 等[1]研究，航班周轉(zhuǎn)時(shí)間每減少1 min就會節(jié)省約30美元.登機(jī)時(shí)間減少可以提高飛機(jī)的飛行次數(shù)，增加停機(jī)位服務(wù)飛機(jī)的數(shù)量[2]；對旅客來說，在登機(jī)口、廊橋或機(jī)艙過道等待時(shí)間縮短會使整個(gè)登機(jī)過程感知更加輕松[3].

登機(jī)問題的目標(biāo)通常為登機(jī)時(shí)間最小，研究方法以仿真模擬和數(shù)學(xué)優(yōu)化為主.Steffen[4]利用馬爾可夫—蒙特卡洛優(yōu)化算法提出Steffen 登機(jī)策略.Qiang 等[5]建立了座位吸引值模型和旅客選座行為模型研究自由登機(jī)策略.還有一些在已有策略基礎(chǔ)上，從不同方面進(jìn)行策略優(yōu)化的研究.學(xué)者考慮到乘客放置行李過程是造成登機(jī)延誤的關(guān)鍵因素[6-8]，從行李方面進(jìn)行優(yōu)化，任新惠等基于過道干擾轉(zhuǎn)移思想提出了一種按行李數(shù)量安排座位的登機(jī)新策略[9]，建立多格子元胞自動機(jī)登機(jī)模型，提出了多行李優(yōu)先登機(jī)策略[10].Milne 提出了一個(gè)將行李平均分布的座位預(yù)分配算法[6]；使用混合整數(shù)規(guī)劃模型求解，根據(jù)旅客攜帶的行李數(shù)量分配座位[7]；Milne 等[11]運(yùn)用兩階段混合整數(shù)規(guī)劃模型分配旅客座位，進(jìn)一步優(yōu)化了登機(jī)過程.

以往研究多集中于提出新策略或?qū)Σ呗赃M(jìn)行優(yōu)化改進(jìn)，但仍存在放置行李影響登機(jī)時(shí)間的情況，說明從行李方面還有進(jìn)一步優(yōu)化的空間.此外，以往登機(jī)時(shí)間模型通常用過道干擾和座位干擾的時(shí)間總和來代替登機(jī)時(shí)間，實(shí)際上，座位干擾可以分為有效座位干擾和無效座位干擾[12]，Kierzkowski等[8]通過統(tǒng)計(jì)5 000多位旅客的干擾情況得出，30%的座位干擾對總登機(jī)過程沒有影響，故用干擾時(shí)間代替登機(jī)時(shí)間缺乏一定準(zhǔn)確性.為完善登機(jī)時(shí)間模型，針對行李的影響探尋最優(yōu)策略，本文提出干擾時(shí)間閾值的概念，運(yùn)用數(shù)學(xué)模型和優(yōu)化算法使所有旅客的過道干擾時(shí)間小于其對應(yīng)的干擾時(shí)間閾值，并根據(jù)旅客攜帶行李數(shù)量不同，求解基于Steffen的動態(tài)登機(jī)策略.

1 模型構(gòu)建

為便于問題討論，登機(jī)問題的基本假設(shè)包括：以單通道客機(jī)經(jīng)濟(jì)艙為研究對象，機(jī)艙內(nèi)20排，每側(cè)3 個(gè)座位；旅客按照一定μs 的放行間隔和步速登機(jī)(其中μs 為時(shí)間步長單位)；過道只允許一名旅客同時(shí)通過；旅客到達(dá)指定座位所在過道放置行李；行李放置完成后進(jìn)入座位，其座位元胞被占用，過道元胞變?yōu)榭臻e.

1.1 登機(jī)模型

為研究旅客過道干擾對登機(jī)時(shí)間的影響，將登機(jī)過程分為兩個(gè)階段，如圖1所示.第1 階段為旅客開始進(jìn)入機(jī)艙時(shí)刻T0到預(yù)計(jì)最后一名入座旅客m進(jìn)入機(jī)艙時(shí)刻Te_board結(jié)束.在這個(gè)階段旅客陸續(xù)進(jìn)入機(jī)艙，只有當(dāng)機(jī)艙入口被占用時(shí)，后續(xù)旅客才會停止進(jìn)入機(jī)艙，延長登機(jī)時(shí)間，這里將機(jī)艙入口占用時(shí)間稱為入口延時(shí)td_door.

第2 階段為預(yù)計(jì)最后一名入座旅客m進(jìn)入機(jī)艙時(shí)刻Te_board開始到實(shí)際最后一名旅客入座的時(shí)刻Ta_board結(jié)束，在這個(gè)階段尚未入座的旅客因?yàn)榇嬖谶^道干擾，延長登機(jī)時(shí)間的部分稱為入座延時(shí)td_seat.

圖1 登機(jī)時(shí)間組成示意圖Fig.1 Boarding time composition diagram

旅客登機(jī)時(shí)間可以分為無干擾登機(jī)時(shí)間、入口延時(shí)和入座延時(shí)3個(gè)部分，滿足關(guān)系式

式中：tboarding為登機(jī)時(shí)間，即從第1名旅客進(jìn)入機(jī)艙到全部旅客進(jìn)入座位的時(shí)間；tuninterference為無干擾登機(jī)時(shí)間，指在沒有任何干擾的情況下所有旅客全部入座的時(shí)間；td_door為入口延時(shí)；td_seat為入座延時(shí).

考慮登機(jī)過程中延時(shí)問題的新登機(jī)模型相比前人模型更加直觀便于理解，以下提出干擾閾值概念作為優(yōu)化算法的基礎(chǔ).

1.2 入口延時(shí)

在第1階段，機(jī)艙入口被占用是由于機(jī)艙內(nèi)旅客的過道干擾時(shí)間超過干擾時(shí)間閾值，使后續(xù)旅客在機(jī)艙內(nèi)擁堵到入口所致，因此入口延時(shí)滿足關(guān)系式

式中：i為第1 階段旅客；x表示座位的列；y表示座位的行；tinterference(i)為旅客i的過道干擾時(shí)間；Δt1(x,y,i)為第1階段干擾時(shí)間閾值，該閾值只受到后續(xù)旅客到達(dá)r行的時(shí)刻Tr影響，即

如圖2所示，以Steffen策略為例，旅客A4因?yàn)檎加眠^道時(shí)間超過其時(shí)間閾值，造成機(jī)艙入口被占用，產(chǎn)生入口延時(shí)，干擾后續(xù)旅客進(jìn)入機(jī)艙，延長了登機(jī)時(shí)間，而旅客A10 占用過道時(shí)間小于其時(shí)間閾值，不會延長登機(jī)時(shí)間.

圖2 入口延時(shí)示意圖Fig.2 Door delay diagram

1.3 入座延時(shí)

在第2 階段尚未入座的旅客j的實(shí)際入座時(shí)刻Ta(j)超過預(yù)計(jì)最后一名入座旅客m入座時(shí)刻Te_board+te_board(m)時(shí)，將會延長無干擾登機(jī)時(shí)間tuninterference，產(chǎn)生入座延時(shí)td_seat，即

式中：j為第2 階段未入座旅客；n為旅客數(shù)量；te_board(m)為預(yù)計(jì)最后一名旅客進(jìn)入機(jī)艙到入座的預(yù)計(jì)時(shí)間；Ta(j)為旅客j的入座時(shí)刻，滿足

式中：Tb(j)為旅客j進(jìn)入機(jī)艙時(shí)刻；tinterference(j)為旅客j的過道干擾時(shí)間；te_board(j)為旅客j進(jìn)入機(jī)艙到入座的預(yù)計(jì)時(shí)間.

將式(5)帶入式(4)，得到tinterference(j)和td_seat的關(guān)系，即

式中：Δt2(x,y,j)稱為第2 階段干擾時(shí)間閾值，且te_board屬于無干擾登機(jī)時(shí)間的一部分，即

如圖3所示，仍以Steffen 策略為例，旅客D19為預(yù)計(jì)最后一名入座旅客，旅客D19進(jìn)入座位后，旅客D17、D15、D5仍占用過道，延長登機(jī)時(shí)間.

圖3 入座延時(shí)示意圖Fig.3 Seat delay diagram

圖4展示了干擾時(shí)間與登機(jī)時(shí)間的關(guān)系.第1階段的入口延時(shí)td_door和第2 階段的入座延時(shí)td_seat組成登機(jī)延時(shí).而第1 階段和第2 階段tinterference≤Δt(x,y)的旅客，雖然占用過道，但不延長無干擾登機(jī)時(shí)間，Δt(x,y)為第1階段和第2階段干擾時(shí)間閾值總稱.

圖4 干擾時(shí)間與登機(jī)時(shí)間關(guān)系示意圖Fig.4 Diagram of relationship between interference time and boarding time

2 動態(tài)登機(jī)策略

Steffen 利用馬爾可夫—蒙特卡洛優(yōu)化算法提出Steffen 登機(jī)策略[4]，該策略完全避免了座位干擾，并且提高不同旅客在過道中處理行李的并行性，極大程度上減少了過道干擾.另外，通過真人登機(jī)實(shí)驗(yàn)可知，當(dāng)旅客不攜帶行李時(shí)，按照Steffen次序登機(jī)能夠完全避免座位干擾和過道干擾.因此，本節(jié)將基于Steffen登機(jī)策略，統(tǒng)計(jì)每個(gè)座位的干擾時(shí)間閾值；在此基礎(chǔ)上研究行李分配的優(yōu)化算法，指派每個(gè)座位行李的數(shù)量使過道干擾時(shí)間盡可能小于干擾時(shí)間閾值，使登機(jī)時(shí)間最小.

2.1 登機(jī)時(shí)間優(yōu)化

建立新登機(jī)模型的目標(biāo)是登機(jī)時(shí)間最小化，根據(jù)式(4)，優(yōu)化模型為

其中，無干擾登機(jī)時(shí)間在旅客數(shù)量、登機(jī)順序和機(jī)艙結(jié)構(gòu)固定的情況下，為常數(shù)項(xiàng).因此優(yōu)化模型變?yōu)?/p>

式(9)對過道干擾時(shí)間tinterference求導(dǎo)，得到

根據(jù)式(2)和式(6)，當(dāng)過道干擾時(shí)間小于干擾時(shí)間閾值時(shí)，登機(jī)時(shí)間達(dá)到最小，即無干擾登機(jī)時(shí)間為

2.2 干擾時(shí)間閾值

在Steffen登機(jī)策略中，由前文分析可知，旅客D19 預(yù)計(jì)最后一個(gè)入座.旅客A20 到旅客C1 這前110 名旅客屬于登機(jī)第1 階段，在不造成入口占用的情況下，根據(jù)式(3)統(tǒng)計(jì)出第1 階段干擾時(shí)間閾值Δt1(x,y,i).旅客D19到旅客D1后10名旅客屬于登機(jī)第2階段，根據(jù)式(7)統(tǒng)計(jì)得到第2階段干擾時(shí)間閾值Δt2(x,y,j).通過仿真模型統(tǒng)計(jì)出Steffen 策略時(shí)120 個(gè)座位的干擾時(shí)間閾值分布，如圖5所示，其中每一個(gè)座位上的數(shù)字為Δt(x,y)的值.仿真模型的參數(shù)設(shè)置為：放行間隔為1 μs ，x=A,B,…,F,y=1,2,…,20.

2.3 優(yōu)化算法

在干擾時(shí)間閾值分布的基礎(chǔ)上，通過優(yōu)化算法分配行李，使得過道干擾時(shí)間與干擾閾值之間的差值最小，最大程度地減少放置行李對登機(jī)時(shí)間的影響.優(yōu)化算法的具體步驟如下：

Step 1按照多件行李優(yōu)先的原則，將行李從多到少排列，并設(shè)置行李架上的初始行李數(shù)量nbin(x,y)=0,x=A,B,…,F,y=1,2,…,20.

Step 2參考機(jī)艙干擾時(shí)間閾值分布，遍歷尋找min[tinterference(x,y,i)-Δt(x,y,i)]的位置，確定攜帶行李旅客所在的座位.

Step 3重復(fù)Step 2，依次確定所有行李的位置.

Step 4確定120 個(gè)座位上的行李數(shù)量，為證明在不同的行李數(shù)量分布下優(yōu)化算法得到的結(jié)果都為最優(yōu)策略，選取0，1，2件行李數(shù)量比例分別為43∶52∶25和12∶72∶36兩種行李數(shù)量分布，由優(yōu)化算法分別得到行李分配的優(yōu)化算法結(jié)果，如圖6所示，圖中每個(gè)座位上的數(shù)字為該位置擺放行李的件數(shù).

圖5 Steffen 策略干擾時(shí)間閾值分布Fig.5 Interference time threshold distribution of Steffen strategy

圖6 Steffen 策略行李分配優(yōu)化結(jié)果Fig.6 Baggage allocation optimization results of Steffen strategy

所提出的動態(tài)登機(jī)策略實(shí)質(zhì)上是從兩個(gè)方面組織登機(jī)過程：一方面，根據(jù)旅客攜帶行李數(shù)量進(jìn)行座位分配，如圖6所示，攜帶不同數(shù)量行李的旅客被分配到不同的座位，使得每個(gè)座位上放置行李時(shí)間盡可能低于時(shí)間閾值；另一方面，在登機(jī)次序上按照Steffen 的序列登機(jī)，能夠在登機(jī)過程中減少干擾.根據(jù)實(shí)際情況中，旅客攜帶行李數(shù)量的不同，優(yōu)化算法會求解出不同的行李分配結(jié)果，故該策略是動態(tài)變化的.

3 實(shí)驗(yàn)與結(jié)果分析

為驗(yàn)證新登機(jī)模型的正確性和動態(tài)登機(jī)策略的效率，使用元胞自動機(jī)仿真實(shí)驗(yàn)和真人現(xiàn)場模擬實(shí)驗(yàn)兩種方法進(jìn)行驗(yàn)證.元胞自動機(jī)仿真實(shí)驗(yàn)以經(jīng)典單通道機(jī)艙為例，設(shè)計(jì)為20行6列，放行間隔為1 μs，仿真通過Matlab2012B編程實(shí)現(xiàn).

3.1 仿真實(shí)驗(yàn)結(jié)果分析

通過設(shè)置不同的行李比例，仿真運(yùn)行BF_3、BF_4、Random、OI、RP_4 和Steffen 這6 種登機(jī)策略，統(tǒng)計(jì)4 種行李情況下新登機(jī)模型的時(shí)間組成：登機(jī)時(shí)間tboarding、無干擾登機(jī)時(shí)間tuninterference、入口延時(shí)td_door、入座延時(shí)td_seat，統(tǒng)計(jì)結(jié)果如圖7所示.

圖7 登機(jī)模型的時(shí)間組成Fig.7 Time composition of boarding model

從圖7中可得到以下結(jié)論，登機(jī)時(shí)間的3個(gè)組成部分無干擾登機(jī)時(shí)間、入口延時(shí)、入座延時(shí)與登機(jī)時(shí)間的關(guān)系滿足登機(jī)模型，即式(1).由圖7(a)可知，當(dāng)旅客不攜帶行李時(shí)，BF_3、BF_4、Random 這3種策略登機(jī)過程中不存在行李干擾時(shí)間，但仍存在座位干擾，且座位干擾會產(chǎn)生入口延時(shí)和入座延時(shí)，導(dǎo)致登機(jī)時(shí)間比無干擾登機(jī)時(shí)間長.而OI、RP_4 和Steffen 這3 種策略避免了座位干擾，因此登機(jī)時(shí)間和無干擾登機(jī)時(shí)間一致；由圖7可知，隨著旅客攜帶行李的增多，機(jī)艙內(nèi)旅客的過道干擾時(shí)間增加，產(chǎn)生入口延時(shí)和入座延時(shí)，使得登機(jī)時(shí)間都有所增加；對比不同行李比例下的6種策略可知，Steffen策略表現(xiàn)得更高效、更穩(wěn)健.

為使本文的優(yōu)化算法與前人的研究具有可比性，將優(yōu)化算法與經(jīng)典Steffen 策略和基于Steffen的兩種改進(jìn)策略[6]在同一個(gè)元胞自動機(jī)仿真環(huán)境中進(jìn)行實(shí)驗(yàn)對比.選取文獻(xiàn)中一種行李比例，即0，1，2件所占比例為43∶52∶25，得到4種策略的登機(jī)時(shí)間構(gòu)成情況如圖8所示.仿真結(jié)果顯示：經(jīng)典Steffen策略的登機(jī)時(shí)間為185 μs，登機(jī)次序使旅客在機(jī)艙內(nèi)避免了座位干擾，但放置攜帶行李會產(chǎn)生入口延時(shí)和入座延時(shí)；基于Steffen的兩種改進(jìn)策略通過分配行李再登機(jī)，登機(jī)時(shí)間分別為159 μs 和176 μs，相對于經(jīng)典Steffen減少了登機(jī)時(shí)間，這兩種策略雖然將入口延時(shí)和入座延時(shí)時(shí)間縮短，但仍存在延時(shí)；本文通過優(yōu)化算法分配行李將行李放置時(shí)間控制在干擾時(shí)間閾值以內(nèi)，有效地避免了入口延時(shí)和入座延時(shí)，使登機(jī)時(shí)間縮短為129 μs，使得登機(jī)時(shí)間與無干擾登機(jī)時(shí)間一致；本文的優(yōu)化結(jié)果相比于經(jīng)典Steffen，效率提高30.27%；相比于文獻(xiàn)[6]和文獻(xiàn)[7]的優(yōu)化進(jìn)一步優(yōu)化了18.87%和9.66%.

圖8 優(yōu)化算法驗(yàn)證Fig.8 Optimization algorithm verification

改變旅客攜帶行李數(shù)量為0，1，2 件比例為12∶72∶36 時(shí)，本文的動態(tài)策略用時(shí)154 μs ，Milne 2016年的改進(jìn)策略用時(shí)194 μs.結(jié)果表明，當(dāng)行李數(shù)量增加時(shí)，動態(tài)策略的行李分配發(fā)生變化，并且相比2016年的改進(jìn)策略效率提高了20.62%.可見動態(tài)登機(jī)策略具有比之前的策略進(jìn)一步優(yōu)化了時(shí)間且具有一定的穩(wěn)定性.

3.2 現(xiàn)場模擬實(shí)驗(yàn)結(jié)果分析

本文選取Random、BF、OI、RP、Steffen 和動態(tài)登機(jī)策略6種策略，組織144名參與者在48座飛機(jī)模擬艙中進(jìn)行了3～4 次登機(jī)實(shí)驗(yàn).首先，選擇Steffen策略和本文的動態(tài)登機(jī)策略來驗(yàn)證新登機(jī)模型；其次，將它們與Random策略進(jìn)行比較，以評估動態(tài)策略的性能.

根據(jù)前文圖3對登機(jī)階段的分析，當(dāng)?shù)菣C(jī)總?cè)藬?shù)為48 時(shí)，乘客D7 為預(yù)計(jì)最后一名乘客，作為兩階段的分界點(diǎn).與不攜帶行李時(shí)的Steffen相比，通過觀察實(shí)驗(yàn)視頻，可以獲得入口延時(shí)和入座延時(shí)，如表2所示.當(dāng)旅客不攜帶行李并運(yùn)用Steffen次序登機(jī)時(shí)沒有產(chǎn)生座位或過道干擾，故其登機(jī)時(shí)間被視為無干擾登機(jī)時(shí)間，即136 s.新登機(jī)模型的無干擾登機(jī)時(shí)間、入口延時(shí)、入座延時(shí)3 個(gè)組成部分的總和是173 s和149 s，而仿真模擬實(shí)驗(yàn)的登機(jī)時(shí)間是183 s 和152 s，偏差為5.50%和2%.由于實(shí)驗(yàn)視頻觀測中的最小單位是秒，并且統(tǒng)計(jì)中存在一定的主觀誤差，故可以認(rèn)為新登機(jī)模型是準(zhǔn)確的.

表1 登機(jī)模型驗(yàn)證Table1 Boarding model verification (s)

登機(jī)時(shí)間是評估登機(jī)效率的重要指標(biāo)，真人模擬實(shí)驗(yàn)得到Random、BF、OI、RP、Steffen 和動態(tài)策略6 種策略的登機(jī)時(shí)間分別為：269，279，206，191，183，152 s.可以看出，登機(jī)動態(tài)策略的登機(jī)時(shí)間最短，相比于傳統(tǒng)Random 和BF 策略登機(jī)效率提高了43%和46%.另一方面，通過組織模擬實(shí)驗(yàn)也表明，動態(tài)策略在實(shí)際登機(jī)中具有可行性和可操作性.

4 結(jié) 論

針對以往登機(jī)時(shí)間模型用干擾時(shí)間代替登機(jī)時(shí)間存在的重復(fù)統(tǒng)計(jì)或遺漏的情況，本文將登機(jī)過程分成兩個(gè)階段，建立了新登機(jī)模型，在干擾時(shí)間閾值的基礎(chǔ)上運(yùn)用優(yōu)化算法求解出行李分配結(jié)果，并得到登機(jī)動態(tài)策略.主要結(jié)論如下：元胞自動機(jī)仿真實(shí)驗(yàn)驗(yàn)證了新登機(jī)模型的正確性；仿真結(jié)果表明：當(dāng)行李比例，即0，1，2 件所占比例為43∶52∶25時(shí)，動態(tài)登機(jī)策略相比于經(jīng)典Steffen策略，登機(jī)時(shí)間效率提高30.27%；當(dāng)行李數(shù)量增加，即0，1，2 件所占比例為12∶72∶36 時(shí)登機(jī)時(shí)間效率提高20.62%；組織現(xiàn)場模擬實(shí)驗(yàn)結(jié)果表明動態(tài)策略在實(shí)際中具有可行性，并且相比于Random和BF效率提高43%和46%.

由于動態(tài)登機(jī)策略在實(shí)施過程中需要在登機(jī)前知道旅客攜帶行李件數(shù)，因此，未來可在值機(jī)或安檢系統(tǒng)中加入收集旅客攜帶行李的步驟，不僅有利于提高登機(jī)效率，而且便于旅客行李管理.無論是手機(jī)值機(jī)、自助值機(jī)，在相應(yīng)值機(jī)系統(tǒng)中增加填報(bào)行李數(shù)量的選項(xiàng)；這樣登機(jī)系統(tǒng)就可以根據(jù)旅客填報(bào)行李數(shù)量進(jìn)行座位的分配.如果旅客要進(jìn)行自主選座，可根據(jù)行李分配的結(jié)果對座位進(jìn)行鎖定，旅客只能選擇符合行李數(shù)量的座位.目前實(shí)施的“付費(fèi)選座”“會員選擇”等，航空公司可結(jié)合已分配行李數(shù)量的座位綜合考慮，即滿足登機(jī)效率的要求，又滿足旅客服務(wù)、效益的需求.這個(gè)問題還有待進(jìn)一步深入研究，尋求效率、效益的最佳結(jié)合點(diǎn).本文提出的干擾閾值概念可以運(yùn)用到按照預(yù)先指定的次序進(jìn)行登機(jī)/入座/進(jìn)場等其他領(lǐng)域.旅客行走速度、放行間隔和攜帶行李的多少都會影響旅客入座時(shí)間，因此，如何將兩個(gè)階段更明顯地劃分，以及如何確定最后一名入座旅客都將是進(jìn)一步研究的內(nèi)容.