基于粒子群算法的航班座位自動分配系統(tǒng)

李方方 蔣理 戴勝 秦勝男

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

關(guān)鍵詞：自動分配? 粒子群? 航班座位

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

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

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

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

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

2? 系統(tǒng)的設(shè)計與實現(xiàn)

航班座位自動分配系統(tǒng)整體是基于MVVM模式設(shè)計的，根據(jù)軟件開發(fā)中前后端模式的基本歷程，采用了前后端分離的基本結(jié)構(gòu)。前端完全負責(zé)View層和ViewModel層。View是視圖層，也就是所謂的用戶界面;ViewModel是生成和維護的視圖數(shù)據(jù)層，是對后端獲取的Model數(shù)據(jù)完成數(shù)據(jù)轉(zhuǎn)換的功能;兩者完成封裝，來生成視圖數(shù)據(jù)模型。后端負責(zé)Model層，主要實現(xiàn)各種業(yè)務(wù)邏輯和數(shù)據(jù)庫操作。

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

3.1 粒子群算法

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

3.2 粒子群算法的改進

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

3.2.1 參數(shù)選擇與優(yōu)化

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

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

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

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

3.2.2 極值擾動的引入

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

4? 座位自動分配過程

該系統(tǒng)實現(xiàn)單個旅客座位分配、一組旅客分配、整機旅客分配。根據(jù)分配結(jié)果展示單個旅客分配的位置，一組旅客的位置和整機旅客分配的位置;實現(xiàn)了算法分配過程的展示，計算出旅客的滿意度。實現(xiàn)了旅客信息的展示、編輯添加旅客的信息、添加多人的信息、查看所有旅客的信息;展示了旅客的年齡分布圖;展示了旅客的個人的屬性偏好和一組的旅客的關(guān)系偏好。根據(jù)隨機分配的算法與智能分配算法的對比展示出智能分配算法的優(yōu)勢，能展示隨機分配的滿意度、預(yù)分配的滿意度、算法的執(zhí)行時間和分配的失敗的人數(shù)。

4.1 單個旅客自動分配

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

4.2 一組旅客自動分配

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

4.3 整機旅客自動分配

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

5? 算法的實現(xiàn)

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

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

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

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

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

6? 結(jié)語

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

參考文獻

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

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

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