基于多目標(biāo)算法的航站樓值機(jī)系統(tǒng)動態(tài)配置研究

張?zhí)祆牛の模?婷，羊 釗，田詩佳

（南京航空航天大學(xué)民航學(xué)院，江蘇 南京211100）

專家學(xué)者對航站樓值機(jī)及安檢設(shè)施動態(tài)配置進(jìn)行了各類研究[1-5]，基于服務(wù)標(biāo)準(zhǔn)[6-9]，以設(shè)施使用成本與旅客時(shí)間成本總成本之和最小化為目標(biāo)對設(shè)施資源進(jìn)行優(yōu)化[10-11]，改善旅客滿意度。 同時(shí)，構(gòu)建適合航站樓空間特點(diǎn)的排隊(duì)模型[12-16]，有利于確定值機(jī)及安檢設(shè)施具體數(shù)量。由決策支持系統(tǒng)[17]、網(wǎng)絡(luò)模型[18]開發(fā)的模型能有效反應(yīng)設(shè)施系統(tǒng)內(nèi)在運(yùn)行機(jī)制，從而進(jìn)行資源配置。

多目標(biāo)優(yōu)化[19]能對不同成本目標(biāo)進(jìn)行針對性研究，展現(xiàn)優(yōu)化目標(biāo)間的博弈關(guān)系，消除目標(biāo)量綱不同引起的優(yōu)化結(jié)果低置信度現(xiàn)象。 NSGA-Ⅱ算法[20]是目前解決多目標(biāo)優(yōu)化問題的常用算法之一，通過NSGA-Ⅱ算法可得到問題的Pareto 最優(yōu)解集。同時(shí)，由于多目標(biāo)優(yōu)化問題的解不是唯一的，基于TOPSIS 法[21]可以從有限的Pareto 解集中選擇合適解進(jìn)行多目標(biāo)資源優(yōu)化決策。

在航站樓值機(jī)設(shè)施動態(tài)配置方面，基于多目標(biāo)算法構(gòu)造配置模型并運(yùn)用后驗(yàn)評價(jià)方法選擇最優(yōu)方案的研究幾乎沒有。本文基于多目標(biāo)算法，分別站在航空公司及旅客角度構(gòu)建航站樓值機(jī)系統(tǒng)動態(tài)配置模型，采用NSGA-Ⅱ多目標(biāo)遺傳算法、TOPSIS 方法進(jìn)行求解，確定最佳配置方案。

1 系統(tǒng)模型與問題描述

1.1 問題描述

如何構(gòu)建航站樓值機(jī)系統(tǒng)動態(tài)配置模型，選擇綜合效益最好的柜臺配置方案成為提高機(jī)場和航空公司運(yùn)營水平的關(guān)鍵。本文從柜臺運(yùn)營成本和旅客值機(jī)排隊(duì)等待時(shí)間兩方面建立優(yōu)化目標(biāo)，考慮柜臺數(shù)約束、排隊(duì)及服務(wù)辦理時(shí)間運(yùn)行標(biāo)準(zhǔn)約束和繁忙概率約束三約束條件，提出航站樓值機(jī)柜臺配置方案。

1.2 目標(biāo)函數(shù)

1） 航空公司值機(jī)柜臺運(yùn)營成本目標(biāo)。 值機(jī)柜臺運(yùn)營成本反映了柜臺配置對航空公司經(jīng)濟(jì)發(fā)展規(guī)劃的影響情況，是衡量航空公司收益的重要指導(dǎo)目標(biāo)，由柜臺租用成本和地服人員工作費(fèi)用兩部分組成。 在對值機(jī)柜臺進(jìn)行優(yōu)化配置時(shí)，航空公司管理部門盡可能要求運(yùn)營成本達(dá)到最小，具體如式（1）所示

式中：Z1為航空公司值機(jī)柜臺運(yùn)營成本，元/min；Cs為航空公司值機(jī)柜臺租用成本，元/（個(gè)/min）；Cp為航空公司值機(jī)地服人員工作費(fèi)用，元/（人/min）；c 為值機(jī)柜臺開放數(shù)量。

