运筹学理论在航空领域的应用

随着中国经济的不断发展,国家综合实力的不断提高,作为最先进的交通运输方式与重要的国民经济组成,民用航空业也迎来了迅猛的发展。随着国内运输需求的增加,以东航为代表的国内航空公司航班总量与机队规模迅速扩大。对于航空公司而言,人力成本、燃油成本及资本/商业支持成本是构成公司运营成本的三驾马车。而在人力资源中,机组资源是其核心部分,而国内航空公司又都普遍面临着机组培养速度跟不上航班任务增长速度的问题,导致目前以手动方式安排机组、调配资源的排班方式面临着空前的挑战。

运筹学是20世纪初发展起来的一门新兴学科,是现代管理学的一门重要专业基础课,也是近代应用数学的一个分支,主要是通过对有限的资源进行优化配置,以求系统最优的科学决策方法。在现代民用航空领域当中,运筹学有着诸多关键应用,早在上世纪80年代,美航就利用运筹学方法将收益管理应用到自身当中,使其每年的收益增加了近5000万美元。

机组自动排班优化的问题属于资源调配优化、工作计划安排的问题,是典型的可以通过运筹学来优化、解决的问题。为解决目前手动排班能力不足的问题,通过计算机和自动化手段进行机组资源的优化安排,合理安排并在最大程度上利用机组资源、发挥其效用十分必要。但是,这类问题因优化难度高、问题结构复杂,也属于当今国际运筹学界最顶尖技术难题。机组自动排班问题作为运筹学界最难的问题之一,全球只有极少数几家欧美公司能开发出机组自动排班系统,且价额昂贵。

虽然对于机组排班问题国外早有研究,也有一些成熟的产品,但是由于国内航空公司的情况与国外航空公司情况截然不同,这些产品的基础业务功能与国内航空公司所面临的实际需求有很大差异,并无法完全适用到国内航空公司运营当中。因此,东航开发出一套具有自主产权的、可以高度定制化、能够适应自身需求的机组自动排班系统就非常重要,也非常有意义。

机组自动排班的过程可以分为组环和排班两个过程。组环的过程可以理解为一个航班配对联线的成一个“环”的过程,而排班则是为已经组成“环”的航班任务安排执勤人员的过程。在机组自动排班系统中,组环的结果对排班过程有着举足轻重的影响。组出来的“环”的性质一来决定着这一个任务当中执勤人员的结构,二来影响着所需执勤人员的资质需求。组环的过程也有一定的规则与要求,既有它作为一个“环”自身的需求,比如起始机场与结束机场相同且必须为基地机场、期间航班任务时间不能重叠等等,也有民航局和东航机组管理部门制定“环”的规则要求,比如航班之间的过站时间、“环”的时间长度和飞行时间限制等等。组环的过程也是一个寻求各因素动态平衡与最优的过程。比如说环的长度这一因素,如果组出来的“环”越长,那么总体环的数量就越少,自动排班的难度也就越低,但“环”越长,所需要执行这一任务环的人的资质就越复杂,可用执勤人员就越少;在另一方面来看,如果“环”越短,那么总体环的数量就越少,排班结果的灵活性也就越高,但“环”越短,环的数量也就越多,需要特殊资质人员的“环”也就越多,会导致执勤人员不足的问题。因此,最终的组环结果要有一个总体最优的指标,维持“环”长度等因素的动态平衡,为自动排班的过程提供良好的基础。

当所有的航班都被组成“环”之后,就可以为这些“环”安排飞行员,也就是排班了。排班主要有两种类型的约束和要求,一类是由“环”所决定的资质类别要求,比如安排给这个“环”的人需要何种资质、等级的飞行员,需要飞行员的数量与配置是如何;另一个是民航局以及东航自身制定的对飞行员飞行时间、休息时间等条件限制,比如飞行员每月最多的飞行时间是多少、飞行员执勤的“环”之间至少需要有多长的休息时间等等。自动排班系统的主要目标就是在满足这些约束和要求的前提下,为所有“环”安排可用的机组人员。此外,在满足排班硬性需求的前提下,还要尽量使排版结果人性化、均衡化,减轻机组人员的疲劳度。

机组自动排班系统的整个求解过程是非常复杂的,是一个在巨大的多面体空间内寻找一个最优点的过程。简单来说,假设只有4个航班,组环的方法只有唯一的两两组环,也有12种可能性;不考虑安排副驾驶、学员的情况下,也至少需要2名机长。仅仅对于这4个航班、2名机长、单一组环方法来说,就有24种排班的可能性;而考虑到整个东航的资源配置、组环方法的多样性,整个机组自动排班的复杂度可想而知。因此,将整个机组自动排班的过程比作大海捞针并不夸张。

但是随着计算机能力水平的提高及大规模数学规划商业软件的应用,“大海捞针”并非遥不可及。信息部机组排班项目组采购了当今世界领先的数学规划求解软件Gurobi,与依托世界名校“佐治亚理工大学”(Gatech)、具有全美领先航空优化经验的美国公司Decision Making L.L.C等供应商通力合作,开发出了具有自主产权、高度定制化的机组自动排班系统。目前,该系统的组环功能已经全面应用到东航上海基地及全部分子公司的机组排班的进程当中,后续的排班功能也已经在多家分子公司上线并处在运行测试当中。机组自动排班系统的应用,不但能够使机组管理部门面临的排班困难问题迎刃而解,大幅度减轻排班人员的工作量,在一定程度上还能够对整个公司资源的分配与划拨、规章制度的制定与应用及商业计划的预测与决策起到指导作用。

回到开篇的陈述,

除了机组自动排班系统,民用航空业的领域当中还有许多地方可以利用运筹学的理论和方法来实现流程与结果的优化。通过机组自动排班系统的这一个应用可以发现,在民用航空领域智能化改革的趋势是不可避免的。而经过东航人近几年来不懈的努力,整个东航的运营模式已经从靠口头传授交流、纸质文书流转的传统模式转变为依靠计算机系统进行数据处理的自动化模式。自动化模式的建立为东航向智能化发展奠定了良好的基础,未来信息部也将以机组自动排班系统为起始,逐步开发出更多改善现有流程与模式的、优化最终结果、减轻人员工作量与疲劳程度、节省公司运营成本的产品,为东航向智能化的跨越做出更大的贡献。

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: