基于粒子群算法的航班座位自動分配系統

李方方 蔣理 戴勝 秦勝男

摘? ?要：航班座位的分配有一系列的規則，但由于物理座位限制，一般無法滿足所有旅客的個性化需求;一般自動分配座位通常采取“先到先得”的方式，但是這樣的方式只能解決前一部分旅客的座位要求。此外，由于航班變更，機械故障，航線計劃調整等原因，機型會發生變更，因此如何根據用戶已有的需求進行座位自動分配算法是個需要解決的問題。本文主要采用了改進的粒子群算法為已購票旅客自動分配航班座位，盡可能滿足旅客的個性化需求。

關鍵詞：自動分配? 粒子群? 航班座位

目前民航旅客在預定航班后，一般都可以提前自助選擇座位。如果不提前選擇座位，旅客到達機場后，在柜臺值機或自助設備上值機時，可以選擇一個座位，或者由后臺系統隨機分配一個座位。

航班座位的分配有一系列的規則，但由于物理座位限制，一般無法滿足所有旅客的個性化需求。由于大多航班都具備提前選座功能，想要預留好的座位要提前“下手”。而自動分配座位通常采取“先到先得”的方式，只能解決前一部分旅客的座位要求。

1? 旅客的不同的座位需求

飛機機艙內的座位本身具備多種屬性，包括：靠窗座位、靠過道座位、腿部寬敞座位、緊急出口座位、VIP旅客預留座位（一般是前排）等。不同旅客的座位需求是不同的。有人喜歡靠窗座位看風景;有人喜歡過道座位，方便去衛生間;VIP旅客一般分配前排座位;登機口邊上座位不會分配給殘疾人旅客，一般分配給男性，以便于突發事件時可以協助機組打開安全出口門;結伴同行的旅客盡可能分配在一起，在前后排或同一排;嬰兒旅客不占座位，但是攜帶嬰兒的旅客如果申請嬰兒搖籃可以分配到有嬰兒搖籃掛載點對應的位置，方便照看嬰兒。

本系統主要涉及到的座位屬性有很多，主要包括靠窗、中間、靠過道、安靜、平穩、安全感高、VIP、登機口、殘疾人、孕婦、嬰兒搖籃、飛機平衡、票價、年齡等。

2? 系統的設計與實現

航班座位自動分配系統整體是基于MVVM模式設計的，根據軟件開發中前后端模式的基本歷程，采用了前后端分離的基本結構。前端完全負責View層和ViewModel層。View是視圖層，也就是所謂的用戶界面;ViewModel是生成和維護的視圖數據層，是對后端獲取的Model數據完成數據轉換的功能;兩者完成封裝，來生成視圖數據模型。后端負責Model層，主要實現各種業務邏輯和數據庫操作。

3? 粒子群算法簡介及其改進

3.1 粒子群算法

本文主要采用粒子群算法實現航班座位的自動分配，在計算機科學中，粒子群優化（PSO）是一種計算方法，可以通過迭代來改進候選方案的優化問題。它通過粒子的位置和速度根據數學公式得到一組候選解決方案，并在搜索空間中移動這些粒子來解決問題。

3.2 粒子群算法的改進

由于PSO操作簡單、收斂速度快，因此在函數優化、 圖像處理、大地測量等眾多領域都得到了廣泛的應用。 隨著應用范圍的擴大，PSO算法存在早熟收斂、維數災難、易于陷入局部極值等問題需要解決，本文針對航班座位分配主要對粒子群算法進行了如下的改進：

3.2.1 參數選擇與優化

（1）參數w代表慣性部分，c1代表社會部分，c2代表自身部分 這三個部分決定了搜索的作用。慣性權重w主要是代表粒子上一代速度對當前代速度的影響。w較大，說明全局尋優能力越強，而局部尋優能力則越弱;所以為了在達到搜索速度和搜索精度之間平衡，要對w進行了改進。隨著迭代次數的增加，慣性權重w應不斷減少，從而使得粒子群算法在初期具有較強的全局收斂能力，而晚期具有較強的局部收斂能力。

（2）學習因子c1，c2都不為0，即為完全型粒子群算法，完全型粒子群算法更容易保持收斂速度和搜索效果的均衡，是較好的選擇。