2） 旅客值機(jī)排隊(duì)等待時(shí)間目標(biāo)。 在值機(jī)系統(tǒng)總資源定量的情況下，合理高效地利用柜臺資源對保證航站樓值機(jī)區(qū)域秩序、提高旅客滿意度具有重要意義。 因此在對值機(jī)柜臺進(jìn)行優(yōu)化配置時(shí)，機(jī)場管理部門要保證旅客值機(jī)排隊(duì)等待時(shí)間盡可能小，具體如式（2）所示。 同時(shí)由于大多數(shù)大型航站樓值機(jī)區(qū)域排隊(duì)系統(tǒng)為多通道服務(wù)系統(tǒng)，根據(jù)排隊(duì)論M/M/C 模型可得到值機(jī)柜臺總服務(wù)強(qiáng)度、空閑概率以及排隊(duì)長度如式（3）～式（5）所示

式中：Z2為旅客值機(jī)排隊(duì)等待時(shí)間，min；Lq為值機(jī)柜臺排隊(duì)長度；λ 為值機(jī)柜臺旅客到達(dá)率， 人/min；ρ 為值機(jī)柜臺總服務(wù)強(qiáng)度；P0為值機(jī)柜臺空閑概率；μ 為單個(gè)值機(jī)柜臺服務(wù)率，人/min。

1.3 約束條件

1） 柜臺數(shù)約束。 在實(shí)際配置工作中由于資源限制所開放的值機(jī)柜臺數(shù)不能超過系統(tǒng)已有最大資源，式（6）表明了值機(jī)柜臺總體資源條件限制

式中：C 為值機(jī)系統(tǒng)柜臺總數(shù)。

2） 柜臺旅客乘機(jī)手續(xù)排隊(duì)及辦理時(shí)間運(yùn)行標(biāo)準(zhǔn)約束。在值機(jī)系統(tǒng)的實(shí)際生產(chǎn)過程中，為了保證值機(jī)旅客的高服務(wù)滿意度，需要將值機(jī)服務(wù)水平控制在機(jī)場運(yùn)行標(biāo)準(zhǔn)服務(wù)水平之上，即95%的國內(nèi)經(jīng)濟(jì)艙旅客乘機(jī)手續(xù)排隊(duì)及辦理時(shí)間應(yīng)不超過10 min，如式（7）所示

2 算法設(shè)計(jì)

2.1 NSGA-Ⅱ在航站樓值機(jī)系統(tǒng)動態(tài)配置問題中的實(shí)現(xiàn)

NSGA-Ⅱ算法源于遺傳算法，采用快速非支配排序算法和擁擠距離排序算子，使準(zhǔn)Pareto 域中的個(gè)體能擴(kuò)展到整個(gè)Pareto 域，并均勻分布，保持了種群的多樣性；同時(shí)引入精英策略，擴(kuò)大采樣空間，防止最佳個(gè)體的丟失，提高了算法的運(yùn)算速度和魯棒性。

航站樓值機(jī)系統(tǒng)動態(tài)配置為多目標(biāo)、非線性，有眾多約束條件的復(fù)雜規(guī)劃問題，NSGA-Ⅱ在求解動態(tài)配置模型中的實(shí)現(xiàn)步驟如圖1 所示。

圖1 NSGA-Ⅱ算法流程圖Fig.1 NSGA-Ⅱalgorithm flowchart

2.2 TOPSIS 方法

通過NSGA-Ⅱ算法得到了航站樓值機(jī)系統(tǒng)動態(tài)配置問題的Pareto 最優(yōu)解集， 但通常需要選擇綜合效益最好的方案來進(jìn)行具體配置，于決策者而言，從所有Pareto 最優(yōu)解中選擇一個(gè)方案稱為后驗(yàn)評價(jià)。 本文在TOPSIS 方法的基礎(chǔ)上，對Pareto 最優(yōu)解進(jìn)行排序，確定最終柜臺配置方案。

