基于粒子群算法的機型排班系統研究

魯力 劉晨宇

摘? 要：近幾年來，隨著經濟的快速發展選擇乘坐飛機出行的人數逐漸增長，這種現象為民航業帶來發展的同時，也帶來了一系列的挑戰，其中由于民航業具有的高成本的特征，因此面對日益增長的需求如何進行機型的選擇與航班排班就顯得格外重要，本研究通過線性規劃的方法建立了機型排班模型并通過收集不同機型及航線信息對模型采用粒子群算法進行了仿真求解，得到了十分具有可靠性的答案，驗證了模型的科學性。

關鍵詞：航班排班? 排班模型? 線性規劃? 粒子群算法

中圖分類號：V351? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻標識碼：A? ? ? ? ? ? ? ? ? ? 文章編號：1674-098X（2021）02（b）-0004-05

Research on Aircraft Scheduling System based on Particle Swarm Optimization

LU Li1? LIU Chengyu2

（College of Air Traffic Management， Civil Aviation Flight University of China， Guanghan， Sichuan Province， 618307， China）

Abstract： In recent years， with the rapid development of economy， the number of people who choose to travel by aircraft increases gradually. This phenomenon not only brings development to civil aviation industry， but also brings a series of challenges. Due to the high cost characteristics of civil aviation industry， it is particularly important how to select aircraft types and schedule flights in the face of increasing demand. This study adopts linear programming. By collecting the information of different aircraft types and routes， the model is simulated and solved by particle swarm optimization algorithm. The reliable answer is obtained and the scientific nature of the model is verified.

Key Words：? Flight scheduling; Scheduling model; Linear programming; Particle swarm optimization

近些年來，隨著人們生活水平的不斷提高，中國民航機場旅客吞吐量從2013年的75430萬人次增長到2019年的135200萬人次（見圖1），旅客周轉量更是從2014年的6334.2億人公里增長到了2019年的11705.1億人公里（見圖2），因此機型的規劃排班問題開始變得格外重要，規劃排班類問題是生活中十分常見的一類問題，在民航業中排班問題也已有了很廣泛的研究，2008年李麗娟基于免疫算法針對飛行的安全問題與公司成本進行了排班模型的研究[1]，2016年繆晨暉針對天氣的干擾對航班排班進行了研究[2]，同年，李耀華，王磊利用遺傳算法對機型排班進行了優化[3]，劉婧，賈寶惠基于啟發式算法對機型排班進行了優化[4]，宋政對不正常航班的優化調度進行了研究[5]，2018年于焯、樊瑋對機場航班航線調度進行了仿真優化管理[6]，2020年王舳通過遺傳算法及啟發式算法對正常性飛機排班計劃進行了研究[7]。

本研究則主要通過航空公司收益的角度建立航班排班計劃模型，通過不同機型在不同航線上的不同收益及不同成本建立目標函數使航空公司收益最大化，通過不同航線的最大客流量和最小客流量及不同機型的載運量與不同機型最大可安排次數之間的關系建立約束條件，通過粒子群算法進行仿真求解驗證模型可靠性。

1? 模型的建立

1.1 約束條件的設定

由于航班排班涉及到眾多復雜的問題，本研究選取的主要影響航班排班因素如下假設條件。

假設一：假設航班排班目標僅考慮公司收益;

假設二：航班排班只考慮機型的選擇、安排次數及航線運輸量的限制。

1.2 文中公式采用的符號說明

文中公式采用的符號說明見表1。

1.3 相關概念及理論方法

1.3.1 航班排班

航班排班是指航空公司制定的飛行計劃重要環節，通過合理的航班排班，可使得航空公司獲取最大的利潤，但其考慮的因素較為復雜，往往涉及到航班的起飛時刻、機型選擇、頻次選擇等，因此，復雜的航班排班是一項可以關系到航空公司能否正常運營的重要工作，從而，決定著航空公司的市場競爭力。本研究通過模型及算法對航班排班進行仿真計算，可以為航班排班的人工智能化起到重要的啟發式作用。

