航空公司机组航班任务串优化方法研究
|
摘要
机组排班是航空公司生产活动中的重要环节。科学合理地进行机组排班可以优化配置机组资源，降低航空公司的机组成本，在某些情况下，既可以保证航班飞行的正常执行，又可以减少人力使用，这对于航空公司来说非常重要。研究机组排班的技术和方法，实现计算机辅助排班，对于降低航空公司运营成本，提高机组管理信息化水平和市场竞争力具有重要意义。机组排班通常分为机组航班任务串编排和机组指派两个阶段。本论文主要研究机组排班前一阶段工作——机组航班任务串编排。
论文对机组航班任务串编排的限制条件及优化目标进行了深入的研究，通过构建航班连接网络图来获得所有初始可行航班任务串，根据航空公司的实际需求建立了基于机组资源利用率最大的数学优化模型，最后以某小型航空公司一天的航班计划为例采用遗传算法进行了求解，求解结果与手工编排结果相对比，证明该方法是可靠的。在当前激烈竞争的航空运输市场环境及国内机组资源严重短缺的情况下，提高机组资源利用率的思想对于航空公司编排航班任务串具有一定的指导意义。
The crew scheduling is a most important part in airline operation. A scientific andrational crew scheduling planning can reach the optimal allocation of crew resource, andreduce the crew cost. It not only can guarantee the normal execution of the flights, but alsocan reduce the total human resource needed, which are very important for airlines. The studyof the methods and techniques of crew scheduling with the assistance of computers are ofgreat significance for airlines in aspects of reducing the operating cost and improving marketcompetitiveness. Crew scheduling is usually divided into two phases: crew pairing problemand crew assignment problem. In this paper, we focused on studying the crew pairingproblem.
We conducted a deep research on constraints and optimization goals of crew pairingproblem. First, by constructing flight connect network diagram, all initial feasible flight dutystrings were obtained. Then, according to the actual requirements of airlines, a mathematicaloptimization model was established based on maximum utilization of crew resource. Last, wetook a daily flight plan of a small airline as an example, and used genetic algorithm to solvethe problem. The method is proved to be true by contrast with the manual pairing result. Inthe condition of a fierce competition air transport market environment and a serious shortageof domestic crew resource, the idea of improving the utilization of crew resource has certainguidance significance for airlines.
论文对机组航班任务串编排的限制条件及优化目标进行了深入的研究，通过构建航班连接网络图来获得所有初始可行航班任务串，根据航空公司的实际需求建立了基于机组资源利用率最大的数学优化模型，最后以某小型航空公司一天的航班计划为例采用遗传算法进行了求解，求解结果与手工编排结果相对比，证明该方法是可靠的。在当前激烈竞争的航空运输市场环境及国内机组资源严重短缺的情况下，提高机组资源利用率的思想对于航空公司编排航班任务串具有一定的指导意义。
The crew scheduling is a most important part in airline operation. A scientific andrational crew scheduling planning can reach the optimal allocation of crew resource, andreduce the crew cost. It not only can guarantee the normal execution of the flights, but alsocan reduce the total human resource needed, which are very important for airlines. The studyof the methods and techniques of crew scheduling with the assistance of computers are ofgreat significance for airlines in aspects of reducing the operating cost and improving marketcompetitiveness. Crew scheduling is usually divided into two phases: crew pairing problemand crew assignment problem. In this paper, we focused on studying the crew pairingproblem.
We conducted a deep research on constraints and optimization goals of crew pairingproblem. First, by constructing flight connect network diagram, all initial feasible flight dutystrings were obtained. Then, according to the actual requirements of airlines, a mathematicaloptimization model was established based on maximum utilization of crew resource. Last, wetook a daily flight plan of a small airline as an example, and used genetic algorithm to solvethe problem. The method is proved to be true by contrast with the manual pairing result. Inthe condition of a fierce competition air transport market environment and a serious shortageof domestic crew resource, the idea of improving the utilization of crew resource has certainguidance significance for airlines.
引文
[1]赵焕省,航班机组排班算法及应用技术研究[D] .南京:南京航空航天大学, 2007: 3-5
[2]邵俊,基于遗传算法的机组任务配对研究[D] .南京:南京航空航天大学, 2006: 1-2
[3]于贵桃,南航机组排班系统的研究与应用[J] .中国民航学院学报, 2003, 10(21): 80-81
[4]李建,航班机组自动编排研究及实现[D] .南京:南京航空航天大学, 2008: 32-38
[5]李青,解决排班问题的多目标优化模型及算法研究[J] .北京航空航天大学学报, 2003, 29(9):822-823
[6]王红,遗传算法在航空公司飞行人员排班中的应用研究[J] .计算机工程与应用, 2006, (10):220-221
[7]石丽娜,基于二次遗传算法的机组任务配对问题研究[J] .计算机工程与设计, 2008, 29(5):1244-1246
[8]赵红竹,基于自适应遗传算法的机组排班方法研究和应用[D] .南京:南京航空航天大学, 2008:21-22
[9] Harry Kornilakis and Panagiotis Stamstopoulos, Crew Pairing Optimization with Genetic Algorithms.Transportation Science[J]. 2001,35(4): 363-365
[10] Taejin Park .Kwang Ryel Ryu, Crew pairing optimization by a genetic algorithm with unexpressedgenes, Springer Science+Business Media[J]. 2006:375-376
[11]卢慧,基于多AGENT的机组配对算法及实现技术研究[D] .南京:南京航空航天大学, 2006:11-12
[12]中国民用航空总局.大型飞机公共航空运输航空承运人运行合格审定规(CCAR-121FS-R2).中国民用航空总局.北京: 2005:130-136
[13] Cynthia Barnhart, Airline Crew Scheduling, Handbook of Transportation Science[M]. 2001: 518-521
[14]孙宏,文军,航空公司生产组织与计划[M].成都:西南交通大学出版社, 2008: 79-89
[15]朱金福,航空运输规划[M],南京:西北工业大学出版社, 2009: 461-480
[16]张吉吉,一种基于遗传算法的多重决策树组合分类方法[J] .系统工程理论与实践, 2004, (4):64-68
[17] Shaw Ching Chang, A new aircrew-scheduling model for short-haul routes, Journal of Air TransportManagement[J]. 2002, (8):249-260
[18] Joyce.W.Yen, A Stochastic Programming Approach To Airline Crew Scheduling Problem.Transportation Science[J]. 2006, 40(1): 5-6
[19]周棍,夏洪山,基于启发式遗传算法的航班勤务编排算法[J] .信息与控制, 2010, 39(3): 362-363
[20]邢文训,谢金星,现代优化计算方法[M],北京:清华大学出版社, 2003: 379-384
[21]陶世群,基于遗传算法的多级目标非平衡指派问题求解[J] .系统工程理论与实践, 2004, (8):81-82
[22]宋静波,基于单亲遗传算法的飞行机组指派技术[J] .哈尔滨商业大学学报, 2009, 25(3): 312-313
[23]王红,齐雁楠,刘金兰,分阶段飞行人员排班方法的研究[J] .中国科技信息, 2006, (20): 103-104
[24]王正林,龚纯,精通Matlab科学计算[M],北京:电子工业出版社, 2009: 415-417
[25] Peter Wark, Aircrew schedule generation using repeated matching, European Journal of OperationalResearch[J]. 1997, 102:21-22
[26] Christos Goumopoulos, Efficient trip generation with a rule modeling system for crew schedulingproblems, The Journal of Systems and Software[J]. 2004, 69: 48-49
[27] Balaji Gopalakrishnan, Airline Crew Scheduling: State-of-the-Art, Annals of Operations Research[J].2005, 140:309-310
[28] Wei Yang, It r Z. Karaesmen·P nar, Keskinocak·Sridhar Tayur, Aircraft and crew scheduling forfractional ownership programs, Springer Science+Business Media[J], 2007: 415-416
[29] Dennis Huisman, Multiple-Depot Integrated Vehicle and Crew Scheduling, Transportation Science[J].2005, 39(4): 492-493
[30] Ellis L.Johnson, Airline Crew Scheduling under Uncertainty, Transportation Science[J]. 2005,39(3):342-343
[31] Ellis L.Johnson, Solving Large Airline Crew Scheduling Problem, Computational Optimization andApplications[J]. 2001,20:74-75
[32] Sergey Shebalov, Robust Airline Crew Pairing: Move-up crews, Transportation Science[J].2006,40(3) :301-302
[2]邵俊,基于遗传算法的机组任务配对研究[D] .南京:南京航空航天大学, 2006: 1-2
[3]于贵桃,南航机组排班系统的研究与应用[J] .中国民航学院学报, 2003, 10(21): 80-81
[4]李建,航班机组自动编排研究及实现[D] .南京:南京航空航天大学, 2008: 32-38
[5]李青,解决排班问题的多目标优化模型及算法研究[J] .北京航空航天大学学报, 2003, 29(9):822-823
[6]王红,遗传算法在航空公司飞行人员排班中的应用研究[J] .计算机工程与应用, 2006, (10):220-221
[7]石丽娜,基于二次遗传算法的机组任务配对问题研究[J] .计算机工程与设计, 2008, 29(5):1244-1246
[8]赵红竹,基于自适应遗传算法的机组排班方法研究和应用[D] .南京:南京航空航天大学, 2008:21-22
[9] Harry Kornilakis and Panagiotis Stamstopoulos, Crew Pairing Optimization with Genetic Algorithms.Transportation Science[J]. 2001,35(4): 363-365
[10] Taejin Park .Kwang Ryel Ryu, Crew pairing optimization by a genetic algorithm with unexpressedgenes, Springer Science+Business Media[J]. 2006:375-376
[11]卢慧,基于多AGENT的机组配对算法及实现技术研究[D] .南京:南京航空航天大学, 2006:11-12
[12]中国民用航空总局.大型飞机公共航空运输航空承运人运行合格审定规(CCAR-121FS-R2).中国民用航空总局.北京: 2005:130-136
[13] Cynthia Barnhart, Airline Crew Scheduling, Handbook of Transportation Science[M]. 2001: 518-521
[14]孙宏,文军,航空公司生产组织与计划[M].成都:西南交通大学出版社, 2008: 79-89
[15]朱金福,航空运输规划[M],南京:西北工业大学出版社, 2009: 461-480
[16]张吉吉,一种基于遗传算法的多重决策树组合分类方法[J] .系统工程理论与实践, 2004, (4):64-68
[17] Shaw Ching Chang, A new aircrew-scheduling model for short-haul routes, Journal of Air TransportManagement[J]. 2002, (8):249-260
[18] Joyce.W.Yen, A Stochastic Programming Approach To Airline Crew Scheduling Problem.Transportation Science[J]. 2006, 40(1): 5-6
[19]周棍,夏洪山,基于启发式遗传算法的航班勤务编排算法[J] .信息与控制, 2010, 39(3): 362-363
[20]邢文训,谢金星,现代优化计算方法[M],北京:清华大学出版社, 2003: 379-384
[21]陶世群,基于遗传算法的多级目标非平衡指派问题求解[J] .系统工程理论与实践, 2004, (8):81-82
[22]宋静波,基于单亲遗传算法的飞行机组指派技术[J] .哈尔滨商业大学学报, 2009, 25(3): 312-313
[23]王红,齐雁楠,刘金兰,分阶段飞行人员排班方法的研究[J] .中国科技信息, 2006, (20): 103-104
[24]王正林,龚纯,精通Matlab科学计算[M],北京:电子工业出版社, 2009: 415-417
[25] Peter Wark, Aircrew schedule generation using repeated matching, European Journal of OperationalResearch[J]. 1997, 102:21-22
[26] Christos Goumopoulos, Efficient trip generation with a rule modeling system for crew schedulingproblems, The Journal of Systems and Software[J]. 2004, 69: 48-49
[27] Balaji Gopalakrishnan, Airline Crew Scheduling: State-of-the-Art, Annals of Operations Research[J].2005, 140:309-310
[28] Wei Yang, It r Z. Karaesmen·P nar, Keskinocak·Sridhar Tayur, Aircraft and crew scheduling forfractional ownership programs, Springer Science+Business Media[J], 2007: 415-416
[29] Dennis Huisman, Multiple-Depot Integrated Vehicle and Crew Scheduling, Transportation Science[J].2005, 39(4): 492-493
[30] Ellis L.Johnson, Airline Crew Scheduling under Uncertainty, Transportation Science[J]. 2005,39(3):342-343
[31] Ellis L.Johnson, Solving Large Airline Crew Scheduling Problem, Computational Optimization andApplications[J]. 2001,20:74-75
[32] Sergey Shebalov, Robust Airline Crew Pairing: Move-up crews, Transportation Science[J].2006,40(3) :301-302