基于多因素分析的机场任务指派建模与仿真.pdf

书书书第 卷第 期运 筹 与 管 理 ，年 月 收稿日期：基金项目：国家自然科学基金资助项目（，）；湖北省教育厅科学研究计划项目（）；湖北省高等学校优秀中青年科技创新团队计划项目（）；河南省高校重点科研项目（）作者简介：田倩南（），女，河南驻马店人，博士研究生，副教授，研究方向：调度优化；李杰（），河北邯郸人，男，博士研究生，研究方向：调度优化；李昆鹏（），通讯作者，男，湖北武汉人，博士，教授，研究方向：生产运作管理；郭群（），女，黑龙江哈尔滨人，博士研究生，讲师，研究方向：技术创新。基于多因素分析的机场任务指派建模与仿真田倩南，李 杰，李昆鹏，郭 群，（湖北经济学院 湖北物流发展研究中心，湖北 武汉 ；湖北经济学院 湖北企业文化研究中心，湖北 武汉 华中科技大学 管理学院，湖北 武汉 ）摘要：机场任务指派问题是一个复杂的组合优化问题，属于 问题。本文研究了考虑任务部分覆盖率、资格匹配度等多因素的指派问题，通过分析研究问题，建立整数规划模型，对模型进行分析并提出有效不等式，应用 优化软件对不同因素的实际数据进行仿真测试，数值实验结果表明：）该模型的可行性与有效性；）对不同规模的实际数据求解发现，即使覆盖率设置高达 ，目标函数的均值依然提高 ；当同时考虑资格匹配度时，目标函数均值也能提高 ；）对考虑不同属性因素数据的测试结果对比发现，降低任务对资格的要求对目标函数产生的影响最大，目标函数均值增加量高达 ，从而对任务完成率影响更直观。研究可以有效提高机场的运行效率和任务完成率，为企业实际运营决策提供科学依据。关键词：任务部分覆盖率；问题；整数规划模型；优化软件中图分类号：文章标识码：文章编号：（）：，（，；，；，）：，“”“”，：，：；引言据国际航空运输协会的数据，年全球航空业的旅客总量为 亿人次，相比 年增长 。和其他运输行业对比发现，航空运输在速度、效率、覆盖范围等方面具有明显优势。另外机场正常运行是航班计划实施的前提 。机场地面服务工作包含了很多方面，比如，咨询服务、检票进站等。在以往的研究中，任务与班次之间在满足其他约束的基础上，时间约束也要求完全满足才能被指派，然而随着淡旺季不同以及临时突发状态的发生，就会出现在某一段时间内机场的任务量剧增，而人员严重不足的情况，这时如果还是考虑任务的初始时长被完全覆盖，将会导致大量任务无法被指派给班次，降低班次的利用率。在实际情况中，机场任务是允许在任务持续时间内较早或较晚开始的，只要工作时长满足部分覆盖率的要求，那么任务允许在班次加急的情况下被完全执行。另外，从任务和班次都具有多种属性中可以发现，安排与任务资格熟练程度要求相近的班次去执行相应的任务可以有效避免资源浪费，这也是现在越来越多机场在解决任务指派问题时注重的方面。表 分别给出了五个任务和二个班次的各种属性，当一个任务被班次所完成时会产生相应的效益（任务的结束时间 任务的开始时间）优先级）。任务与班次之间要满足约束要求才能进行指派，比如：在表中任务，任务时长为 ，任务 对资格的要求为 和熟练程度要求为 ；而对于班次，其资格集合为 ，熟练程度分别为 ，。表 中，的开始和结束时间包含在班次 的工作时间内，但是 的结束时间和 的开始时间有冲突不能依次指派给，因此只能，依次分配给，获得效益 ；如果考虑部分覆盖率（），可以依次指派给（在规定时间内，连续完成时长不低于部分覆盖率），则产生效益是 。运 筹 与 管 理 年第 卷表 有五个任务和二个班次的指派问题任务 班次编号类型开始时间结束时间优先级资格要求熟练程度 机场任务指派问题属于 的组合优化问题，随着任务与班次数量的增加，问题规模会变的很大，特别是变量数量，呈指数增加。现有文献关于机场任务指派问题的研究较少，大多研究集中在行李运输调度 ，、跑道调度 以及进离港航班排序优化问题上 ，只有少量文献研究机场任务指派问题，而机场任务指派问题中任务和班次具有多种特征，约束条 件多，模型 结 构 复杂。和 针对机场地勤员工排班问题进行研究，建立了弹性排班模型，该模型的目标函数是最小化加班员工人数。等 提出了不同研究目标，最大化机场地勤员工利用率，建立整数规划模型，采 用 列 生 成 算 法 对 问 题 进 行 求 解。等 研究机场人员分配问题，建立排班模型，该模型 分 别 以 班 次 数 和 员 工 数 最 小 化 为 目 标。研究的排班问题考虑了多任务的需求，建立整数规划模型，采用启发式算法对问题进行求解，并在文中对算法的稳定性进行分析对比。付晓薇等 针对非确定性的指派问题，工作数不受限制，但每项工作只能由一人承担的情况进行了研究。对于大规模的算例，等 和 等 分别提出改进的基因算法和大领域搜索方法对大规模问题进行求解。而使用 对整数规划问题求解的研究相对不多，其中，等 虽然使用了 优化软件，但是由于缺乏模型的有效不等式，即使问题的求解规模不大，仍需要花费比较长的求解时间。现有成果为进一步研究基于多因素分析的机场任务指派问题提供了借鉴和思路，由于任务和班次都具有多种属性，该问题在考虑任务产生效益最大化的同时也考虑班次与任务之间的资格精通程度等因素。本文通过分析研究问题的属性，提出多个有效不等式，采用 加有效不等式对考虑不同因素的实际数据进行求解分析，由求解结果可知，机场管理人员可以根据机场类型合理设置不同因素方案，有利于提高机场任务的完成率，从而也有利于提升乘客的满意度。问题描述与数学模型 问题描述设（，）为一个有向图，其中，为节点集，为虚拟任务；（，）：，为边集。，代表任务集合，个数为 ；，代表班次集合，个数为。机场每天的任务量比较大，而班次数量比较有限，每个被指派任务的完成都是由班次中满足要求的地勤人员在一定时间规定内完成的。当一个任务成功指派给一个班次时，那么任务和班次之间一定要满足以下要求：）任务的执行时间包含在班次的工作时间内；）任务的资格包含在班次资格集中，其熟练程度小于等于班次中资格的熟练程度；）不同任务间的距离（用时间表示）必须满足；）班次在执行任务时，不能再指派任务给该班次；）部分覆盖率，在原规定的时间内，任务被连续完成的时长不低于提前设置的值。数学模型建立数学模型用到的变量及解释如下：，：任务 的开始 结束时间；：任务类型；：任务优先级；：任务资格要求；：资格熟练程度要求；，：班次 的开始时间和结束时间；，：班次 拥有的第 个资格，其中，；，：班次 所拥有第 个资格的精通程度，其中，；：任务 和 之间的距离；：，被 执行所获得的效益，即（）（）；，：非负变量，其中，；：较大的实数；：模型中被执行的任务数；：决策变量，其中任务 ，指派给班次 为 ，否则为 。根据以上变量的定义，建立如下整数规划模型：（）（），（，）（）第 期田倩南，等：基于多因素分析的机场任务指派建模与仿真 ，（），（）；，（），；，（），（），；，（），；，（）（，），；，（）（）（）（）；，（）（）（）；，（）（）；，（）：，（）（），（）式（）表示第一目标函数，被执行任务产生效益最大化；式（）表示第二目标函数，最小化任务与班次之间相应资格精通程度差总和；式（）表示当班次开始执行任务时都是从 开始（表示空任务）；式（）表示班次执行的最后一个任务也是 ；式（）表示任务不能被两个及以上班次去完成，最多由一个班次执行；式（）表示流量守恒约束；式（）表示任务不能 被班次 多 次执 行；式（）（）（）表示任务指派给班次时，要满足资格和熟练程度的要求；式（）（）（）表示考虑部分覆盖率的情况；式（）表示如果有两个任务依次指派给同一个班次，后面任务开始执行时间与前一个任务结束执行时间之差要满足两个任务之间的距离要求；式（）表示所有班次执行完成的任务总数量；式（）表示对执行任务班次个数的约束，不能大于总的班次数；式（）表示决策变量的取值范围。模型分析与有效不等式数学模型中包含了两个目标函数（）和（），由于这两个目标的量纲存在一定差距，需要进行归一化处理，归一化处理后得到 （）。其中 和 分别表示任务 ，被班 次执行所产生的最小和最大效益；归一化处理后得到 （，（，）（，）（，）（，）（，）。其中（，）和（，）分别表示相应资格精通程度差的最小值和最大值。然后，对归一化处理后的 和 进行线性加权转化为一个决策目标：（）（）其中效益的权重为，资格精通程度差的权重为，和 取值 ，。约束条件（）表示班次与任务之间不仅要满足资格要求，还需要满足资格熟练程度的要求。为了避免资源浪费，即本文的另外一个目标，当任务与班次互相指派时，尽量使其熟练程度相近，即式（）可以由原不等式改变为有效不等式（）：，（），；，（）其中，根据班次与任务之间的特征需求来设置。通过实际算例发现任务之间的距离 的值大小不一，当 的值比较大时，说明任务之间的距离比较远，当班次执行任务 ，时，会花费过多时间在路上，不利于班次的利用率，因此需要添加如下有效不等式：；，且 （）其中，根据机场的实际类型进行设置。另外，由式（）可知如果一个任务指派给一个班次，那么班次的开始时间要小于任务被实际执行的开始时间。特别是对于指派给班次的首个任务，为了降低班次的等待时长，提高人员利用率，需要对班次的等待时间进行限制，即添加有效不等式（）：（）（）；，（）班次等待时间不能大于其正常工作总时间的 。对于变量，当 和 ，约束条件（）和（）变成如下形式：（）；，（）（）；，（）即，要求任务与班次之间的开始 结束时间要完全满足时 间 约 束。在 实 验 部 分，通 过 设 定 不 同 的，的值来比较考虑部分覆盖率的重要性。实验结果与分析 算例生成问题的求解采用 版本。由于机场中的不同任务分布在机场不同位置，任务之间有距运 筹 与 管 理 年第 卷离约束，为了减少班次浪费在路上的时间，通过观察机场实际数据可知设置合适参数值：，算例的求解时间限制在 内。通过对实际数据分析发现每天任务和班次的比例大概为 ：。所有测试的算例是从国内某航空咨询公司提 供 不 同 规 模 的 实 际 数 据 中 随 机 生 成 的，用 表示生成的测试算例，其中 代表机场中的任务，代表机场中的班次。考虑部分覆盖率对目标函数的影响首先对小规模算例进行测试，结果见表 。前三列中“”代表没有考虑部分覆盖率的原算例，其中，“”和“”分别代表原算例的最优解和测试时间（秒），第 第 列表示考虑部分覆盖 率 的 测 试 情 况。由 表 的 测 试 结 果 可 知 优化软件对小规模算例可在 秒内获得整数最优解。第 、第 和第 列是考虑部分覆盖率的测试结果，与第 列测试结果相比，最后一行均值表明，第 、第 和 列中“”的均值分别增涨了 ，和 。相对于第 列考虑部分覆盖率是在原规定时间区间前一部分完成和第 列考虑部分覆盖率在区间后一部分完成相比，第 列考虑的情况操作更加灵活，目标函数值增加更多，而求解时间的变化在可接受时间范围内。另外，单独比较第 、第 和 列中“”的值发现，第 列 中“”的 值 大 于 等 于 第 列 中“”，第 列中“”。表 “部分覆盖率”在小规模算例中的测试结果算例 （）（）（）（）均值 表 给出了大规模算例的求解结果。在设置的时间内可以对规模“”的原算例以及部分考虑覆盖率的算例获得问题的最优解。但是对于“，”的情况，当算例规模达到“”时，无法在规定的时间内求得最优解。从表 可知，第 列和第 列的“”的值相对于“”中的“”分别增加 和 。另外，第 列中从已求得最优解的算例中发现，仍满足“”的值大于等于 第 列中“”，第 列中“”。表 “部分覆盖率”在大规模算例中的测试结果算例 （）（）（）（）均值 第 期田倩南，等：基于多因素分析的机场任务指派建模与仿真 有效不等式的效果对比表 中列“（）”表示添加所有不等式（）（）（）的测试结果；列“（）”表示仅添加不等式（）的测试结果；列“（）”和“（）”分别表示仅添加不等式（）和（）的测试结果；最后一列“”表示没有添加任何有效不等式的测试结果。因为表 涉及到两个目标函数，所以列“”的值均经过归一化处理。由最后一行均值可知，在求解时间上，每一种有效不等式均降低了算例的求解时间，特别是当所有有效不等式同时使用时，效果最为显著，平均求解时间由 缩短为 ，求解效率提高了 。表 有效不等式的效果对比算例 （）（）（）（）（）（）（）（）（）均值 考虑匹配度对目标函数的影响表 中的列“”表示原算例；列“”表示仅考虑资格匹配度的测试结果；最后两列表示既考虑任务的部分覆盖率同时也考虑资格匹配度的测试结果。表 涉及到两个目标，列“”的值均是归一化处理后的值。同样 可以在均值 秒内求解问题的最优解。最后一行均值表明仅考虑匹配度时“”的均值相对于“”中“”的均值降低了 ，说明任务与班次之间的资格精通程度存在一定的差值。而第 列中“”的均值相对于第 列“”的均值增加了 ，说明即使在目标函数中添加了资格的匹配度，但是在允许任务考虑部分覆盖率的情况下，仍然可以对目标函数显著增加。表 “匹配度”在小规模算例中的测试结果算例 （）（）（）均值 运 筹 与 管 理 年第 卷 不同属性对目标函数的影响 降低任务要求对目标函数的影响机场每年都会通过对工作人员进行培训以及资格考核来提高工作人员的业务水平。随着工作人员业务水平的提高，那么任务的要求就相对降低。在机场任务指派问题中，机场每天有大量任务等着指派，而班次数量有限，由式（）可知，越多任务被指派，越有利于式（）值增加，所以尝试对机场任务分类，有较低要求的任务被分在一起，测试任务要求的降低对目标函数值影响的影响。如表所示：第 列中的算例是在第 列算例的基础上把每个算例中任务的资格要求降低 （其他属性保持不变）得到的。前三列分别代表原算例的测试结果；在接下来的第 列 第 列，都是针对第 列中算列的测试情况。由于表 涉及到两个目标函数，所以列“”的值均是归一化处理后的值。由均值的可知，降低任务要求会对目标函数产生显著影响，尤其是再考虑部分覆盖率的情况，目标函数值的增加量高达 ，从而对机场任务完成率 影 响 更 直 观。即 使 考 虑 资 格 的 匹 配 度，“”的均值均大于以上其他属性中“”的均值。因此，当班次给定时，降低任务资格要求的同时也考虑任务的部分覆盖率和资格的匹配度，不仅可以增加任务的完成率，使收益更大，而且还能在一定程度上控制资源浪费。班次工作时长对目标函数的影响通过检验实际算例发现，机场任务指派问题中有一部分任务总时长为 分钟而没有被执行的，究其原因发现，针对这些任务，虽然有些班次满足任务资格要求和熟练程度等要求，但是由于工作时长不满足，导致这些任务无法指派。在机场，随着淡旺季不同以及临时突发状态的发生，就会出现在某一段时间内机场的任务量剧增，地勤人员在轮班之外适当延长 分钟的加班时间是比较普遍的一种措施。实验结果表明，当只改变班次的工作时长时，目标函数值随着班次工作时长的增加而增加。既考虑增加班次工作时长又考虑部分覆盖率时“”的均值增加了 ；考虑班次工作时长增加同时考虑部分覆盖率和资格匹配度，“”均值降低了 。这表明在特殊时期合理延长班次的工作时间，有利于提升机场的服务水平，提高乘客的满意度。表 降低任务要求对目标函数影响算例 （）算例降低 （），（）（）（）均值 均值 总结本文研究了考虑多因素的机场任务指派问题，建立了多目标整数规划模型，通过对模型分析提出有效不等式。结合公司的实际数据，调用 优化软件分别对原算例、考虑不同情况下任务部分覆盖率以及资格匹配度的算例求解。求解数据显示，针对大规模算例的求解时间仍可接受，并且考虑任务的部分覆盖率能够提高机场资源的利用率，同时也对有效不等式的效果进行了测试分析。由于任务和班次又具有多种属性，本文同时对影响目第 期田倩南，等：基于多因素分析的机场任务指派建模与仿真标函数的两个因素：任务资格要求和班次工作时长分别测试分析。通过算例的求解结果对比发现，根据机场类型特征调整不同因素和对应的任务部分覆盖率以及资格的匹配度，不仅可以有效提高机场任务的完成率和机场的运行效率，而且在保持一定服务水平的同时还能控制资源的浪费，可为企业实际运营决策提供科学依据。参考文献：中国民用 航 空 局 年 民 航 行 业 发 展 统 计 公 报 （）：，（）：，：樊玮，吴建波，衡红军 基于多 的机场地面服务车辆 调 度 方 法 研 究 计 算 机 应 用 与 软 件，（）：彭瑛，胡明华，李印风 基于航班时刻优化的跑道运行容 量 提 升方 法 系统 工 程 理 论与 实 践，（）：张建同，杨文娟 基于优先级的进离港飞机排序优化问题研究 运筹与管理，（）：胡玉真，张耸 基于多目标规划的飞机路径恢复最优化算法研究 运筹与管理，（）：，：，（）：，（）：，（）：，（）：付晓薇，郭强，马芹芹 一类非确定型多目标指派问题及其算法研究 运筹与管理，（）：，（）：，（）：，（）：运 筹 与 管 理 年第 卷