1.3.2 航線的獲取

根據民航政府部門公布的有效全國范圍航路圖以及國內航空資料匯編中的各個機場的進場、離場、進近航圖，可以從中獲取航班始發地至目的地的航線，其具有一定最低安全高度、航線保護區寬度以及磁方向等信息，可使得飛機在空中做載客飛行的線路。

1.3.3 粒子群算法

粒子群算法是模仿鳥類群體尋覓食物的一種協作性的隨機搜索算法，利用群體中各別獨立個體對信息的共享，從而使得尋覓過程從無序到有序，以進一步縮小搜索范圍，獲得最優解，可以很大程度地減少計算量，且計算出來的結果較為精確，粒子群算法基本形式如下[8]：

（1）

其中w是權重因子;vi為粒子速度;C1，C2為非負常數;rand（1），rand（2）為0～1的隨機數;pbesti是該粒子已知最好為最好位置;gbesti是為該粒子群已知最好位置;xi該粒子當前位置。

2? 實際問題的建立與求解

2.1 航班排班模型的建立

該模型以某航空公司收益最大化為目標，排除特殊情況的發生，航班排班模型如下所示：

（2）

其中，公式中的代數符號參考1表中說明。

2.2 基于粒子群算法的求解

由于現實情況下航空公司擁有大量的航線網絡及多種機型，因此模型變量龐大，且隨著航空公司每新開辟一條航線或新購買一架飛機，其模型的計算量都將呈幾何式增加，因此對于該模型的求解可通過粒子群算法進行個體的信息共享下的快速尋優，具體算法流程如圖3所示。

2.3 模擬仿真

2.3.1 數據收集

收集的某航空公司旗下機型信息如表2所示。

某航空公司航線分布信息如表3所示。

不同機型執行不同航線飛行任務公司收益如表4所示。

2.3.2 仿真計算

將表2至表4的信息帶入公式（2）通過matlab編程仿真計算得到最終安排方案為表5所示。

2.4 結論

本節內容通過對某公司旗下的航空公司進行采樣飛機機型、航線分布、收益等信息數據，將數據作為限制條件帶入到粒子群算法進行仿真計算，能合理安排出各航線采用確切的機型可以為公司獲取最大的收益，結果表明，計算出的結論與公司實際情況較為符合。

3? 結語

本研究采用的是粒子群算法建立模型，該模型從收益的角度可運用于解決航空公司機型排班任務，并通過粒子群算法對數據進行求解驗證了模型的科學性，采用粒子群算法避免了當航線網絡復雜機型種類多時求解計算量龐大的問題，可以更快的收斂于最優解，但與此同時模型有可能造成陷入局部最優解的問題。但是本研究采用的數據分析較為簡單，比如航空公司選取旗下公司，航線分布簡單，機型簡單，在后續的研究中，將豐富航線分布、增加機型等信息以及其他約束條件使結果更加具有可靠性。

參考文獻

[1] 李麗娟.航班排班模型及算法研究[D].南京：南京航空航天大學，2008.

[2] 繆晨暉.基于天氣干擾的航班排班問題研究[D].南京：南京航空航天大學，2016.

[3] 李耀華，王磊.基于改進遺傳算法的航班排班優化方法研究[J].系統仿真學報，2016，28（? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?3）：620-626.

[4] 劉婧，賈寶惠.基于啟發式算法的飛機指派優化模型及算法[J].系統仿真技術，2016，12（2）：79-82+94.

[5] 宋政.不正常航班優化調度方法研究[J].內江科技，2016，37（6）：46-47.

[6] 于焯，樊瑋.機場航班航線調度優化管理仿真研究[J].計算機仿真，2018，35（7）：54-58.

[7] 王舳. 面向正常性的飛機排班優化方法研究[D].天津：中國民航大學，2020.

[8] 李樹松.粒子群算法在優化問題中的應用研究[J].科學技術創新，2020（32）：103-104.