空运航班串的基本生成方法

    对于机组排班，核心问题是生成符合适航要求的机组空运航班 环。一条空运航班环可能由一条到多条空运航班串组成，一个空运航班串是若干个空运航班根据时 间和空间的先后顺序连接而成的。如果一条空运航班串的起点和终点都是基地，生成 的空运航班串即空运航班环，此时的空运航班环只有一条空运航班串。如果一条空运航班串的最后一个 空运航班未能回到基地，那么机组将在外场过夜，执行第二个空运航班串。

    如果第二个空运航班 串的最后一个空运航班回到基地，那么一条空运航班环有两条空运航班串；如果第二天还不能回 到基地过夜，则机组将在外场二次过夜，第三天执行第三条空运航班串。如果第三条航 班串的最后一个空运航班回到基地，则一条空运航班环有三条空运航班串，等等。一般地，很少 采用三条以上空运航班串构成的空运航班环。因为这样的空运航班环不仅质量不高，而且成本 较高；机组在外场过夜次数多，将影响机组的执行意愿。 

    下面首先讨论生成空运航班串的方法。为生成空运航班串，可采用时空网络或空运航班连 接网络。某空运航班计划构成的时空网络，有四个机场(A、B、C、D)和15个航 班，C是基地机场。其中，fi表示在此时间段上最早的一个空运航班，从C（基地）出发， 到达机场A。fs的出发机场与fi的到达机场相同，同时满足时间上衔接的要求， 因此f；与fs可连接成一个可行的机组任务(即空运航班串)。另外，fa、f7、fi可连接成 另一个可行机组任务，等等，以此方式将所有空运航班连接成若干个可行机组空运航班串。 空运航班串S1、S2、Ss、S4、S。涵盖所有15个空运航班，是一组可行的机组任务。这些空运航班串的最后一个空运航班都回到了 基地，因此都是一条空运航班串的空运航班环。 在航空货代公司，空运航班环简单地用城市简称序列表示，如宁一深一琼一深一宁，也 可用机场三字代码表示，如NKG-SZX-HAK-SZX-NKG。 另外一种生成空运航班串的方法是采用空运航班连接网络。空运航班连接网络是一种有向 网络，其中节点表示空运航班，有向边表示前后两个空运航班的衔接。

如果两个空运航班满足以 下条件：

    ①前一空运航班的到达城市是后一空运航班的出发城市；

    ②两个空运航班的衔接时间不 

    短于最小衔接时间，那么这两空运航班节点用有向边连接，方向从前一个空运航班节点指向 后一个空运航班节点。 空运航班连接网络以基地机场为发点和收点(或称源和汇)。如果航空公司只有一 个基地机场，它将是单发点单收点的网络图。对于多基地航空公司，它是一个多发 点多收点的网络图。此时，可以将各基地机场分开，用它们的始发空运航班单独构造航 班连接网络，构成多个单发节点单收节点网络图。 找空运航班串就是在空运航班连接网络中搜索从发点到收点的一条路径。这条路径总 飞行时间不超过适航条例规定的一个值勤期中的飞行小时数，总出勤时间不超过 适航条例要求的一个值勤期的执勤小时数。 例5-3表5-3是一种机型执行的支线空运航班计划，空运航班号用0、1、2.…表示，共9 个空运航班，服务4个城市A、B、C、D，其中A是基地机场。机组最短衔接时间规定为 30min,试用空运航班连接网络求出它的可行空运航班串(空运航班环）。 上述空运航班计划9个空运航班连接成了14个空运航班串，通常可行的空运航班串数远远超过 空运航班数，如果该网络中某些节点的“度”很大(如在枢纽机场连接的空运航班)，那么这些 空运航班可衔接的后继空运航班相当多，可生成的空运航班串将是海量的。 

    对于一个机组空运航班串，除执勤小时数和飞行小时数不能违规外，空运航班串的长度 也有限制，如不能超过6个空运航班，此时并不是所有的路径都是可行的空运航班串。假设 航空公司限制一个机组一天最多执行4个空运航班，那么上述的空运航班串S，和S。就是 不可行的。