机组排班优化

    经过5.5.1节和5.5.2节的研究工作，已经获得了符合各项规定的活动事和 机组，现在的任务是将这两者进行指派。假设有n个活动串和n个机组，并且已经征求了每个机组的意愿，了解了他们最希望执行的活动串和最不希望执行的活动串，并将其他的看作“无所谓”的活动串。 

    设对于最希望的活动串的指派满意度为10，最不希望的活动串的满意度为1， 其他活动串的满意度为6。再考虑资格因素，在满意度前乘以1~2的资格因子。 对活动串和机组分别进行编号，用下标i=1，2，…，n，j=1，2，…，n表示。以总体 满意度最大为目标函数，建立活动串指派模型为 式中，p，是将机组i指派到活动串j的满意度(已乘以资格因子)；x，是指派决策 变量，把机组i指派给活动串j时等于1，否则等于0。

     模型（5-25）的求解并不困难，可以首先用20减去满意度矩阵p，的每一个元 素，得 模型（5-26）与模型（5-25）同解，然后用匈牙利算法求解。但当n很大时，如 n1000时，匈牙利算法仍然需要较长时间。可以首先根据上一周期的指派结果， 对保留的机组，让它们仍执行原来的航线（航班环)，或首先满足一些老资格机长的 愿望，然后对剩下的部分建立模型，再采用匈牙利算法求解。 也可以首先根据机组排班的水平规则构建活动串，进行优化选择。然后将机 组的组配与活动串的指派同时进行。也就是不首先组配机组，机长和副驾驶都直 接参与指派。方法是将垂直规则表达成约束条件，附加到基本指派问题模型中。 与上述基本指派问题建模方法一样，让活动串作为指派矩阵的列，每位飞行员作为 指派矩阵的行，垂直规则可按如下形式表达为附加约束条件。 

     (1)飞行员对活动串执行意愿的约束。将活动串集合按照飞行员i的意愿划 分成子集R（），加果各飞行员的意照于集尽）不交，则对每位飞行员有 8.如果子集尽(D存在交集，则对每条活动串，将可以执行它的飞行员划分 成子集C（G），对每条活动电有 

   （3）对于多人机组，如双机长和三人机组，可以增加如下约束条件： 式中，RosterAdd是需要多人机组执行的活动串子集，一般情况下c=3 

   （4），对于资格型约束，如机组中跟班学员不能超过一人。设可以安排眼班学 员的活动串子集为NewR，则对跟班学员子集NwCrew增加约束： 

   （5）两位飞行员必须一起值班，构成相容约束。设飞行员i和k必须一起值 勤，令CrewComp是必须一起值勤的飞行员对的集合，将飞行员i执行的活动串集 复制给他的同事k，增加约束： （6)如果两位飞行员、k不能一起值勤，则构成不相容约束。设不相容的飞 行员对的集合是Crewlncomp，与上述相容约束正好相反，有 这样可构建成扩展的活动串指派问题的数学模型，即 求解式(5-27）后即可完成活动串指派和机组的组配。

    但这样的解决方法使 问题更复杂了，求解难度更大。 美国在完成构建和优选活动串后，并不进行指派，而是让飞行员竞拍，称为 Bidline。这种方法可能导致某些活动串流拍。这种情况下，公司将不得不增加这 些活动串的优惠条件，吸引飞行员接受这些活动串。 例5-7对例5-6选出的5条活动串（表5-11），如果航空公司有该机型的机 长8人，其中新机长2人，但有1人已飞行超过300h，教员1人，一类副驾驶5人， 二类副驾驶2人，跟班学员4人，请为这5条活动串指派机组。 解首先组配机组，机组数应大于等于5。根据适航规定，跟班学员必须有教 员当机长时，才能在右座实习，对于不满30h的新机长必须实行双机长制，机长不 能和二类副驾驶搭配。

     对这19名飞行员编号：1位教员编号为1，5名老机长编号 为2~6，2位新机长编号为7和8，一类副驾驶编号为9～13，2名二类副驾驶编号 为14和15，4名跟班学员编号为16、17、18、19。 征求飞行员意愿时规定：只征求机长的意愿；教员、老机长和新机长的活动申 意感可分别填2个、3个、4个，新机长不能填写最不希望的活动串；教员不能不愿 意与跟班学员搭配。8名机长的意愿如表5-13所示。表中未填写者为“无所谓”。