摘    要：为了提高航空企业飞机排班计划的自动化水平，分析了航空企业飞机排班计划编制流程，将这个复杂组合优化问题分解为3个组合优化问题，重点研究了其中的飞机指派优化问题，归纳了要考虑的主要约束条件，以优化理论为基础，针对飞机排班计划优化问题中的关键问题飞机指派问题建立了飞机指派优化模型，模型考虑了飞机与航班之间在机型、飞行区域、器流量等条件上的匹配要求，井给出了模型约束条件的编码方法，同时根据大量实际生产数据给出相应的惩罚系数表为求解模型，构造了一种自适应单亲遗传算法，算法选用了适合模型的遗传算子，采用动态调整遗传算子操作概率的方式加快优化速度采用航空公司的实际航班数据进行仿真实例研究结果表明，该模型和算法切买可行。

关键词：生产计划；排班调度；飞机指派；遗传算法

中图分类号：TP 29    文献标识码：A

    飞机排班是航空公司生产计划中的一项控制性工作，由于认识到飞机排班工作在航空运输生产中的重要性和复杂性，欧美的许多大型航空公司从20世纪80年代开始在生产中广泛采用专门的飞机调度管理系统来管理这项工作。在中国，随着各航空公司机队规模的扩大，航班量的增长，特别是航线网的日益大型化和复杂化，人工排班的落后方式已难以满足运营管理工作的要求，因此实现飞机排班工作的自动化已大势所趋。从国内来看，由于航空公司前几年规模普遍偏小，因此对生产计划管理工作缺乏重视，计划方式简单、粗放，因而对生产计划管理方面的研究非常有限。

    近几年来，随着运营规模的扩大，航空运输市场的开放，市场竞争不断加剧，航空公司逐渐意识到加强生产计划管理工作的重要性和急迫性，但是总体来说，关于飞机调度管理方面的理论研究还处于起步阶段。

    为了提高生产调度的自动化永平，本文针对目前航空公司排班计划现状，分析了飞机排班计划编制流程，着重研究了其中的飞机指派问题，建立了飞机指派优化模型，同时，构造了一种自适应单亲遗传算法快速求解此模型。

    1)问题提出  针对飞机排班问题，国内外有关学者进行了相应的研究，文献[4]概括了飞机指派问题中的一些基本概念、模型和算法，并指出了进一步的研究方向。文献[5]提出了一种基于传递闭包法的进／离场航班分类方法考虑4种不同因素的条件下建立了航班分类模型，并给出了各类航班单位时间延误成本的计算公式。文献[6]以航班总收益****化为目标，提出了一个针对单枢纽机场航线网络的Lagrangian松驰算法，但是对于大多航空公司需要多种机型混合排班的情况并不太适用。文献[1]针对单枢纽航线网络的特点，以所需飞机数最少，航班在枢纽机场的过站衔接最紧凑为目标，提出了描述航班衔接问题的最小费用****流网络模型。文献[2]针对机场航班延误问题进行了研究，文献[3]研究了起降航班的排序问题，都没有涉及飞机排班调度中的飞机指派问题。

    飞机排班的实质就是根据市场部下达的航班计划、每架飞机的技术状况以及飞机调度指令，为每个航班指定一架具体执行的飞机。一般地，航空公司首先要向航班管理部门申请航班，在获得批准后作为本公司的执行航班；然后，计划部门针对本公司要执行的所有航班，综合考虑公司所拥有的飞机情况、飞机调度的诸多约束等条件来编制飞机的排班计划，在保证航班正常运行的前提下实现效益****他，这是一个复杂的组合优化问题。

    由于近年来航空公司机队规模不断扩大，航班量在日益增长，而大多航空公司编制飞机排班计划都是采用人工或半人工的方式，因此飞机排班问题成了航空公司发展中迫切需要解决的一个问题。

    目前，飞机排班的具体方法如下：

    ①首先根据公司的所有航班信息，将所有航班编制为若于个航班串，所谓航班串就是将本航空公司的一个到港航班与另一个离港航班衔接起来，生成若干个可以由一架飞机去执行的航班连接，每一个称为一个“航班串”。

    ②针对编制好的航班串计划，对每一个航班串指派执行飞机。

    ③对每一个航班串和执行飞机指派空勤机组。这样，一个飞机排班问题就包括了航班串编制、飞机指派、机组指派3个优化问题，而且它们互有影响和联系。

    由于飞机排班问题规模大、约束条件众多，很难建立一个模型和算法来求解，一个有效的方法就是采用分层分块分别建立模型和算法，然后再综合平衡，以求****效果。本文主要针对飞机排班中的飞机指派优化问题进行研究，这个问题需要考虑的主要约束如下：

  ①飞机要满足所执行航班串中所有航班的机型要求。

  ②飞机的适合飞行区域条件要满足所执行航班串中航班要求。

  ③飞机的载客量要满足所执行航班串中的航班客流量的需求，

  2)飞机指派优化模型建立飞机指派问题就是针对已经编制好的航班串计划，综合考虑公司可用飞机的情况，为每一个航班串指派一架执行飞机，在满足飞机和航班的各种约束条件的基础上使公司的运行成本****。由于飞机和航班的数量都比