（3） 群體大小m是一個整數，m很小時陷入局部最優解的可能性很大;m很大時PSO的優化能力很好，但是當群體數目增長至一定水平時，再增長將不再有顯著作用，而且數目越大計算量也越大。

（4）粒子群的最大速度Vmax對維護算法的探索能力與開發能力的平衡很重要，Vmax較大時，探索能力強，但粒子容易飛過最優解;Vmax較小時，開發能力強，但是容易陷入局部最優解。Vmax一般設為每維變量變化范圍10%～20%。

3.2.2 極值擾動的引入

粒子會出現“聚集”現象，當搜索到一定程度，算法就會處于進化停滯，粒子停留在一個較小的范圍內搜索，容易使算法陷入局部最優。因此，可以在公式中引入擾動因子r3和r4，對個體極值pbest和全局極值gbest進行隨機調整，從而擴大粒子的搜索范圍，幫助粒子跳出局部最優。

4? 座位自動分配過程

該系統實現單個旅客座位分配、一組旅客分配、整機旅客分配。根據分配結果展示單個旅客分配的位置，一組旅客的位置和整機旅客分配的位置;實現了算法分配過程的展示，計算出旅客的滿意度。實現了旅客信息的展示、編輯添加旅客的信息、添加多人的信息、查看所有旅客的信息;展示了旅客的年齡分布圖;展示了旅客的個人的屬性偏好和一組的旅客的關系偏好。根據隨機分配的算法與智能分配算法的對比展示出智能分配算法的優勢，能展示隨機分配的滿意度、預分配的滿意度、算法的執行時間和分配的失敗的人數。

4.1 單個旅客自動分配

單個旅客的自動分配主要采用“先來先服務算法”。系統首先生成航班每位旅客的可選座位集合，采用先來先服務算法模擬航班旅客值機過程中的座位分配算法。

4.2 一組旅客自動分配

一組旅客的自動分配主要滿足結伴同行的旅客，通過采用算法讓他們盡可能自動分配在一起，比如分配在前后排或同一排。

4.3 整機旅客自動分配

整機旅客自動分配，就是根據用戶提交的需求，實現一種自動分配座位的算法，為旅客分配合理的座位，盡可能滿足旅客的個性化需求，提高旅客出行的用戶體驗。用戶提交的需求主要包括前面介紹的靠窗等30多種屬性。

5? 算法的實現

本文主要通過抽取20組數據，分配采用改進的粒子群算法、貪心+匈牙利算法，樸素算法和先到先得算法這4種算法，從算法分配的滿意度、算法分配的時間、算法分配涉及到的主要因素進行分析。得出結論如下。

（1）樸素算法分配滿意度最高（人工消耗大量時間進行置換，將不滿意的人交換，直到分配到滿意的位置，得到最大滿意度）

（2）先來先得算法分配結果滿意度相對較低，為20%～40%，不能滿足大多數旅客。

（3）貪心+匈牙利算法分配結果滿意度比人工分配滿意度相近，接近人工分配最大滿意度，相對于粒子群算法滿意度要低一點。

（4）粒子群算法分配結果滿意度接近于人工分配滿意度，最接近于人工分配結果。相對于貪心+匈牙利算法滿意度更高。

6? 結語

旅客對個體性化服務水平的需求對航空公司的服務提出了更高的要求，改造現有業務模式、提升服務品質、提高運營效率成為了民用航空業的重要目標。航班座位自動分配系統主要基于旅客的各種個性化需求，通過改進的粒子群算法實現為整機旅客分配最大滿意度座位的需求，同時滿足旅客個性化的需求。該算法將應用于中國航信的座位預分配業務系統，預期將會顯著緩解柜臺值機壓力、提升旅客出行的座位滿意度，航班旅客座位預分配算法將會對航空的業務流程產生重要的影響。

參考文獻

[1] 王琨琨.一種航班座位分配算法[J].現代計算機：專業版，2015（14）：37-39.

[2] 張雁茹，趙志剛，李永恒.基于擾動的自適應粒子群優化算法[J].廣西科學，2017，24（3）：258-262.

[3] 董文永，康嵐蘭，劉宇航，等.帶自適應精英擾動及慣性權重的反向粒子群優化算法[J].通信學報，2016，37（12）：1-10.