航班机组自动编排研究及实现
|
摘要
民航机组排班问题是人员安排类型中经典的NP-hard难题,涉及到较多的限制条件和优化因素。在航空公司的运营费用中,人力资源支出的费用占据了很大的比例,近年来更是成为继航油费用之后航空企业第二大成本支出。因此,合理地科学地进行机组排班,将有利于充分利用航空公司人力资源,降低运营成本,提高航空公司的竞争力。
本文在分析国内外研究的基础上,首先详细论述了机组排班的主要流程,分析了机组配对、人员分组和机组指派等关键环节和技术。比较现有算法如遗传算法、模拟退火算法、蚁群算法、粒子群算法和人工神经网络算法的可行性可靠性,选择符合实现要求的遗传算法,对编码方式、概率值和初始种群的产生进行改进调整,使得更便于系统实现。接下来对排班问题的机组配对、机组指派环节建立数学模型,设计系统中所需要的数据结构和数据库中的表结构,将算法和数学语言描述的解决方法用计算具体实现。最后总结了有待改进的地方,提出改进设想。
Crew scheduling is a classical NP-hard combinatorial optimization problem in area of Airline Flight Scheduling, It refers lots of restrictions and optimum rules. The expenses on crew resources take a great part in the flight expenses of the civil aviation firms. Especially in recent years, the costs of crew resources has become the second largest cost just follow the oil cost. So, scientific crew scheduling would be able to have a good use of human resources in the firm, reduce operating expenses and improve airline’s competitiveness.
This essay based with the recent study of crew scheduling problem. First of all, the essay introduces the flow of crew scheduling, it also analyses the key point and technology to solve the problem. In essay it compares the feasibility and the dependability of popular algorithms then chooses the genetic algorithm to implement the system. After that the essay makes the mathematic models of all the steps of crew scheduling then design the data structures and datasheets. In the end, the essay summarizes the shortages which the system needs improve and some further suggestions.
本文在分析国内外研究的基础上,首先详细论述了机组排班的主要流程,分析了机组配对、人员分组和机组指派等关键环节和技术。比较现有算法如遗传算法、模拟退火算法、蚁群算法、粒子群算法和人工神经网络算法的可行性可靠性,选择符合实现要求的遗传算法,对编码方式、概率值和初始种群的产生进行改进调整,使得更便于系统实现。接下来对排班问题的机组配对、机组指派环节建立数学模型,设计系统中所需要的数据结构和数据库中的表结构,将算法和数学语言描述的解决方法用计算具体实现。最后总结了有待改进的地方,提出改进设想。
Crew scheduling is a classical NP-hard combinatorial optimization problem in area of Airline Flight Scheduling, It refers lots of restrictions and optimum rules. The expenses on crew resources take a great part in the flight expenses of the civil aviation firms. Especially in recent years, the costs of crew resources has become the second largest cost just follow the oil cost. So, scientific crew scheduling would be able to have a good use of human resources in the firm, reduce operating expenses and improve airline’s competitiveness.
This essay based with the recent study of crew scheduling problem. First of all, the essay introduces the flow of crew scheduling, it also analyses the key point and technology to solve the problem. In essay it compares the feasibility and the dependability of popular algorithms then chooses the genetic algorithm to implement the system. After that the essay makes the mathematic models of all the steps of crew scheduling then design the data structures and datasheets. In the end, the essay summarizes the shortages which the system needs improve and some further suggestions.
引文
[1]中国民用航空总局规划发展司,2006年航空运输指标,从统计看民航(2007),2007,1:71～72
[2] Dennis Huisman and Albert P.M. Wagelmans,A solution approach for dynamic vehicle and crew scheduling,European Journal of Operational Research, In Press, Corrected Proof, Available online 16 December 2004.
[3]程恺,机组运行控制系统的研究与实现,北京航空航天大学,2002。
[4]李青、张军、张学军,解决排班问题的多目标优化模型及算法研究,北京航空航天大学学报,2003年9月,第29卷第9期:821～824。
[5] G.L.Nemhauser, L.A.Wolsey, Integer and Combinatorial Optimization, New York,Wiley-Interscience,1988:127～140.
[6] Hjorring, C.A. and J. Hansen. (1999). Column Generation with a Rule Modeling Language for Airline Crew Pairing. In Proceedings of the 34th Annual Conference of the Operational Research Society of New Zealand, Hamilton, New Zealand, December 10–11, pp. 133–142.
[7] S.Yan, T.-T. Tung and Y.-P.Tu,Optimal construction of airline individual crew pairings,Computers & Operations Research, Volume 29, Issue 4, April 2002:341-363.
[8] Niklas Kohl,Stefan E.Karisch,Airline Crew Rostering: Problem Types, Modeling, and Optimization,Annals of Operations Research,2004,Volume 127(Numbers 1-4):223～157。
[9]于贵桃,南航机组排班系统的研究与应用,中国民航学院学报,2003年10月,第21卷增刊2:79～81。
[10] Diego Klabjan,Ellis L.Johnson,Georgel L.nemhause,Solving Large Airline Crew Scheduling Problems: Random Pairing Generation and Strong Branching,Computational Optimization and Applications,20,2001: 73–91.
[11] Wedelin D, The Design of a 0-1 Integer Optimizer and its Application in the Carmen System, European Journal of Operational Research, 87:722–730, 1995.
[12] Srinivas M, Patnaik L M. Adaptive probabilities of crossover and mutation in genetic algorithms. IEEE Transaction on System ,Man and Cybernetics , 1994 , 24 (4): 656～666。
[13] Panta L. Simulated annealing for the multi2objective aircrew rostering problem. Transportation Research , 1999 ,33 (A) : 19～45。
[14] Fraster A S., Simulation of Genetic System, J of Theoretical Biology, 1962.2: 329～346.
[15]明亮,遗传算法的模式理论及收敛理论,西安,西安电子科技大学,2006。
[16]阎平凡,张长水,人工神经网络与模拟进化计算,清华大学出版社,2000。
[17] Wong, K.P, Wong, Y.W. Genetic and genetic/simulated-annealing Approaches to electromic, IEE Proc.C, Generation, Transmission and Distribution.Vol.141, NO5. 1994,9:507～513。
[18] De Jong KA, Analysis of the Behavior of a Class of Genetic Adaptive Systems, Ph D Dissertation, University of Michigan,1995:76-93.
[19]张维明,姚莉,智能协作信息技术,电子工业出版社,北京,2002:245～252。
[20]孙宏,杜文,徐杰,最小费用最大流模型在航班衔接问题中的应用,南京航空航天大学学报,2001,第33卷第5期:478～481。
[21]孙宏,杜文,飞机排班数学规划模型,交通运输工程学报,2004,第4卷第3期:117～120。
[22] Joyce W.yen,A Stochastic Programming Formulation Of The Stochastic Crew Scheduling Problem, Industrial and Operations Engineering,the University of Michigan,2001。
[23] Srnivas M.Patnaik L M. , Adaptive Probability of Crossover and Mutation in Genetic Algorithm, IEEE Trans on SMC. 1994, 24(4):656-667.
[24]王红,齐燕楠,机组人员搭配协调性评价方法的研究,计算机工程与设计,2006,第27卷第17期:3220～3276。
[25]王红,齐燕楠,刘金兰,分阶段飞行人员排班方法的研究,中国科技信息,2006,第20期:103-105,107。
[26] Andersson E., Housos E., Kohl N., Wedelin D.,Operations Research in the Airline Industry. Kluwer Academic Publishing,1997:15～21。
[27] Anne Mercier,Fran?ois Soumis,An integrated aircraft routing, crew scheduling and flight retiming model,Computers & Operations Research, In Press, Corrected Proof, Available online 15 November 2005:48～65.
[28] Jay Michael Rosenberger,Topics in Airline Operations,Georgia Institute of Technology,November 2001:225～235.
[29] Etschmaier M.M., Mathaisel D.F. Airline Scheduling: An Overview. Transportation Science, 19:127–138, 1985.
[30] Harry Kornilakis ,Panagiotis Stamatopoulos, Crew Pairing Optimization with Genetic Algorithms, I.P. Vlahavas and C.D. Spyropoulos (Eds.): SETN 2002, LNAI 2308, 2002,Springer-Verlag Berlin Heidelberg 2002:109～120.
[31] Tina L.shaw,Hybrid Column Generation for Large Network Routing Problems: with Implementations in Airline Crew Scheduling,Georgia Institute of Technology,April 2003.
[32]陶世群,蒲保兴,基于遗传算法的多级目标非平衡指派问题求解,系统工程理论与实践,2004年8月第8期:80～85。
[33]黄康,许志伟,董迎晖,改进的遗传算法及其在多目标优化设计中的应用,机械计,2005年9月,第22卷第9期:735～738。
[34] Martin T.Hagan, Howard B.Demuth, Mark H.Beale,神经网络设计(戴葵,李伯民),北京:机械工业出版社,2002。
[35]陈国良,遗传算法及其应用,北京:人民邮电出版社,1996:88～89。
[36]李金屏,何苗,杨波,遗传算法平均截止代数和成功率与种群规模之间的关系.系统仿真学报(增刊),2001,V 0113:206-210。
[37] Sanghyun Kim, Adaptations of constraint programming to aircraft scheduling problems, Washington University, August,2001.
[38]王小平,曹立明,遗传算法,西安交通大学出版社,2002。
[39] Harp S,etal,Towards the Genetic Synthesis of Neural Networks. ICGA,1989.360～369.
[40]赵赫,杜端甫,遗传算法求解旅行推销员问题时的算子的设计与选择,系统工程理论与实践,1998,18(2): 62-65。
[2] Dennis Huisman and Albert P.M. Wagelmans,A solution approach for dynamic vehicle and crew scheduling,European Journal of Operational Research, In Press, Corrected Proof, Available online 16 December 2004.
[3]程恺,机组运行控制系统的研究与实现,北京航空航天大学,2002。
[4]李青、张军、张学军,解决排班问题的多目标优化模型及算法研究,北京航空航天大学学报,2003年9月,第29卷第9期:821～824。
[5] G.L.Nemhauser, L.A.Wolsey, Integer and Combinatorial Optimization, New York,Wiley-Interscience,1988:127～140.
[6] Hjorring, C.A. and J. Hansen. (1999). Column Generation with a Rule Modeling Language for Airline Crew Pairing. In Proceedings of the 34th Annual Conference of the Operational Research Society of New Zealand, Hamilton, New Zealand, December 10–11, pp. 133–142.
[7] S.Yan, T.-T. Tung and Y.-P.Tu,Optimal construction of airline individual crew pairings,Computers & Operations Research, Volume 29, Issue 4, April 2002:341-363.
[8] Niklas Kohl,Stefan E.Karisch,Airline Crew Rostering: Problem Types, Modeling, and Optimization,Annals of Operations Research,2004,Volume 127(Numbers 1-4):223～157。
[9]于贵桃,南航机组排班系统的研究与应用,中国民航学院学报,2003年10月,第21卷增刊2:79～81。
[10] Diego Klabjan,Ellis L.Johnson,Georgel L.nemhause,Solving Large Airline Crew Scheduling Problems: Random Pairing Generation and Strong Branching,Computational Optimization and Applications,20,2001: 73–91.
[11] Wedelin D, The Design of a 0-1 Integer Optimizer and its Application in the Carmen System, European Journal of Operational Research, 87:722–730, 1995.
[12] Srinivas M, Patnaik L M. Adaptive probabilities of crossover and mutation in genetic algorithms. IEEE Transaction on System ,Man and Cybernetics , 1994 , 24 (4): 656～666。
[13] Panta L. Simulated annealing for the multi2objective aircrew rostering problem. Transportation Research , 1999 ,33 (A) : 19～45。
[14] Fraster A S., Simulation of Genetic System, J of Theoretical Biology, 1962.2: 329～346.
[15]明亮,遗传算法的模式理论及收敛理论,西安,西安电子科技大学,2006。
[16]阎平凡,张长水,人工神经网络与模拟进化计算,清华大学出版社,2000。
[17] Wong, K.P, Wong, Y.W. Genetic and genetic/simulated-annealing Approaches to electromic, IEE Proc.C, Generation, Transmission and Distribution.Vol.141, NO5. 1994,9:507～513。
[18] De Jong KA, Analysis of the Behavior of a Class of Genetic Adaptive Systems, Ph D Dissertation, University of Michigan,1995:76-93.
[19]张维明,姚莉,智能协作信息技术,电子工业出版社,北京,2002:245～252。
[20]孙宏,杜文,徐杰,最小费用最大流模型在航班衔接问题中的应用,南京航空航天大学学报,2001,第33卷第5期:478～481。
[21]孙宏,杜文,飞机排班数学规划模型,交通运输工程学报,2004,第4卷第3期:117～120。
[22] Joyce W.yen,A Stochastic Programming Formulation Of The Stochastic Crew Scheduling Problem, Industrial and Operations Engineering,the University of Michigan,2001。
[23] Srnivas M.Patnaik L M. , Adaptive Probability of Crossover and Mutation in Genetic Algorithm, IEEE Trans on SMC. 1994, 24(4):656-667.
[24]王红,齐燕楠,机组人员搭配协调性评价方法的研究,计算机工程与设计,2006,第27卷第17期:3220～3276。
[25]王红,齐燕楠,刘金兰,分阶段飞行人员排班方法的研究,中国科技信息,2006,第20期:103-105,107。
[26] Andersson E., Housos E., Kohl N., Wedelin D.,Operations Research in the Airline Industry. Kluwer Academic Publishing,1997:15～21。
[27] Anne Mercier,Fran?ois Soumis,An integrated aircraft routing, crew scheduling and flight retiming model,Computers & Operations Research, In Press, Corrected Proof, Available online 15 November 2005:48～65.
[28] Jay Michael Rosenberger,Topics in Airline Operations,Georgia Institute of Technology,November 2001:225～235.
[29] Etschmaier M.M., Mathaisel D.F. Airline Scheduling: An Overview. Transportation Science, 19:127–138, 1985.
[30] Harry Kornilakis ,Panagiotis Stamatopoulos, Crew Pairing Optimization with Genetic Algorithms, I.P. Vlahavas and C.D. Spyropoulos (Eds.): SETN 2002, LNAI 2308, 2002,Springer-Verlag Berlin Heidelberg 2002:109～120.
[31] Tina L.shaw,Hybrid Column Generation for Large Network Routing Problems: with Implementations in Airline Crew Scheduling,Georgia Institute of Technology,April 2003.
[32]陶世群,蒲保兴,基于遗传算法的多级目标非平衡指派问题求解,系统工程理论与实践,2004年8月第8期:80～85。
[33]黄康,许志伟,董迎晖,改进的遗传算法及其在多目标优化设计中的应用,机械计,2005年9月,第22卷第9期:735～738。
[34] Martin T.Hagan, Howard B.Demuth, Mark H.Beale,神经网络设计(戴葵,李伯民),北京:机械工业出版社,2002。
[35]陈国良,遗传算法及其应用,北京:人民邮电出版社,1996:88～89。
[36]李金屏,何苗,杨波,遗传算法平均截止代数和成功率与种群规模之间的关系.系统仿真学报(增刊),2001,V 0113:206-210。
[37] Sanghyun Kim, Adaptations of constraint programming to aircraft scheduling problems, Washington University, August,2001.
[38]王小平,曹立明,遗传算法,西安交通大学出版社,2002。
[39] Harp S,etal,Towards the Genetic Synthesis of Neural Networks. ICGA,1989.360～369.
[40]赵赫,杜端甫,遗传算法求解旅行推销员问题时的算子的设计与选择,系统工程理论与实践,1998,18(2): 62-65。