基于BP方程算法的多机型机组恢复时空网络模型

摘要

Aircrew scheduling recovery is an important part of airlines work.To abate the effect on flight operation planning from abnormal aircrew scheduling,various types of airplane crew recovery time-space network model is built up.Before the establishment,the objective constraint according to abnormal aircrew scheduling is analyzed.Meanwhile,the minimum of airlines operation aircrew recovery of multi-types of airplanes based on time-space network model and heuristic binary search algorithm on costs is the optimization goal.These models are applied to the actual operational data of some domestic airline to carry on the instance analysis.Minimum vertex cover and BP(Bethe-Peierls) equation algorithm are used to solve it.Results showed that the usage of minimum vertex cover and BP equation algorithm accelerate the aircrew scheduling recovery and increase the robustness of aircrew scheduling recovery.They adjust automatically when some factor changes.Whole-related structure is employed to help aircrew scheduling automatically adjust to urgent change of factors.This model is simple to operate and with strong systematicness to be used widely.%航空公司工作中的一个重要部分就是不正常机组排班恢复,为减少机组排班不正常对航班运行计划的影响,以航空公司资源浪费最小为优化目标,在分析不正常机组排班要满足的客观约束条件下,建立了多机型不正常机组排班恢复的时空网络数学模型,并针对国内某航空公司的实际运营数据运用该模型进行实例分析,利用最小顶点覆盖(MDS)和BP方程法求解.结果表明:用MDS和BP方程法不仅加速了机组排班恢复的时间,更增加了机组排班恢复的鲁棒性.该方法利用完全相关结构,当遇到某些突发情况时,机组排班能自动随之调整,操作起来方法简便,适用面广,并且系统性强,便于普及和推广.