1） 方法概述。TOPSIS 方法是有限方案多目標(biāo)決策分析的常用方法，它可以計(jì)算出理想中的最佳方案和最差方案，同時(shí)求解各評價(jià)方案與最佳、最差方案之間的距離，得出該方案與最佳方案的接近程度，最后對評價(jià)方案進(jìn)行排序。

2） TOPSIS 后驗(yàn)評價(jià)實(shí)現(xiàn)步驟。 ①根據(jù)Pareto 最優(yōu)柜臺配置解構(gòu)建初始化判斷矩陣；②對初始化判斷矩陣進(jìn)行歸一化處理； ③根據(jù)DELPHI 法得到柜臺運(yùn)營成本及旅客值機(jī)排隊(duì)等待時(shí)間的信息權(quán)重矩陣，并形成加權(quán)判斷矩陣；④根據(jù)加權(quán)判斷矩陣獲得兩目標(biāo)的正負(fù)理想解；⑤計(jì)算各評價(jià)目標(biāo)值與理想值之間的距離及相對貼近度；⑥根據(jù)相對貼近度對各評價(jià)目標(biāo)進(jìn)行排序，得到最終決策結(jié)果。

3 實(shí)例分析

3.1 數(shù)據(jù)獲取及分析

本文選取南京祿口國際機(jī)場T2 航站樓D 島值機(jī)柜臺作為研究對象，對D 島值機(jī)旅客到達(dá)情況和值機(jī)柜臺服務(wù)能力進(jìn)行了分析。 研究數(shù)據(jù)來自對2019 年中國東方航空夏秋航季航班和值機(jī)區(qū)域高峰時(shí)段的調(diào)查，通過模型分析和錄制視頻的方式進(jìn)行數(shù)據(jù)獲取。

1） D 島值機(jī)柜臺旅客到達(dá)率。 根據(jù)2019 年中國東方航空夏秋航季航班離港時(shí)刻、航班座位數(shù)及航班擁擠度并假設(shè)柜臺值機(jī)比例為60%，通過離港時(shí)刻主導(dǎo)的單航班離港旅客聚集模型（TD-SFAPM 模型）可得到D 島值機(jī)柜臺全天5:00-22:20 每10 min 旅客到達(dá)率，且TD-SFAPM 模型使規(guī)定10 min 時(shí)段內(nèi)的旅客到達(dá)數(shù)服從相應(yīng)到達(dá)率的泊松分布，如圖2 所示。

圖2 2019 年夏秋航季D 島值機(jī)柜臺值機(jī)旅客到達(dá)率Fig.2 Passengers’ arrival rate at the D Island check-in counter during the summer and autumn season of 2019

2） D 島值機(jī)柜臺單窗口服務(wù)率。 通過視頻錄制隨機(jī)調(diào)查了值機(jī)區(qū)域2019 年7 月8 日、9 日兩天6:00-7：00 高峰時(shí)段100 名旅客在D 島值機(jī)柜臺的值機(jī)服務(wù)時(shí)間如圖3 所示。

運(yùn)用SPSS 軟件對高峰時(shí)段D 島值機(jī)柜臺單窗口值機(jī)服務(wù)時(shí)間進(jìn)行K-S 非參數(shù)指數(shù)分布檢驗(yàn)，檢驗(yàn)結(jié)果如表1 所示。

圖3 D 島值機(jī)柜臺單窗口值機(jī)服務(wù)時(shí)間Fig.3 Single-window service time at the D Island check-in counter

表1 單窗口值機(jī)服務(wù)時(shí)間Kolmogorov-Smirnov 指數(shù)分布檢驗(yàn)結(jié)果Tab.1 Kolmogorov-Smirnov exponential distribution test results of single-window service time

3.2 NSGA-Ⅱ仿真測試參數(shù)設(shè)置

仿真測試選取6:00 航站樓D 島20 個(gè)值機(jī)柜臺相關(guān)數(shù)據(jù)，表2 給出了動態(tài)配置問題原始數(shù)據(jù)。

表2 值機(jī)系統(tǒng)動態(tài)配置問題原始數(shù)據(jù)Tab.2 Raw data of check-in system dynamic configuration issues

