论文部分内容阅读
摘 要：在前人运用遗传算法解决飞机调度问题中的航班规划问题的基础上，利用云模型云滴的随机性和稳定倾向性改进遗传算法中交叉率和变异率的设置方式，设计云自适应遗传算法对该问题进行再优化。通过对求解变量，即各机型在航线上的航次的整数编码，实现求解目标在遗传算法中的表达，并且通过利用基于惩罚方式的有效修补策略对染色体的实用性进行修补，减少非法解的出现，使得求解结果符合实际情况。通过国内A机场与其它城市间的航线航班的规划实例，对模型和算法的有效性进行验证。
关键词：飞机调度 航班规划 云自适应遗传算法
一、引言
随着航空公司飞机数的增加以及航线的复杂化，人工航班规划已经满足不了要求。因此研究一种算法，使得可以利用计算机科学、高效、合理地制定航班计划具有重大的意义。解决航班规划问题，传统的方法是整数规划及线性规划等数学规划方法。如都业富最早提出航班规划的一个动态规划的算法框架，黄小荣采用数学的方法在基于收益的前提下探讨了航班规划问题。近年来，智能计算方法逐渐开始在飞机调度问题上得到了应用。孙宏等人采用了模拟退火问题对飞机调度中的飞机排班问题进行了求解，李玥采用基于不均等策略的多目标遗传算法解决了飞机的路由安排问题。不同于前人的研究，本文针对飞机调度问题中的航班规划环节论述如何用云自适应遗传算法解决航班规划的问题，使得在航班止常运行情沉下，航空公司能实现最大的利益。
二、航班规划问题
本文考虑的是飞机排班问题中的航班规划问题，即是根据飞机的机型特性、航路的特性，在利益最大化的前提下，得到每种机型的飞机在每个航线上的初步班次安排，并在实际条件的约束下调整，最终得到具有比较大的现实参考意义的航班班次安排。假设一个拥有M种类型的飞机的航空公司，并且对以一个中心城市A向其它N个城市的航线进行航班的规划。给定每种机型飞机的特性数据（座位容量、小时飞行成本、日利用率和飞机数量）和每条航线的特性数据（票价、做客率和飞行时间）。
三、云自适应遗传算法
云自适应遗传算法是对云遗传算法的改进，它由云模型的X条件发生器根据适应度函数值的大小自适应产生交叉和变异概率。其基本原理：高于种群平均适应度的个体，随着其适应度的增加，为了对较优个体进行保护，交叉和变异概率逐渐减小；而低于种群平均适应度的个体采用最大交叉变异概率，使其产生较优个体。云自适应遗传算法的操作步骤为：⑴设计编码，初始化种群，并初始化，设计适应度函数；⑵计算种群适应度值；⑶选择最优个体保留至下一代，淘汰最差个体选择操作；⑷设计交叉算子，由云模型X条件发生器算法产生交叉率，选择两个个体进行交叉操作；⑸设计变异算子，由云模型X条件发生器算法产生变异率，选择个体进行变异操作；⑹转至步骤⑵，直到停止条件被满足。
四、模型建立
1.染色体编码。将问题考虑的求解变量定为每种机型的飞机在每条航线上的飞行的次数，记，其中，具体含义为机型在从城市A到城市j的航线上有次往返。所以，每个染色体的编码如下：（1）
染色体CH的每个基因都有其取值范围，遗传算法的目标就是在这些变量的范围内对这些变量进行取值，组合，构造出最优的解。在完成对染色体的编码后，我们给定基因（变量）的求解范围。具体的方法如下（2）
2.适应度函数。在航班规划这个问题上，适应度函数是和染色体编码中的基因直接关联的。根据“收益=总收入-总成本”，可以得到如下公式 （3），式（3）中：--客座率、座位容量、票价与班次的乘积，得到的是总收入；--小时飞行成木、飞行时间与班次的乘积，得到的是总成本。
3.约束条件。由于航班规划问题受到众多约束条件的限制，我们将上而提到的约束条件用数学表达形式表示出来。①飞机数量和日利用率约束，根据相应的条件，可得到该约束条件的函数表达式如下（4）；②机型可用性约束，当某机型s对于某航线不可用时，则该机型在该航线上的航次。即若，则的取值区间定为[0，N]；③需求实现约束，可得到该约束条件的函数表达式如下（5），从城市A到城市j的航班总数不得小于下限式；④降落条件限制，（6），从城市A到城市j的航班总数不得超过所能承受的上限。
4.遗传算子。遗传算法自从提出以来，关于选择、交叉和变异等遗传算子已经得到广泛而深入的研究，并且在具体的实际问题中的应用也各具特色。本文采用上文所述的云模型的X条件发生器根据适应度函数值的大小自适应产生交叉和变异概率。
5.仿真测试及算法对比。为验证上述算法的正确性与可行性，进行仿真测试。以城市A机场为出发点进行仿真测试，采用云自适应遗传算法对飞机航班规划问题进行求解与优化。问题如下：给出一个以城市A为中心，分别飞往3个大城市（B、C和D）的简单航线网络。航空公司须决定使用哪种机型，通过合理航班规划，实现收益最大化。表1列出各种机型的相关特性，表2列出飞行时间和票价。表3是在某个季度的市场信息。由于某种原因，737-800机型飞机暂时不能飞往C的航班，而757-200机型飞机暂时不能飞往D的航班。
问题的求解根据整体的算法流程来进行。遗传算法采用的群体规模为20，进行了100代的进化，参数交叉概率和变异概率分别为0.7和0.07。由于遗传算法是一种带指导的随机搜索算法，因此这里对求解过程进行了20次的测试，求解结果如表4所示。
从表4看到，本文的算法能够较好地满足到各个城市的往返航班要求。但是，从比较中还是可以看到，算法在满足B、C两个城市的航班要求的基础上，倾向于将多余的机力放到D，这个看上去虽然有点不实际，因为到D可能不需要那么多航班。不过在给定的上下限的条件下，算法要做的是尽量使总收益最大化，所以这反而佐证算法的有效性和高效性。至于需要限制到D的航班次数，可以进一步采用相关的约束条件加以约束。
算法对比。为检验云自适应遗传算法的准确性和实效性，在此采用标准遗传算法和云自适应遗传算法对算例进行求解对比分析，如表5所示。可看出，云自适应遗传算法搜索成功率大于标准遗传算法，最劣值小于标准遗传算法，反映出云自适应遗传算法的全局搜索能力强于标准遗传算法。平均成功搜索迭代次数云自适应遗传算法小于标准遗传算法，可见云自适应遗传算法在保证快速收敛的同时并保持很好的全局搜索能力。
五、结语
本文采用云自适应遗传算法对飞机调度过程中的航班规划环节进行求解和优化。从仿真测试和算法对比的结果可以看出，用云自适应遗传算法解决航班规划问题是可行的，并且简单、易于被人们接受；鲁棒性强，能适应不同的约束情况，求解速度相对较快，求解效果也很好。同时，也可以体现，云自适应遗传算法在全局搜索能力、搜索成功率和收敛速度方面由于标准遗传算法。另外本文采用约束方程来表示相应的约束条件，因此相关的约束条件可以随时更变，也可以随时增加，具有很大的灵活性。本文只举例几个典型约束条件下的飞机调度情况，而实际中的约束将会更多更复杂，但增加新的约束条件我们只需要添加新的约束公式便可得到相应约束下的最优解。并且在算法框架中，机型参数及市场信息都是其输入参数，因此，在不同的季度，算法都能夠适用。算法具有强大的可扩展性和通用性，适合投入实际应用中。
参考文献：
[1]都业富. 实用航班计划优化方法[J]. 系统工程理论与实践，1995，02：23-27.
[2]黄小荣. 航班收益分析与最佳航班安排[J]. 中国民航学院学报（综合版），2012，06：21-24+28.
[3]孙宏，杜文. 飞机排班数学规划模型[J]. 交通运输工程学报，2010，03：117-120.
[4]李玥. 基于多目标遗传算法的航空发动机多目标优化控制[D].南京航空航天大学，2007.
关键词：飞机调度 航班规划 云自适应遗传算法
一、引言
随着航空公司飞机数的增加以及航线的复杂化，人工航班规划已经满足不了要求。因此研究一种算法，使得可以利用计算机科学、高效、合理地制定航班计划具有重大的意义。解决航班规划问题，传统的方法是整数规划及线性规划等数学规划方法。如都业富最早提出航班规划的一个动态规划的算法框架，黄小荣采用数学的方法在基于收益的前提下探讨了航班规划问题。近年来，智能计算方法逐渐开始在飞机调度问题上得到了应用。孙宏等人采用了模拟退火问题对飞机调度中的飞机排班问题进行了求解，李玥采用基于不均等策略的多目标遗传算法解决了飞机的路由安排问题。不同于前人的研究，本文针对飞机调度问题中的航班规划环节论述如何用云自适应遗传算法解决航班规划的问题，使得在航班止常运行情沉下，航空公司能实现最大的利益。
二、航班规划问题
本文考虑的是飞机排班问题中的航班规划问题，即是根据飞机的机型特性、航路的特性，在利益最大化的前提下，得到每种机型的飞机在每个航线上的初步班次安排，并在实际条件的约束下调整，最终得到具有比较大的现实参考意义的航班班次安排。假设一个拥有M种类型的飞机的航空公司，并且对以一个中心城市A向其它N个城市的航线进行航班的规划。给定每种机型飞机的特性数据（座位容量、小时飞行成本、日利用率和飞机数量）和每条航线的特性数据（票价、做客率和飞行时间）。
三、云自适应遗传算法
云自适应遗传算法是对云遗传算法的改进，它由云模型的X条件发生器根据适应度函数值的大小自适应产生交叉和变异概率。其基本原理：高于种群平均适应度的个体，随着其适应度的增加，为了对较优个体进行保护，交叉和变异概率逐渐减小；而低于种群平均适应度的个体采用最大交叉变异概率，使其产生较优个体。云自适应遗传算法的操作步骤为：⑴设计编码，初始化种群，并初始化，设计适应度函数；⑵计算种群适应度值；⑶选择最优个体保留至下一代，淘汰最差个体选择操作；⑷设计交叉算子，由云模型X条件发生器算法产生交叉率，选择两个个体进行交叉操作；⑸设计变异算子，由云模型X条件发生器算法产生变异率，选择个体进行变异操作；⑹转至步骤⑵，直到停止条件被满足。
四、模型建立
1.染色体编码。将问题考虑的求解变量定为每种机型的飞机在每条航线上的飞行的次数，记，其中，具体含义为机型在从城市A到城市j的航线上有次往返。所以，每个染色体的编码如下：（1）
染色体CH的每个基因都有其取值范围，遗传算法的目标就是在这些变量的范围内对这些变量进行取值，组合，构造出最优的解。在完成对染色体的编码后，我们给定基因（变量）的求解范围。具体的方法如下（2）
2.适应度函数。在航班规划这个问题上，适应度函数是和染色体编码中的基因直接关联的。根据“收益=总收入-总成本”，可以得到如下公式 （3），式（3）中：--客座率、座位容量、票价与班次的乘积，得到的是总收入；--小时飞行成木、飞行时间与班次的乘积，得到的是总成本。
3.约束条件。由于航班规划问题受到众多约束条件的限制，我们将上而提到的约束条件用数学表达形式表示出来。①飞机数量和日利用率约束，根据相应的条件，可得到该约束条件的函数表达式如下（4）；②机型可用性约束，当某机型s对于某航线不可用时，则该机型在该航线上的航次。即若，则的取值区间定为[0，N]；③需求实现约束，可得到该约束条件的函数表达式如下（5），从城市A到城市j的航班总数不得小于下限式；④降落条件限制，（6），从城市A到城市j的航班总数不得超过所能承受的上限。
4.遗传算子。遗传算法自从提出以来，关于选择、交叉和变异等遗传算子已经得到广泛而深入的研究，并且在具体的实际问题中的应用也各具特色。本文采用上文所述的云模型的X条件发生器根据适应度函数值的大小自适应产生交叉和变异概率。
5.仿真测试及算法对比。为验证上述算法的正确性与可行性，进行仿真测试。以城市A机场为出发点进行仿真测试，采用云自适应遗传算法对飞机航班规划问题进行求解与优化。问题如下：给出一个以城市A为中心，分别飞往3个大城市（B、C和D）的简单航线网络。航空公司须决定使用哪种机型，通过合理航班规划，实现收益最大化。表1列出各种机型的相关特性，表2列出飞行时间和票价。表3是在某个季度的市场信息。由于某种原因，737-800机型飞机暂时不能飞往C的航班，而757-200机型飞机暂时不能飞往D的航班。
问题的求解根据整体的算法流程来进行。遗传算法采用的群体规模为20，进行了100代的进化，参数交叉概率和变异概率分别为0.7和0.07。由于遗传算法是一种带指导的随机搜索算法，因此这里对求解过程进行了20次的测试，求解结果如表4所示。
从表4看到，本文的算法能够较好地满足到各个城市的往返航班要求。但是，从比较中还是可以看到，算法在满足B、C两个城市的航班要求的基础上，倾向于将多余的机力放到D，这个看上去虽然有点不实际，因为到D可能不需要那么多航班。不过在给定的上下限的条件下，算法要做的是尽量使总收益最大化，所以这反而佐证算法的有效性和高效性。至于需要限制到D的航班次数，可以进一步采用相关的约束条件加以约束。
算法对比。为检验云自适应遗传算法的准确性和实效性，在此采用标准遗传算法和云自适应遗传算法对算例进行求解对比分析，如表5所示。可看出，云自适应遗传算法搜索成功率大于标准遗传算法，最劣值小于标准遗传算法，反映出云自适应遗传算法的全局搜索能力强于标准遗传算法。平均成功搜索迭代次数云自适应遗传算法小于标准遗传算法，可见云自适应遗传算法在保证快速收敛的同时并保持很好的全局搜索能力。
五、结语
本文采用云自适应遗传算法对飞机调度过程中的航班规划环节进行求解和优化。从仿真测试和算法对比的结果可以看出，用云自适应遗传算法解决航班规划问题是可行的，并且简单、易于被人们接受；鲁棒性强，能适应不同的约束情况，求解速度相对较快，求解效果也很好。同时，也可以体现，云自适应遗传算法在全局搜索能力、搜索成功率和收敛速度方面由于标准遗传算法。另外本文采用约束方程来表示相应的约束条件，因此相关的约束条件可以随时更变，也可以随时增加，具有很大的灵活性。本文只举例几个典型约束条件下的飞机调度情况，而实际中的约束将会更多更复杂，但增加新的约束条件我们只需要添加新的约束公式便可得到相应约束下的最优解。并且在算法框架中，机型参数及市场信息都是其输入参数，因此，在不同的季度，算法都能夠适用。算法具有强大的可扩展性和通用性，适合投入实际应用中。
参考文献：
[1]都业富. 实用航班计划优化方法[J]. 系统工程理论与实践，1995，02：23-27.
[2]黄小荣. 航班收益分析与最佳航班安排[J]. 中国民航学院学报（综合版），2012，06：21-24+28.
[3]孙宏，杜文. 飞机排班数学规划模型[J]. 交通运输工程学报，2010，03：117-120.
[4]李玥. 基于多目标遗传算法的航空发动机多目标优化控制[D].南京航空航天大学，2007.