基于時間閾值的旅客登機模型及動態(tài)登機策略

任新惠，焦 陽，徐小冰

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

0 引 言

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

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

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

1 模型構建

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

1.1 登機模型

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

第2 階段為預計最后一名入座旅客m進入機艙時刻Te_board開始到實際最后一名旅客入座的時刻Ta_board結束，在這個階段尚未入座的旅客因為存在過道干擾，延長登機時間的部分稱為入座延時td_seat.

圖1 登機時間組成示意圖Fig.1 Boarding time composition diagram

旅客登機時間可以分為無干擾登機時間、入口延時和入座延時3個部分，滿足關系式

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

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

1.2 入口延時

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

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

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

圖2 入口延時示意圖Fig.2 Door delay diagram

1.3 入座延時

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

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

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

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

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

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

圖3 入座延時示意圖Fig.3 Seat delay diagram

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

圖4 干擾時間與登機時間關系示意圖Fig.4 Diagram of relationship between interference time and boarding time

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

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

2.1 登機時間優(yōu)化

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

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

式(9)對過道干擾時間tinterference求導，得到

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

2.2 干擾時間閾值

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

2.3 優(yōu)化算法

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

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

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

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

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

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

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

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

3 實驗與結果分析

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

3.1 仿真實驗結果分析

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

圖7 登機模型的時間組成Fig.7 Time composition of boarding model

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

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

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

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

3.2 現(xiàn)場模擬實驗結果分析

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

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

表1 登機模型驗證Table1 Boarding model verification (s)

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

4 結 論

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

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