其中，NSGA-Ⅱ算法采用Matlab 編程，參數(shù)設(shè)置如表3 所示。

表3 NSGA-Ⅱ算法參數(shù)Tab.3 NSGA-Ⅱalgorithm parameters

3.3 仿真測試結(jié)果

由于優(yōu)化目標(biāo)為航空公司柜臺運(yùn)營成本和旅客值機(jī)排隊(duì)等待時(shí)間，且變量為整數(shù)，Pareto 最優(yōu)解集為二維空間中相互孤立的點(diǎn)， 趨勢線為一曲線。 基于航站樓值機(jī)系統(tǒng)動態(tài)配置模型運(yùn)行NSGA-Ⅱ算法求解Pareto 最優(yōu)解，如表4 所示。

表4 6:00 航站樓值機(jī)系統(tǒng)動態(tài)配置問題Pareto 最優(yōu)解Tab.4 Pareto-optimal set for dynamic configuration problem of terminal check-in system at 6:00

航空公司柜臺運(yùn)營成本和旅客值機(jī)排隊(duì)等待時(shí)間兩個(gè)目標(biāo)均為越小越優(yōu)，在Pareto 前沿面上，非劣的值機(jī)柜臺配置方案的一個(gè)目標(biāo)值增大必然會引起另一個(gè)目標(biāo)的減小，從1 號方案至6 號方案，模型優(yōu)化結(jié)果從傾向于航空公司柜臺運(yùn)營成本最小逐步過渡到旅客值機(jī)排隊(duì)等待時(shí)間最小，成本從68.40 元/min 增至91.20 元/min，而等待時(shí)間從7.50 min 降至0.15 min，不存在某一方案使優(yōu)化的兩目標(biāo)值同時(shí)達(dá)到最小，兩目標(biāo)之間存在博弈。

3.4 Pareto 最優(yōu)解后驗(yàn)評價(jià)

NSGA-Ⅱ得到的6 組Pareto 最優(yōu)解能充分兼顧不同的值機(jī)系統(tǒng)配置方案， 采用基于TOPSIS 方法的決策過程可從6 組解中尋找綜合效益最優(yōu)的解。

1） 評價(jià)指標(biāo)同趨勢化。 在進(jìn)行評價(jià)時(shí)，應(yīng)使所有指標(biāo)變化方向一致，通常將低優(yōu)指標(biāo)和中性指標(biāo)全轉(zhuǎn)化為高優(yōu)指標(biāo)。 因此將模型優(yōu)化目標(biāo)這兩低優(yōu)指標(biāo)通過倒數(shù)法轉(zhuǎn)化為高優(yōu)指標(biāo)，同趨勢化的初始判斷矩陣值如表5 所示。

表5 同趨勢化的初始判斷矩陣值Tab.5 Co-trend and initial judgment matrix value

2） 初始判斷矩陣歸一化。 歸一化處理后的矩陣值如表6 所示。

表6 歸一化矩陣值Tab.6 Normalized matrix value

3） 獲取最優(yōu)及最劣配置方案。

4） 計(jì)算各方案目標(biāo)值與理想值之間的距離。 根據(jù)DELPH 法得到專家對航空公司柜臺運(yùn)營成本及旅客值機(jī)排隊(duì)等待時(shí)間兩目標(biāo)值的權(quán)重矩陣，分別計(jì)算各方案兩目標(biāo)值與最優(yōu)方案和最劣方案的距離，計(jì)算結(jié)果如表7 所示。

5） 選擇最終決策方案。 計(jì)算各方案與最優(yōu)方案的相對貼近度，并按相對貼近度對6 組方案進(jìn)行排序，選擇綜合效益最優(yōu)的方案作為配置問題最優(yōu)解，相對貼近度及排序結(jié)果如表7 所示。

表7 不同值機(jī)柜臺配置方案排序結(jié)果Tab.7 Sorting results of different check-in counter configuration plans

排序結(jié)果表明，值機(jī)系統(tǒng)開放18 個(gè)柜臺時(shí)綜合效益最好。

3.5 配置方案對比分析

