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

taptap下载安装安卓学报

• 民用航空 • 上一篇 taptap点点手机网页

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

张青¹，马永秀¹，杨正全¹，陈增强^1,2

（1.taptap下载安装安卓理学院，天津300300；2.南开大学计算机与控制工程学院，天津300350）

收稿日期:2017-01-10 修回日期:2017-02-22 出版日期:2017-10-25 发布日期:2017-12-14
作者简介:张青（1965—），女，天津人，教授，硕士，研究方向为复杂系统建模与优化、多智能体系统等.
基金资助:
国家自然科学基金项目（6157399）；天津市自然科学基金项目（14JCYBJC18700）；中央高校基本科研业务费专项（3122015C025）

Crew recovery time-space network model with various types of airplanes based on BP equation algorithm

ZHANG Qing¹, MA Yongxiu¹, YANG Zhengquan¹, CHEN Zengqiang^1,2

（1. College of Science, CAUC, Tianjin 300300, China; 2. College of Computer and Control Engineering, Nankai University,Tianjin 300350, China）

Received:2017-01-10 Revised:2017-02-22 Online:2017-10-25 Published:2017-12-14

摘要/Abstract

摘要： 航空公司工作中的一个重要部分就是不正常机组排班恢复，为减少机组排班不正常对航班运行计划的影响，以航空公司资源浪费最小为优化目标，在分析不正常机组排班要满足的客观约束条件下，建立了多机型不正常机组排班恢复的时空网络数学模型，并针对国内某航空公司的实际运营数据运用该模型进行实例分析，利用最小顶点覆盖（MDS）和BP 方程法求解。结果表明院用MDS 和BP 方程法不仅加速了机组排班恢复的时间，更增加了机组排班恢复的鲁棒性。该方法利用完全相关结构，当遇到某些突发情况时，机组排班能自动随之调整，操作起来方法简便，适用面广，并且系统性强，便于普及和推广。

关键词: BP方程, 最小顶点覆盖, 机组排班恢复, 能量函数, 时空网络模型

Abstract: 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.

Key words: BP equation algorithm, minimum vertex cover, aircrew scheduling recovery, energy function, time-space network model

中图分类号:

TP272

张青，马永秀，杨正全，陈增强. 基于BP 方程算法的多机型机组恢复时空网络模型[J]. taptap下载安装安卓学报.

ZHANG Qing, MA Yongxiu, YANG Zhengquan, CHEN Zengqiang. Crew recovery time-space network model with various types of airplanes based on BP equation algorithm[J]. .

参考文献

[1] ELLIS L JOHNSON. Final Report to North Airlines on the Crew Recovery Problem[D]. The Lugistic Institute, Georgia Institute of Technology,1994.
[2] WEI G, YU G, SONG M. Optimization model and algorithm for crew management during airline irregular operations[J]. Journal of Combinatorial Optimization, 1997, 1(3): 305-321.
[3] STOJKOVIC M, SOUMIS F, DESROSIERS J. The operational airline crew scheduling problem[J]. Transportation Science, 1998, 32(3): 232-245.
[4] LETTOVSKY L, JOHNSON E L, NEMHAUSER G L. Airline crew recovery[J]. Transportation Science, 2000, 34(4): 337-348.
[5] MEDARD C P, SAWHNEY N. Airline crew scheduling fromplanning to operations[J]. European Journal of Operational Research, 2007, 183(3):1013-1027.
[6] NISSEN R, HAASE K. Duty-period-based network model for crew reseheduling in European airlines[J]. Journal of Scheduling, 2006, 9(3):255-278.
[7] GUO Yufeng, SUHL L, THIEL M P. Solving the airline crew recovery problem by a genetic algorithm with local improvement[J]. Operational Research, 2005, 5(2): 241.
[8] MESQUITA M, PAIAS A. Set partitioning/covering-based approaches for the integrated vehicle and crew scheduling problem[J]. Computers & Operations Research, 2008, 35(5): 1562-1575.
[9] LETTOVSKY L, JOHNSON E L, NEMHAUSER G L. Airline crew recovery[J]. Transportation Science, 2000, 34(4): 337-348.
[10] HARTMANN A K, WEIGT M. Phase Transitions in Combinatorial Optimization Problems: Basics, Algorithms and Statistical Mechanics[M]. Hobken, New Jersey: John Wiley & Sons, 2006.
[11] GARDNER E. Spin glasses with p-spin interactions[J]. Nuclear Physics B, 1985, 257: 747-765.
[12] KIRKPATRICK T R, THIRUMALAI D. p-spin-interaction spin-glass models:connectionswiththestructuralglassproblem[J].Physical Review B, 1987, 36(10): 5388.
[13] 李腊梅,吴汉松,王树人. 基于BP 算法的模糊关系方程解法及仿真[J].计算机仿真, 2007, 24(4): 149-151.
[14] 王春妮, 王亚, 马军. 基于亥姆霍兹定理计算动力学系统的哈密顿能量函数[J].物理学报, 2016, 65(24): 240501-240501.
[15] 周雪梅,李辉, 潘多. 基于能量函数的故障诊断方法与实验[J].计算机工程与设计, 2015, 36(5): 1385-1389.
[16] FREY B J. Graphical Models for Machine Learning and Digital Communication[M]. Cambridge, Mass: MIT press, 1998.
[17] KSCHISCHANG F R, FREY B J, LOELIGER H A. Factor graphs and the sum-product algorithm[J]. IEEE Transactions on information theory,2001, 47(2): 498-519.
[18] 许锋,潘琦, 王一岚, 等.工业过程多变量系统常规控制结构的频域设计[J].清华大学学报(自然科学版), 2016, 56(4): 448-452.

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

Crew recovery time-space network model with various types of airplanes based on BP equation algorithm

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 0

编辑推荐

Metrics

本文评价