基于粒子群算法的机型排班系统研究

鲁力 刘晨宇

摘  要：近几年来，随着经济的快速发展选择乘坐飞机出行的人数逐渐增长，这种现象为民航业带来发展的同时，也带来了一系列的挑战，其中由于民航业具有的高成本的特征，因此面对日益增长的需求如何进行机型的选择与航班排班就显得格外重要，本研究通过线性规划的方法建立了机型排班模型并通过收集不同机型及航线信息对模型采用粒子群算法进行了仿真求解，得到了十分具有可靠性的答案，验证了模型的科学性。

关键词：航班排班  排班模型  线性规划  粒子群算法

中图分类号：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.