机组空运航班环的计算机辅助生成步骤
已经介绍了空运航班串的两种基本生成方法，即时空网络法和空运航班连接 网络法。对手工编制空运航班串都很有效，只要空运航班量不是太大，都可以获得必需的航班串。在手工编制时，一般并不找出所有可行的空运航班串，而是根据经验找到能覆盖 所有空运航班的若干空运航班串即可。这样得到的空运航班串一般不能保证最优，如果想获得 最优的空运航班串，应当给出所有可行的空运航班串，然后建立数学模型并设计有效算法， 通过优化计算，从中找出最优的一组。 空运航班环是由一条或多条空运航班串连接而成的，所以生成空运航班环首先要生成空运航班 串。对于大规模空运航班问题，要得到所有的空运航班环，必须采用计算机辅助生成系统。 下面讨论计算机辅助生成空运航班环的方法。
计算机辅助生成空运航班环需给定以下数据：
①空运航班计划；
②基地机场；
③过夜机场和过夜飞机。
在生成空运航班串的同时必须考虑如下限制条件。
(1)适航规定：最小衔接时间、执勤小时和飞行小时限制。
（2)公司规定：一个值勤期的最大、最小空运航班数等。
为便于算法设计，采用空运航班连接网络，则空运航班环按以下步骤生成。
（1)对每种机型执行的空运航班子集，按空运航班出发机场，再分成出发空运航班子集。
（2)构造各机场出发空运航班树，即以各出发机场为根节点，用衔接边连接从它出 发的各空运航班节点，分裂各空运航班节点成出发和到达两个机场节点，之间用空运航班边连 接，形成空运航班节线。
(3)从基地机场出发空运航班树开始，将各空运航班节线的到达机场节点与从该机场 出发的空运航班树的根节点合并，删除衔接时间短于最小衔接时间的衔接边和空运航班
（4)重复上述步骤直到各空运航班节线无可衔接的空运航班，得到以各基地机场为根 节点（网络的源或发点）的空运航班连接树，它的叶节点是基地机场或过夜机场、
（5)在空运航班连接树中加上终止机场节点(基地机场，是网络的汇或收点），用终 止边将叶节点和所有到达机场是基地/过夜机场的空运航班节线连接到终止机场节点， 然后在每条空运航班节线的空运航班边上标注飞行时间，在每条衔接边上标注衔接(过站） 时间，这样就形成了空运航班连接网络。
（6）从基地机场节点开始，采用宽度优先或深度优先搜索或混合搜索的方法。 搜索空运航班连接网络的每一条路经，每条路经都是一个空运航班串。在搜索过程中不断 紧加路径上的飞行时间和值勤时间（飞行时间再加上过站时间是值勤时回，翻器 到某节点处，飞行时间或执勤时间已违反了适航规定，就放弃该路径。最后得到的 是符合适航规定的可行空运航班串，其中终止在基地机场的就是由一条空运航班串构成的 空运航班环。
（7）对于最后终止在过夜机场的空运航班串，再把第二天从该过夜机场出发的航 班串与其连接成多天的空运航班串。如果这样新连接的空运航班串最后回到了基地，则得 到一条多天的空运航班环。 试用上述步骤为例53给出的空运航班计划构造机组空运航班环(任务配对)。 解按照本节所给构造步骤。
步骤1该空运航班计划共有9个空运航班，服务四个城市A、B、C、D，将9个空运航班按 照这四个机场的出发空运航班进行分割，即 步骤2构造基地机场A的出发空运航班树如，构造其他机场的出发 空运航班。 步骤3对于空运航班0、1和6，分别连接机场B、D、B的出发空运航班，并判断出空运航班 3和5不能衔接空运航班6，删除这两个空运航班节线，然后再分裂相应的空运航班节点 步骤4这就是表5-3的空运航班计划的空运航班连 接树，为方便辨认，每条空运航班边上给出了空运航班号。 步骤5增加基地机场终止节点，连接生成空运航班连接网络。对空运航班连接网络的每条空运航班边给出飞行时间，每条衔接边给出过站时间。 步骤6进行深度搜索或宽度搜索，得到该树的每一条路经，结果与的相同，共14条，它们都是可能的空运航班串。该例中每个空运航班串的终止机场都是基 地机场，因此它们又都是空运航班环。搜索过程计算累计飞行时间和过站时间。FT和ET分别表示飞行时间和执勤时间，发现所有空运航班串 《环）都符合类于懂勤期时间的适航规定，如果公司对值勤期的空运航班数无规定，则 14个空运航班环都是可行的。 需要注意的是，各空运航班环质量可能不同。例如，表5-4中的S、S与S、S. 相比，飞行时间短了，但执勤时间更长了。因为飞行员的生产力体现在空中飞行，而不是待在地面。飞行时间短而执勤时间长就意味着空运航班串的质量低。
可以用飞行时间与执勤时间的比刀来表示空运航班环的质量，称为机组工作效率，比值 越大越好。本例的空运航班环质量已列在最后一行。可以按照刀从大到小给 航语环排序，当7相同时，以飞行时间从大到小排序，那么排在前面的是质量需的 空运航班环。
