信息技术与应用 Ｃｈｉｎａ Ｓｃｉｅｎｃｅ＆Ｔｅｃｈｎｏｌｏｇｙ Ｏｖｅｒｖｉｅｗ 不确定环境下机组调度问题的规划模型及算法 张培 （中国民航大学理学院，天津３００３００） 【摘要】传统航空公司机组调度模型大多是确定的，然而实际上航班通常会受各种不确定因素影响而产生延误的影响。本文考虑随机因素，将 机组排班的配对寻优建成以成本最小和旅客满意度最大为目标的多目标随机机会约束规划模型，并构造混合智能算法来寻找最优解。案例研究的结 果显示，模型和算法对于实际中机组配对的寻优是可行的。 【关键词ｌ机组配对不确定多目标机会约束规划混合遗传算法 ［Ａｂｓｔｒａｃｔ］Ｆｏｒ ｔｈｅ ｔｒａｄｉｔｉｏｎａｌ ａｉｒｌｉｎｅｓ。ｃｒｅｗ ｓｃｈｅｄｕｌｉｎｇ ｍｏｄｅｌｓ ａｒｅ ｕｓｕａｌｌｙ ｄｅｔｅｒｍｉｎｉｓｔｉｃ，ｉｎ ｆａｃｔ ｔｈｅ ｎｉｇｈｔ ｉｓ ｕｓｕａｌｌｙ ａｆｆｅｃｔｅｄ ｂｙ ｍａｎｙ ｕｎｃｅｒｔａｉｎ ｆａｃｔｏｒｓ ａｎｄ ｃａｕｓｅ ｄｅｌａｙｓ．Ｔｈｉｓ ｐａｐｅｒ ｔａｋｅ ｔｈｅ ｕｎｃｅｒｔａｉｎ ｆａｃｔｏｒｓ ｉｎｔｏ ｃｏｎｓｉｄｅｒａｔｉｏｎ ｔｏ ｂｕｉｌｄ ａ ｍｕｌｔｉ—ｏｂｊｅｃｔｉｖｅ ｓｔｏｃｈａｓｔｉｃ ｃｈａｎｃｅ ｃｏｎｓｔｒａｉｎｅｄ ｐｒｏｇｒａｍｍｉｎｇ ＣｒｅＷ ｐａｉｒｉｎｇｓ ｍｏｄｅｌ ｏｆｍｉｉｎｍｕｍ ＣＯＳｔ ａｎｄｍａｘｉｍｕｍ ｐａｓｓｅｎｇｅｒ ｓａｔｉｓｆａｃｔｉｏｎ，ａｎｄ ｃｏｎｓｔｒｕｃｔｓ ａ ｈｙｂｒｉｄｉｎｔｅｌｌｉｇｅｎｔ ａｌｇｏｒｉｔｈｍ ｔｏ ｆｉｎｄ ｔｈｅ ｏｐｔｉｍａｌ ｓｏｌｕｔｉｏｎ．ｔｈｅ ｒｅｍｉｓｔ ｏｆａ ｃａｇｅ ｓｍａｙ ｓｈｏｗ ｔｈａｔ ｔｈｅ ｍｏｄｅｌ ａｎｄ ａｌｇｏｒｉｔｈｍ ａｒｅ ｆｅａｓｉｂｌｅ ｉｎ ｐｒａｃｔｉｃｅ ｆｏｒ ｃｒｅｗ ｓｃｈｅｄｕｌｉｎｇ ｐｒｏｂｌｅｍｓ． ［Ｋｅｙ ｗｏｒｄｓ］ｃｒｅｗ ｐａｉｉｒｎｇｓ ｐｒｏｂｌｅｍｓ；ｕｎｃｅｒｔａｉｎｔｙ；ｍｕｌｉｔ—ｏｂｊｅｃｉｔｖｅ；ｃｈａｎｃｅ ｃｏｎｓｔｒａｉｎｅｄ ｐｒｏｇｒａｍｍｉｎｇ；ｈｙｂｒｉｄ ｉｎｔｅｌｌｉｇｅｎｔ ａｌｇｏｒｉｈｔｍ １引言 作为单目标规划的推广，多目标规划定义为在一组约束条件 由于民航业的特点和竞争的需要，航空公司的航班运行控制对 下，优化多个不同的目标函数，其一般形式为： 运筹学的许多分支理论和方法，特别是最优化技术有着非常迫切的 需求。航空公司计划和控制系统是围绕航班来运作的，运行控制部门 通过使用辅助决策系统和利用各种现代优化技术建立符合实际问题 ｆｍａｘ［￣（ ）， （ ），．．．， （ｘ）］的调度模型，采用有效的算法、软件来实现调度方案的快速生成。 ｊ ． 在国内外的文献中，Ｌｏ０Ｉ 殖过重新定义航班降落时间，建立一 Ｉ ｇ （ ）≤ｏ√＝１…２…Ｐ， 个用多目标遗传算法，（ＭＯＧＡ）来解决的多目标优化的模型。文献【２】 其中 ＝（Ｘ１ ，．．．，Ｘｎ） 是一个，ｚ 维决策向量， 则引入一个惩罚函数，模拟实际运营成本来进行不确定环境下的机 组调度问题研究。张英楠等人ｆ３ 引入机会约束构建兼顾成本与航班 （ ）（ １，２，．．．， ）是目标函数，ｇ （ ） ０（ｙ＝１，２…．，ｐ）是系统 运行安全及旅客随机需求的机型分配与机组排班模型。牟德一等人 约束条件 提出机组延误概率这一概念，给出机组延误概率计算公式及方法， 利用Ｍａ廿ａｂ编程计算机组配对相关问题。Ｙｅｎ［ 】一方面解决人员指 ４问题描述与基本方法 派问题，另一方面加入惩罚函数来描述延误。文献［６脱明了确定性 ４．１问题描述 航班机组调度的综合论述。 机组调度的问题是航空公司制定航班计划表的一个重要组成 本文在考虑基本的机组配对基础上，考虑实际运营情况，考虑 部分。在机型分配结束后，为每个机型的飞机配备相应的机组人员 一个不确定环境下的的随机变量。在航班约束以及机会成本约束条 来保证航班的飞行计划。为每个机型寻找合适正确的机组不仅能提 件下，建成多目标机会约束模型，利用混合智能算法求解并结合案 高飞行效率节约成本，在飞行安全方面也有一定的保障。 例加以实现。 机组调度问题分为两个部分：机组配对和机组轮班。机组配对 ２随机机会约束规划 是寻找适合的机组，机组轮班是配对以后，将具体的机组人员分配 定义［８】：假设ｘ是一个决策向量，｛是一个随机向量，ｒ（ｘ、ｆ）是 到配对中。在实际航空公司运营中，为一个机组配备相关的人员很 容易操作，而机组配对的过程很复杂，涉及到机场、城市、基地等等 目标函数，ｇ ｘ， ）（ｊ＝１，２，…，ｐ）是没有给出确定可行集的随机 限制规则，所以本文重点研究机组配对。 约束函数。一个点ｘ 是可行的当且仅当事件 ４．２机组配对的一般要求 （１）公司排班人员根据计划时刻表来对航班进行合理配对； 括Ｉ ｇｊ ， ） ０， ＝１，２，…，ｐ｝的概率测度不小于 ，即违反约束 （２）每个配对开始是从基地出发，结束则回到基地， （３）每个配对所安排的航班尽量能在一天内执行完毕以节省机 条件的概率小于（１一口），机会约束可以表示为如下的形式： 组在外费用； ｘ，ｆ）≤０，．， ｌ，２，．．．，ｐ｝≥ （４）为机组人员分配合理的航线。 ３多目标规划 ５不确定环境下机组配对的机会约束多目标规划模型与算法 表１ Ｂ７５７—２００机型的航线调配 航班号 始发地 起飞时间 目的地 到达时间 ｌ０５ ＳＦ０ ０９：５０ ＪＦＫ １５：２０ １１０ ＡＴＬ ０８：１０ ＪＦＫ １０：４０ ｌ１ｌ ＡＴＬ １３：１０ ＪＦＫ ｌ５：４０ １１３ ＭＩＡ ０９：１０ ＪＦＫ １２：１０ １１４ ＭＩＡ １４：３０ ＪＦＫ １７：３０ １ｌ８ Ｂ０Ｓ １５：Ｏ０ ＪＦＫ １６：３０ １２５ ＪＦＫ ０７：２５ ＳＦＯ ０９：５５ ｌ３ｌ ＪＦＫ ０９：３０ ＡＴＬ １２：Ｏ０ １３３ ＪＦＫ １８：０５ ＡＴＬ ２０：３５ ｌ３５ ＪＦＫ ｌ５：１０ ＭＩＡ １８：１０ １３６ ＪＦＫ ｌ８：１０ ＭＩＡ ２１：１０ ｌ３８ ＪＦＫ ｌ２：３０ Ｂ０Ｓ １４：Ｏ０ 作者简介：张培（１９９４一），男，河南省商丘人，学历：本科。工作单位：中国民航大学。 １４ ２０１５年６月下第１２期总第２１６期 信息技术与应用 表２ Ｂ７５７—２００机队的２８个合法机组配对 机组配对序号 ｌ ２ ３ １２５ １３ｌ １３１ 第一天的航班 第二天的航班 ｌ０５ ｌ１Ｏ ｌ１ｌ 飞行时间 １ｌ ５ ５ ４ ５ ６ ７ ８ ９ １３１ ｌ３３ １３３ ｌ３３ ｌ３５ ｌ３５ １ １０—１３８—１ １８ ｌ１０ ｌ１ｌ ｌ １０—１３８—１ １８ ｌ１３ １１４ ８ ５ ５ ８ ６ ６ 一 ｌＯ １１ ｌ２ １３５ １３６ １３６ １ ｌ３—１３８—１ １８ １１３ ｌ１４ ９ ６ ６ １３ １４ １５ １６ ～ １３６ １３８ ｌ３１—１１１ １３１一ｌ １ ｌ—ｌ３３ ｌ ｌ３一ｌ３８一ｌ ｌ８ ｌ１８ ９ ３ ５ 一 ｌ７ １８ １９ ２０ １１０ １０ ｌ３ｌ一１１１—１３３ １３１一ｌ１１—１３３ ｌ３ｌ一１１１一ｌ３６ １３１—１１ｌ一１３６ ｌ３１一ｌｌｌ—ｌ３６ １３８—１１８ １３８一ｌ １８一ｌ３３ ｌ１１ １ １０一ｌ３８—１ １８ ｌ１３ １１４ ｌｌ３一ｌ３８一ｌｌ８ １０ ｌ３ ｌｌ ｌ１ １４ ３ 一 一 ２２ ２３ ２１ １１０ ８ ２４ ２．５ ２６ ２７ ２８ ｌ３８—１ １８一ｌ３３ ｌ３８—１ １８一ｌ３３ ｌ３８一ｌ １８一ｌ３６ ｌ３８—１ １８—１３６ ｌ３８—１ １８—１３６ ｌ１１ １ １０—１３８—１ １８ ｌ１３ ｌ１４ １ １３一ｌ３８—１ ｌ８ ８ １１ ９ ９ ｌ２ 表３ Ｂ７５７—２００机型的航班旅客可接受的降落时间窗 始发地 ＳＦＯ ＡＴＬ ＡＴＬ ＭＩＡ ＭＩＡ ＢＯＳ ＪＦＫ ＪＦＫ ＪＦＫ ＪＦＫ ＪＦＫ ＪＦＫ 目的地 ＪＦＫ ＪＦＫ ＪＦＫ ＪＦＫ ＪＦＫ ＪＦＫ ＳＦＯ ＡＴＬ ＡＴＬ ＭＩＡ ＭＩＡ ＢＯＳ 时间窗 ｎ４：５Ｏ，ｌ５：５ｏ】 ［１０：１０，１１：１Ｏ】 ［１５：ｌ０，ｌ６：１ ｏ】 ［１２：４０，１１：４Ｏ】 ［１７：００，１８：ｏｏ］ ［１６：０Ｏ，１７：ｏｏ］ ［０９：２５，１０：２５】 ［１ｌ：３０，１２：ｏｏ］ ［２０：Ｏ５，２１：Ｏ５】 ［１７：４０，１８：４０】 【２Ｏ：４Ｏ，２１：４ｏ】 ［１３：３０，１４：３Ｏ１ １ １ １０ １２ 表４ Ｂ７５７—２００机组配对的解 方案 配对序号 总成本 １２ ９０．２％ 航班号 ｌＯ５ １１０ ｌ１ｌ ｌｌ３ １ｌ４ ｌ１８ １２５ １３１ ｌ３３ ｌ３５ １３６ １３８ 旅客满意度 １６ ２ １ ８ ２０ １２ ９５．１％ ２３ ３ １ ５ ９ ｌ２ ９２．６％ ２ｌ 表５ Ｂ７５７—２００机组配对的最优解 航班号 配对１ 城市对 起降时间 配对８ 城市对 起降时间 配对２Ｏ 城市对 起降时间 配对２３ 城市对 起降时间 第一天 航班１２５ ＪＦＫ—ＳＦ０ ０７：２５－０９：５５ 航班１３５ ＪＦＫ—ＭＩＡ １５：１０—１８：ｌ０ 航班１３ｌ ＪＦＫ—ＡＴＬ ０９：３０一ｌ２：００ 航班１３８ ＪＦＫ—ＢＯＳ １２：３０－１４：００ 第二天 航班１０５ ＳＦＯ—ＪＦＫ ０９：５Ｏ一１８：２Ｏ 航班１１３ ＭＩＡ—ＪＦＫ ０９：１０—１２：１０ 航班ｌ１４ ＭＩＡ—ＪＦＫ ｌ４：３Ｏ—ｌ７：３０ 航班１ｌ０ ＡＴＬ—ＪＦＫ ０８：１Ｏ一１０：４０ 航班ｌ１１ ＡＴＬ—ＪＦＫ １３：ｌ０—１５：４０ 航班ｌ１８ ＢＯＳ—ＪＦＫ １５：０Ｏ一１６：３０ 航班１３６ ＪＦＫ—ＭＩＡ ｌ８：１０—２１：１０ 航班１３３ ＪＦＫ—ＡＴＬ １８：Ｏ５—２０：３５ 一本文将航班进港时间设随机变量，将总成本和顾客满意度作为 个随机机会约束。 ５．１．１符号约定 ５．１模型建立 本文涉及的上、下标、参数、集合以及变量的实际意义，其中时 间的计量单位是分钟，成本的计量单位是元。 ２Ｏｌ ５年６月下第１２期总第２１６期 １５ 信息技术与应用 Ｃｌｌｉｎａ Ｓｃｉｅｎｃｅ＆Ｔｅｃｈｎｏｌｏｇｙ Ｏｖｅｒｖｉｅｗ 上标和下标变量： ｊ＝配对下标变量； ｉ＝航班下标变量。 集合： Ｆ：航班集合； Ｐ：可行配对集合； Ｋ：机组常驻基地集合； 参数： 我们利用 航空公司运营规划与管理》书中Ｂ７５７—２００机队的机 组配对来进行案例分析。表１为该机型所有的航班调配。根据Ｕｌｔｉ－ ｍａｔｅ Ａｉｒ公司对机组配对的要求（每个飞行出勤不能超过８小时；一 ～∑ 个调配安排的最长时间为两天；机组的常驻基地是ＪＦＫ机场，等待衔 接时间的上下限分别为ｌＯＳａｖ钟和３小时。），我们可以生成２８合法机组 配对，即表２。 ＝ 航班延误是指航班降落时间比计划降落时间 班时刻表上的 ， （ａｉ，ｊ￣ ， ）：配蹦航班ｉ，旅客可容忍的进港时间窗； ∑ 时间）延迟３ｏ＃＊０以上或航班取消的情况。所以我们定义顾客可接受 的进港时间窗为计划降落时间前后三十分钟，即表３。 ∑ 假设在旅客可接受的时间窗口内航班降落的置信水平为９０％， ｐ ｃ，：机组配对ｊ的成本； ：常驻地城市可ｋ用最少机组数量； ：常驻地城市可ｋ用最多机组数量； ａ¨：航班ｉ由配对ｊ负责则为１；否则为０； ．，：配对ｊ的常驻地基地是城市ｋ则为１；否则为０． 决策变量 ，：如果配对．是解的一部分则为１；否则为０。 ５．１．２目标函数和约束条件 目标函数：航班晚点延误等的频繁发生会引起旅客满意度的下 降。因此，综合航空公司飞行成本和旅客的满意度，本模型将航班总 成本和顾客满意度作为目标函数。 由此，模型的目标函数可以写成下式： ｍｉｎ Ｉ∑ｃ， ，∑∑ ，１ Ｌ Ｊ ｐ Ｅ Ｐ ｉＥＦ Ｊ 本模型共有２组约束条件： 约束一：航班到港时间在旅客可接受的时间范围内。 航班计划的固定性与随机扰乱因素相互作用，导致了航班延 误。在每个航班对每个航班中，我们希望旅客以置信度水平 在其 可容忍的时间窗口内进港，于是机会约束为： Ｐ ，∈ａ．． ｂ ）｝ ≥１３ ， 约束二：航班覆盖。 每个机组配对候选方案均覆盖了一定的航班数量，我们必须保 证每个航班仅被覆盖一次。 ∑ａ ，＝１ ＪＥＰ 例如，航班１１４在配对９、１２、２０和２７中出现，因此要覆盖这个航 班则有： ＋ ２＋ ２ｏ＋Ｘ２７＝ｌ 同理，所有航班ｉ均可表达为上述形式。 ５．１．３不确定环境下机会约束规划模型 根据上节的分析，得到如下模型： ｂ 曼２一ｈ ｋｌｊｘｉ２ ｂ ｋ ． Ｐ “∈Ｆ，Ｊ∈Ｐ，ｋ∈ ） ５．２模型分析与混合智能算法 本模型是在基于整数规划中，加入了随机机会约束。模型有两 个目标函数，模型混合智能算法的步骤如下： 步骤一：根据机组配对的规则和过滤条件得到所有的合法机组 配对； 步骤二：根据航班起飞降落时刻、机型、乘客等等，确定模型参 数和集合的取值范围， 步骤三：通过约束二确定航班的覆盖范围； 步骤四：利用混合智能算法来模拟输入输出数据，训练神经元 等来实现约束一。 本模型的步骤三和步骤四的求解均由Ｍａｔｌａｂ编程实现。 ６案例分析 １６ ２０１ ５－ｇ６￣下第１２期总第２１６期 即有机会约束：＿Ｐ ，ｅ ，白 ， ≥ｎ９０ 同时，１２航班全部覆盖且仅被覆盖一次，则有约束： ∑ ｝Ｅ Ｐ ＝＝ｌ 我们在上述两约束条件下极小化总成本，极大化顾客满意度。 利用｝昆合智能算法求解最优值。 算法步骤： 步骤１用随机模拟技术为机会约束不确定函数产生输入输出数 据，（ ： 寸ｖ｛Ｌ，∈（ｑ ， ，）｝＝ ，，≥ｏ．９０ 步骤２根据产生的输入输出数据来训练一个神经元网络逼近 不确定函数。 步骤３初始化ｐＯｐ Ｓｉｚｅ个染色体，并利用训练好的神经元网络检 验染色体的可行性。 步骤４通过交叉好变异操作更新染色体，并利用训练好的神经 元网络计算所有染色体的目标值。 步骤５根据目标值计算每个染色体的适应度。 步骤６通过旋转赌轮选择染色体。 步骤７重复步骤４到步骤７直到完成给定的循环次数。 步骤８给出最好的染色体作为最优解。 首先利用随机模拟为不确定函数Ｕ产生输入输出函数，根据训 练样本，我们训练一个神经元网络来逼近不确定函数 。然后，我们 把训练好的神经元网络嵌入遗传算法产生｝昆合智能算法。 通过运行混合智能算法，我们得到表４。 在总成本均为１２的情况下，我们选择旅客满意度最高的方案２， 即表５为最优解： ７结语 本文是在不确定环境下，将机组排班的寻优建成以成本最小和旅 客满意度最大为目标的多目标机会约束规划模型，并采用混合智能算 法来寻找最优解。在保证最小成本下，使旅客在可接受的时间窗内降 落机场。在航班所有可行机组配对后，利用Ｍ 程求解，得到最优 解。案例表明，该模型和算法对于实际中机组配对的寻优是可行的。 参考文献 ［１ １Ｌｏｏ Ｈ．。Ｃｈｕｌ Ｕ．。Ａ ｍｕｌｔｉ—ｏｂｊｅｃｔｉｖｅ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｒｏ— ｂｕｓｔ ｆｌｉｇｈｔ ｓｃｈｅｄｕｌｉｎｇ ｕｓｉｎｇ ｓｉｍｕｌａｔｉｏｎ［Ｈ］，ＳｃｉｅｎｃｅＤｉｒｅｃｔ，２００７． ［２］Ｓｃｈａｅｆｅｒ Ａ Ｊ。Ｊｏｈｎｓｏｎ Ｅ Ｊ，Ｋｌｅｙｗｅｇｔ Ａ Ｊ，ｅｔ ａ１．Ａｉｒｌｉｎｅ ｃｒｅｗ ｓｃｈｅｄｕｌｉｎｇ ｕｎｄｅｒ ｕｎｃｅｒｔａｉｎｔｙ［Ｊ］．丁ｒａｎｓｐｏｒｔａｔ１ｏｎ Ｓｃｉｅｎｃｅ，２００５， ３９（３）：２１ ０－２２３． ［３］张英楠，牟德一，李辉．基于机会约束规划的航班应急调度问题研 究［Ｊ］．中国安全科学学报，２０１ ２． ［４］牟德一。王志新，夏群．基于机组延误概率的鲁棒性机组配对问题 ［Ｊ］．系统管理学报，２Ｏ１ １，２０（２）：２０７－２１２． ［５］Ｙｅｎ ０。Ｂｉｒｇｅ Ｊ，Ａ ｓｔｏｃｈａｓｔｉｃ ｐｒｏｇｒａｍｉｎｇ ａｐｐｒｏａｃｈ ｔｏ ｔｈｅ ａｉｒ— ｌｉｎｅ ｃｒｅｗ ｓｃｈｅｄｕｌｉｎｇ ｐｒｏｂｌｅｍ［Ｄ］．Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｗａｓｈｉｎｇｔｏｎ，２０００． ［６］Ｂａｒｎｈａｒｔ，Ｃ．Ａ．Ｃｏｈｎ，Ｅ．Ｌ．Ｊｏｈｎｓｏｎ，Ｄ．Ｋｌａｂｊａｎ，Ｇ．Ｌ．Ｎｅｍｈａｕｓｅｒ，Ｐ．Ｈ． Ｖａｎｃｅ．Ａｉｒｌｉｎｅ ｃｒｅｗ ｓｃｈｅｄｕｌｉｎｇ［Ｍ］．Ｒ．Ｍ．Ｈａｌｌ，ｅｄ．Ｈａｎｄ ｂｏｏｋ ｉｎ ｔｒａｎｓ－ ｐｏｒｔａｔｉｏｎ Ｓｃｉｅｎｃｅ。Ｋｌｕｗｅｒ Ｓｃｉｅｎｔｉｆｉｃ Ｐｕｂｌｉｓｈｅｒｓ，２００２：５１ ７－５６０． ［７］Ｃｈａｒｎｅｓ Ａ，Ｃｏｏｐｅｒ Ｗ．Ｃｈａｎｃｅ—ｃｏｎｓｔｒａｉｎｅｄ ｐｒｏｇｒａｍｍｉｎｇ［Ｊ］．Ｍａｎ— ａｇｅｍｅｎｔ Ｓｃｉｅｎｃｅ，１９５９，６（１）：７３—７９． ［８］刘宝碇，赵瑞清。王纲．不确定规划及应用［Ｍ］．北京：清华大学出版 社。２００３． ［９］彭锦，刘保碇，不确定规划的研究现状及其发展前景［Ｊ］．运筹于管 理。２００２，１ １（２）：１—１ Ｏ． ［１ ０］杨立兴．不确定环境中的指派问题及其混合智能算法［Ｄ］．保定： 河北大学。２００２． ［１１］马苏德一巴扎尔甘（美）．航空公司运营规划与管理［Ｈ］．邵龙。王美 佳。译．北京：中国民航出版社，２００６：３９—５６，８ｌ一９１．