基于多目標算法的航站樓值機系統動態配置研究

張天炫，包丹文，朱 婷，羊 釗，田詩佳

（南京航空航天大學民航學院，江蘇 南京211100）

專家學者對航站樓值機及安檢設施動態配置進行了各類研究[1-5]，基于服務標準[6-9]，以設施使用成本與旅客時間成本總成本之和最小化為目標對設施資源進行優化[10-11]，改善旅客滿意度。 同時，構建適合航站樓空間特點的排隊模型[12-16]，有利于確定值機及安檢設施具體數量。由決策支持系統[17]、網絡模型[18]開發的模型能有效反應設施系統內在運行機制，從而進行資源配置。

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

在航站樓值機設施動態配置方面，基于多目標算法構造配置模型并運用后驗評價方法選擇最優方案的研究幾乎沒有。本文基于多目標算法，分別站在航空公司及旅客角度構建航站樓值機系統動態配置模型，采用NSGA-Ⅱ多目標遺傳算法、TOPSIS 方法進行求解，確定最佳配置方案。

1 系統模型與問題描述

1.1 問題描述

如何構建航站樓值機系統動態配置模型，選擇綜合效益最好的柜臺配置方案成為提高機場和航空公司運營水平的關鍵。本文從柜臺運營成本和旅客值機排隊等待時間兩方面建立優化目標，考慮柜臺數約束、排隊及服務辦理時間運行標準約束和繁忙概率約束三約束條件，提出航站樓值機柜臺配置方案。

1.2 目標函數

1） 航空公司值機柜臺運營成本目標。 值機柜臺運營成本反映了柜臺配置對航空公司經濟發展規劃的影響情況，是衡量航空公司收益的重要指導目標，由柜臺租用成本和地服人員工作費用兩部分組成。 在對值機柜臺進行優化配置時，航空公司管理部門盡可能要求運營成本達到最小，具體如式（1）所示

式中：Z1為航空公司值機柜臺運營成本，元/min；Cs為航空公司值機柜臺租用成本，元/（個/min）；Cp為航空公司值機地服人員工作費用，元/（人/min）；c 為值機柜臺開放數量。

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

式中：Z2為旅客值機排隊等待時間，min；Lq為值機柜臺排隊長度；λ 為值機柜臺旅客到達率， 人/min；ρ 為值機柜臺總服務強度；P0為值機柜臺空閑概率；μ 為單個值機柜臺服務率，人/min。

1.3 約束條件

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

式中：C 為值機系統柜臺總數。

2） 柜臺旅客乘機手續排隊及辦理時間運行標準約束。在值機系統的實際生產過程中，為了保證值機旅客的高服務滿意度，需要將值機服務水平控制在機場運行標準服務水平之上，即95%的國內經濟艙旅客乘機手續排隊及辦理時間應不超過10 min，如式（7）所示

2 算法設計

2.1 NSGA-Ⅱ在航站樓值機系統動態配置問題中的實現

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

航站樓值機系統動態配置為多目標、非線性，有眾多約束條件的復雜規劃問題，NSGA-Ⅱ在求解動態配置模型中的實現步驟如圖1 所示。

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

2.2 TOPSIS 方法

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

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

2） TOPSIS 后驗評價實現步驟。 ①根據Pareto 最優柜臺配置解構建初始化判斷矩陣；②對初始化判斷矩陣進行歸一化處理； ③根據DELPHI 法得到柜臺運營成本及旅客值機排隊等待時間的信息權重矩陣，并形成加權判斷矩陣；④根據加權判斷矩陣獲得兩目標的正負理想解；⑤計算各評價目標值與理想值之間的距離及相對貼近度；⑥根據相對貼近度對各評價目標進行排序，得到最終決策結果。

3 實例分析

3.1 數據獲取及分析

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

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

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

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

運用SPSS 軟件對高峰時段D 島值機柜臺單窗口值機服務時間進行K-S 非參數指數分布檢驗，檢驗結果如表1 所示。

圖3 D 島值機柜臺單窗口值機服務時間Fig.3 Single-window service time at the D Island check-in counter

表1 單窗口值機服務時間Kolmogorov-Smirnov 指數分布檢驗結果Tab.1 Kolmogorov-Smirnov exponential distribution test results of single-window service time

3.2 NSGA-Ⅱ仿真測試參數設置

仿真測試選取6:00 航站樓D 島20 個值機柜臺相關數據，表2 給出了動態配置問題原始數據。

表2 值機系統動態配置問題原始數據Tab.2 Raw data of check-in system dynamic configuration issues

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

表3 NSGA-Ⅱ算法參數Tab.3 NSGA-Ⅱalgorithm parameters

3.3 仿真測試結果

由于優化目標為航空公司柜臺運營成本和旅客值機排隊等待時間，且變量為整數，Pareto 最優解集為二維空間中相互孤立的點， 趨勢線為一曲線。 基于航站樓值機系統動態配置模型運行NSGA-Ⅱ算法求解Pareto 最優解，如表4 所示。

表4 6:00 航站樓值機系統動態配置問題Pareto 最優解Tab.4 Pareto-optimal set for dynamic configuration problem of terminal check-in system at 6:00

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

3.4 Pareto 最優解后驗評價

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

1） 評價指標同趨勢化。 在進行評價時，應使所有指標變化方向一致，通常將低優指標和中性指標全轉化為高優指標。 因此將模型優化目標這兩低優指標通過倒數法轉化為高優指標，同趨勢化的初始判斷矩陣值如表5 所示。

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

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

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

3） 獲取最優及最劣配置方案。

4） 計算各方案目標值與理想值之間的距離。 根據DELPH 法得到專家對航空公司柜臺運營成本及旅客值機排隊等待時間兩目標值的權重矩陣，分別計算各方案兩目標值與最優方案和最劣方案的距離，計算結果如表7 所示。

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

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

排序結果表明，值機系統開放18 個柜臺時綜合效益最好。

3.5 配置方案對比分析

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

圖4 6:00 不同配置方案優化目標差值分析圖Fig.4 Difference between optimization goals of different configuration plans at 6:00

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

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

3.6 D 島值機系統動態配置結果

最終，2019 年夏秋航季D 島值機系統全天5:00-22:00 每半小時綜合效益最優柜臺動態開放數量如圖5 所示，其分布情況與值機旅客到達率相符合。 6:30 時柜臺開放數量最多，為19 個；5:00 和22:00 時柜臺開放數量最少，為1 個。

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

4 結論

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