1） 方案優(yōu)化目標(biāo)差值分析。 其中，不同值機(jī)柜臺配置方案與最優(yōu)方案兩優(yōu)化目標(biāo)之間的差值如圖5 所示。 可見，航空公司柜臺運(yùn)營成本與旅客值機(jī)排隊(duì)等待時(shí)間是兩完全相反的優(yōu)化目標(biāo)，運(yùn)用TOPSIS 方法不僅可以展現(xiàn)優(yōu)化目標(biāo)間的博弈關(guān)系，而且能充分反映了各配置方案之間的差距，提供更多決策支持信息，利于選擇航站樓值機(jī)系統(tǒng)動態(tài)配置問題最佳折衷配置方案。

圖4 6:00 不同配置方案優(yōu)化目標(biāo)差值分析圖Fig.4 Difference between optimization goals of different configuration plans at 6:00

2） 不同權(quán)重最優(yōu)方案分析。 由于不同機(jī)場及航空公司對旅客滿意度、航站樓運(yùn)行效率及航空公司運(yùn)營成本的決策需求存在差異， 運(yùn)用DELPHI 法得出的專家對成本及時(shí)間兩目標(biāo)值的權(quán)重矩陣有所不同。 表8顯示了不同權(quán)重矩陣下綜合效益最優(yōu)柜臺配置情況：隨著航空公司柜臺運(yùn)營成本權(quán)重的增加，值機(jī)柜臺開放數(shù)量和航空公司柜臺運(yùn)營成本逐漸減少，旅客值機(jī)排隊(duì)等待時(shí)間逐漸增加；當(dāng)成本權(quán)重增加至0.9 時(shí)，旅客值機(jī)排隊(duì)等待時(shí)間突增。 可見，Pareto 最優(yōu)解能充分兼顧不同的值機(jī)系統(tǒng)配置方案，滿足各類機(jī)場及航空公司的不同決策需求。

表8 不同權(quán)重矩陣下綜合效益最優(yōu)柜臺配置情況Tab.8 Configuration of counters with optimal comprehensive benefits under different weight matrices

3.6 D 島值機(jī)系統(tǒng)動態(tài)配置結(jié)果

最終，2019 年夏秋航季D 島值機(jī)系統(tǒng)全天5:00-22:00 每半小時(shí)綜合效益最優(yōu)柜臺動態(tài)開放數(shù)量如圖5 所示，其分布情況與值機(jī)旅客到達(dá)率相符合。 6:30 時(shí)柜臺開放數(shù)量最多，為19 個(gè)；5:00 和22:00 時(shí)柜臺開放數(shù)量最少，為1 個(gè)。

圖5 2019 年夏秋航季D 島值機(jī)柜臺動態(tài)開放數(shù)量Fig.5 Dynamic opening number of D-island check-in counters during the summer and autumn season of 2019

4 結(jié)論

本文采用多目標(biāo)算法，構(gòu)建航站樓值機(jī)系統(tǒng)動態(tài)配置模型，消除了航空公司柜臺運(yùn)營成本和旅客值機(jī)排隊(duì)等待時(shí)間量綱間的差異。在NSGA-II 算法中，充分考慮了柜臺數(shù)、排隊(duì)及服務(wù)辦理時(shí)間運(yùn)行標(biāo)準(zhǔn)和繁忙概率三方面約束條件，生成了Pareto 最優(yōu)解集，清晰地展示了成本與時(shí)間之間的博弈過程。 同時(shí)基于TOPSIS 方法的后驗(yàn)評價(jià)，對Pareto 最優(yōu)解進(jìn)行排序，確定了航站樓值機(jī)系統(tǒng)動態(tài)配置問題綜合效益最優(yōu)的配置方案。 利用航站樓值機(jī)系統(tǒng)動態(tài)配置模型能對比各時(shí)段可選值機(jī)柜臺配置方案與最優(yōu)方案的相對貼近度，找到最佳折衷配置方案，使運(yùn)營成本和旅客等待時(shí)間兩決策目標(biāo)同時(shí)達(dá)到最優(yōu)化的效果。