较多，这是一个大规模的复杂优化问题，本文建立飞机指派优化模型如下：

    式中，k=1,2，...m，m为航班串数，i=1.,2,...nk，nk为第k和航班串内的航班数；jj=l，2，…，n，n为飞机数cij为航班i和飞机j之间的匹配差异惩罚值，pij为飞机j与航班i要求机型代码、飞行区域代码、载客量和客流量之间的差异惩罚值,Tj为第j架飞机的适合飞行区域代码；Rki为第A个航班串内第i个航班要求的飞机最小飞行区域代码；pj为笫j架飞机的载客容量；P为第t个航班串内第j个航班的平均客流量；dj为第j架飞机的机型代码；Dk为第A个航班串内第i个航班的要求机型代码。

    目标函数(1)针对所有的航班串在指派飞机后的函数惩罚适应值最小，是针对批量的航班的全局优化，约束条件(2)保证选择与航班串数相等的执行飞机数，约束条件(3)保证为每一个航班串只指派一架执行飞机，约束条件(4)要求为航班串指派的飞机满足该航班串内的任一航班的飞行区域要求，约束条件(5)要求为航班串指派的飞机满足该航班串内的任一航班客流量的需求，约束条件(6)要求为航班串指派的飞机的机型代码要大于该航班串内任一航班的要求。

  为了模型和算法计算方便，将各机型、飞行区域编制为自然数代码，机型代码、载客量、飞行区域的差异惩罚值，经过大量数据仿真研究，选取见表1～表3。

    其中，飞机j被指派执行航班！所在的航班串，di为航班i要求机型代码，dj为飞机j的机型代码，机型代码根据机型的不同采用1，2，3，4，5，6来表示，Pi量，Ri为航班；飞行区域代码，Ri为飞机j的可飞行区域代码，飞行区域代码按飞行区域等级用l，2，3，4，5来表示。

    文献[1，2，3，5，6]都是针对航班问题进行了研究，没有单独对飞机指派问题进行研究，文献[4]对飞机指派问题进行了研究，但是只是给出了一般概念和方法，没有深人研究。

  本文建立模型对此问题进行了深入研究，并给出了一种机型代码、载客量、飞行区域等因素的处理方法一自然数编码，基于这种编码同时给出了惩罚值参数表，为航空公司编制飞机指派计划提供了很大的方便。

  本文所建立模型的求解属于NP -难问题，采用数学规划等方法很难求解。本文根据模型特点构造一种自适应单亲遗传算法，算法中主要采用自然数编码，以单点基因换位为主，辅以多点基因换位和基因移位等遗传算子的方法，基因换位和移位的概率自适应动态调整，同时使用专家规则进行修正。

    1)遗传操作算子基因换位算子是按一定的概率交换染色体某些位置上基因的过程，被交换位置随机确定。基因换位可分为单点换位和多点换位，单点换位是一次只交换一对（2个）基因的位置（如下实例所示）；多点换位是对预先给定的正整数N，取随机数-次交换。对基因。本文在求解过程中以单点基因换位为主，辅以多点基因换位和单点基因移位算子。

    2)单点基因换位概率、多点基因换位及基因移位概率的自适应调整本文将M Srinivas提出的自适应遗传算法：引入到单亲遗传算法中，并针对M Srinivas算法的缺点，根据适的集中程度，动态调整每一代群体的单点基因换位概率pe、多点基因换位概率pm及基因移位概率ps，采用每一代群体的****适应度值fmax最小适应度值Lm、平均适应度值来作为适应值集中程度的判断标准。在本文的算法中，判断为当代群体中个体趋于集中，根据集中程度自适应调整概率；否则，判断为群体中个体不趋于集中，仍维持正常情况下的单点基因换位概率pe、单点基因换位概率pm及基因移位概率ps。

    概率调整公式如下：

    3)自适应单亲算法求解流程如下：

    ①输入模型求解所需数据读入要计算的合同信息。

    ②算法参数的初始化确定算法种群数目和结束****循环代数，和基因单点换位、多息换位、基因移位的初始概率peo，pmo，pso，然后根据种群数目给出一代初始的染色体，作为当前代染色体。

    ③计算当前代染色体的函数适应值，记录****个体作为当前****解，并判断是否满足结束准则，如是，则停止转⑦。否则，进行下一步④。

    ④对当前染色体进行概率的自适应动态调整，按公式计算单点基因换位概率pe、单点基因换位概率pm及基因移位概率ps。

    ⑤对当前染色体进行单亲遗传操作：以设定的概率pe，pm，ps依次进行基因单点换位、多点换位和单点移位操作，最后进行选择操作，选择出一代****的染色体。

    ⑥将选出的一代染色体作为当前代染色体，转③。

    ⑦输出当前****解作为算法的解。

    为了验证飞机指派优化模型及算法，选取一个航空公司一周10个航班串，从15架可用飞机中选取飞机执行航班串，原始数据，见表4～表6。

    在算法求解中，本文采用基本单亲遗传算法与文中的改进的自适应单亲遗传算法进行了比较研究。

    在比较研究中，本文自适应单亲遗传算法参数和基本单亲遗传算法选取相同的参数如下：

  种群数目选为10，单亲遗传算子的单点基因换位初始概率为peo=0.95，多点基因换位概率为pm0=0 15，单点基因移位概率为pso=0 15，算法结束准则为连续迭代300代。

    不同的就足基本单亲遗传算法没有种群集中程度的判断，仿真绪果如图l所示。

    求解结果，见表6。

    ****目标函数值分别为364 500，529190。基本单亲遗传算法也可以求得可行解，但结果较差，由于篇幅原因文中不再列举其运算结果。

    表4为仿真实例的航班信息，包括了根据模型需要编制的机型代码和飞行区域代码，根据这些航班信息编制成若于个航班串，为了计算方便，从中随机选取了10个航班串（表6的前两列）作为模型和算法的初始数据。

    表5为飞机信息表，由于篇幅原因只列出了算法中需要用到的信息。

    表6中的第二列就是由表4中的航班序号组成的航班串，最后一列为模型和算法计算结果，为航班串选定的执行飞机的序号。

    图l为算法的适应值跟踪图：由算法求解结果可以看出，模型和算法可以很快为航班串选定执行飞机，而且满足航班运行要求，是很好的飞机指派的结果。根据运算结果的图表也可看出，在相同的参数条件下，本文建立的改进的混合遗传算法跟基本单亲遗传算法相比，运算结果更优，而且收敛速度更快。由图1可看出，随着迭代次数的增加，优化效果也越来越来明显，但是计算时间也会增加，具体的迭代次数需要棂据生产实际的情况来决定。

    目前国内大部分航空公司进行飞机排班汁划时都是人工在编制计划，飞机指派也是人工或半人工方式进行，针对上述的10个航班串的飞机指派计划人工一般需要几个小时的计算后才能编制好一个可行的计划。而采用本文的模型和算法，只用十几秒就可以将飞机指派计划编制完成，同时优化效果要远远好于人工方式．随着飞机数量的增加，航班串数目的增大，人工方式变得越来越困难，而本文建立的模型和算法能够很好地满足航空公司编制排班计划的需要，大大提高排班计划的自动化水平，满足当前航空公司的迫切需求。

  本文分析了飞机排班计划的编制流程，重点研究了其中的飞机指派优化问题，建立了飞机指派的优化模型，综合考虑了航班运行的各项要求。同时，构造了一种自适应单亲遗传算法进行快速求解。通过实际生产数据进行应用研究结果表明，本文建立的模型和算法切实可行，飞机指派计划的编制效果良好，可提高航空公司生产调度的自动化水平。