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

李方方 蔣理 戴勝 秦勝男

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

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

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

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

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

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

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

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

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

3? 粒子群算法簡(jiǎn)介及其改進(jìn)

3.1 粒子群算法

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

3.2 粒子群算法的改進(jìn)

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

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

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

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

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

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

3.2.2 極值擾動(dòng)的引入

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

4? 座位自動(dòng)分配過程

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

4.1 單個(gè)旅客自動(dòng)分配

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

4.2 一組旅客自動(dòng)分配

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

4.3 整機(jī)旅客自動(dòng)分配

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

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

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

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

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

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

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

6? 結(jié)語

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

參考文獻(xiàn)

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

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

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