基于任务均衡的航空公司机组人员指派问题研究
|
摘要
民航运输的发展与国民经济的发展息息相关。改革开放以来，随着我国国民经济的快速发展，旅客出行量不断增加，据中商情报网的数据显示2011年中国民航旅客运输量累计高达2.92亿人，其中国内航线旅客运输量累计达2.71亿人，并且预计2012年中国民航旅客运输量将达到3.2亿人。为了应对这种情况，各航空公司都在积极寻求对策，提高自己的竞争力。高铁的出现更是进一步加剧了竞争的趋势，因此国内民航企业要想取得竞争优势，就必须不断提高自身的竞争力，降低成本、提高运营效率。
机组排班是航空公司的生产计划的一个重要部分。合理的机组排班是提高航空公司运营效率、降低运营成本的重要手段之一。机组人员指派问题是机组排班的一个重要子问题，它是在满足公平、合理原则的前提下，根据配对结果和机型属性将机组人员(飞行人员和乘务人员)合理地安排到机组配对生成的每个任务串上去，充分的利用空勤资源。随着航空公司运营规模的扩大，机组排班的数据量增大、限制条件繁多，完全依靠人工完成该项工作的难度越来越大。
本文把机组人员指派问题作为集合覆盖问题来研究。首先通过对机组人员指派问题所要满足的原则和限制条件的分析，构建了飞行员分类指标体系，并通过调查问卷和层次分析法相结合的方法量化了影响飞行员搭配的指标权重；其次根据飞行员搭配指标体系产生机组成员，并对产生的机组进行评价，在机组对应的集合覆盖所有的航班任务串的条件下，建立了以任务分配均衡为目标的单目标函数，并通过分析和比较常用的优化算法，选择了优化能力比较高的自适应遗传算法进行算法设计。最后阐述了完成机组人员指派所要进行的数据信息整理，并选取了国内某航空公司的部分航班任务串和机组数据运用MATLAB进行了实验仿真，验证了算法的可行性。
Civil aviation transportation development has a close relationship with the developmentof national economy. Since the reform and opening up, and along with the rapid developmentof China's national economy, the passenger travel volume keeps on the increase. According tothe data released by askci.com, the passenger volume of China civil aviation in 2011 totals upto 292 million, among which domestic volume is 271 million, and it is expected to reach 320million till 2012. In order to deal with such situation, airlines are actively seekingcountermeasures to improve own competitiveness. While the appearance of high-speedrailway further intensified the competition, the domestic civil aviation enterprises have toimprove their own competitiveness, reduce cost, and improve operation efficiency to gaincompetitive edge.
Crew scheduling is an important part of airline's production planning, and reasonablecrew scheduling is a significant measure to improve airlines operation efficiency and reduceoperation cost. Crew assignment, a sub problem of crew scheduling, while under thecircumstances of justice and reasonability, arrange the crew members (pilots and flightattendants) to each generated task serial according to the matched results and aircraft typeproperty, and make full use of flight resources. Along with the expansion of airlines’operation scale, the increase of crew scheduling data quantity and various constraints, it’smuch harder to complete the work entirely depend on labors.
This paper regards the crew assignment as a set covering problem. First, after analyzingthe principles and constraints that the crew assignment must meet, builds a pilot classificationindex system, and quantitative the index weight that influence the pilot collocation throughthe combination of questionnaire and Analytic Hierarchy Process. Secondly, generates crewmembers based on the pilot collocation index system, and evaluates the crew. On conditionthat the corresponding set covering all the flight task serials, builds single objective functionaims at task allocation balance. Through the analysis and comparison of commonoptimization algorithm, chooses Adaptive Genetic Algorithm which has higher optimalcapacity to design algorithm. Finally, states the data information gathering of crew assignment,and selects part of flight task serials of one domestic airlines and crew data to conductexperimental simulation, then proves the feasibility of the algorithm.
机组排班是航空公司的生产计划的一个重要部分。合理的机组排班是提高航空公司运营效率、降低运营成本的重要手段之一。机组人员指派问题是机组排班的一个重要子问题，它是在满足公平、合理原则的前提下，根据配对结果和机型属性将机组人员(飞行人员和乘务人员)合理地安排到机组配对生成的每个任务串上去，充分的利用空勤资源。随着航空公司运营规模的扩大，机组排班的数据量增大、限制条件繁多，完全依靠人工完成该项工作的难度越来越大。
本文把机组人员指派问题作为集合覆盖问题来研究。首先通过对机组人员指派问题所要满足的原则和限制条件的分析，构建了飞行员分类指标体系，并通过调查问卷和层次分析法相结合的方法量化了影响飞行员搭配的指标权重；其次根据飞行员搭配指标体系产生机组成员，并对产生的机组进行评价，在机组对应的集合覆盖所有的航班任务串的条件下，建立了以任务分配均衡为目标的单目标函数，并通过分析和比较常用的优化算法，选择了优化能力比较高的自适应遗传算法进行算法设计。最后阐述了完成机组人员指派所要进行的数据信息整理，并选取了国内某航空公司的部分航班任务串和机组数据运用MATLAB进行了实验仿真，验证了算法的可行性。
Civil aviation transportation development has a close relationship with the developmentof national economy. Since the reform and opening up, and along with the rapid developmentof China's national economy, the passenger travel volume keeps on the increase. According tothe data released by askci.com, the passenger volume of China civil aviation in 2011 totals upto 292 million, among which domestic volume is 271 million, and it is expected to reach 320million till 2012. In order to deal with such situation, airlines are actively seekingcountermeasures to improve own competitiveness. While the appearance of high-speedrailway further intensified the competition, the domestic civil aviation enterprises have toimprove their own competitiveness, reduce cost, and improve operation efficiency to gaincompetitive edge.
Crew scheduling is an important part of airline's production planning, and reasonablecrew scheduling is a significant measure to improve airlines operation efficiency and reduceoperation cost. Crew assignment, a sub problem of crew scheduling, while under thecircumstances of justice and reasonability, arrange the crew members (pilots and flightattendants) to each generated task serial according to the matched results and aircraft typeproperty, and make full use of flight resources. Along with the expansion of airlines’operation scale, the increase of crew scheduling data quantity and various constraints, it’smuch harder to complete the work entirely depend on labors.
This paper regards the crew assignment as a set covering problem. First, after analyzingthe principles and constraints that the crew assignment must meet, builds a pilot classificationindex system, and quantitative the index weight that influence the pilot collocation throughthe combination of questionnaire and Analytic Hierarchy Process. Secondly, generates crewmembers based on the pilot collocation index system, and evaluates the crew. On conditionthat the corresponding set covering all the flight task serials, builds single objective functionaims at task allocation balance. Through the analysis and comparison of commonoptimization algorithm, chooses Adaptive Genetic Algorithm which has higher optimalcapacity to design algorithm. Finally, states the data information gathering of crew assignment,and selects part of flight task serials of one domestic airlines and crew data to conductexperimental simulation, then proves the feasibility of the algorithm.
引文
[1]中商情报网[EB/OL], http://www.askci.com, 2012-02-17
[2]李建.航班机组自动编排研究及实现[D].南京：南京航空航天大学, 2008
[3]赵焕省.航班机组排班算法及应用技术研究[D].南京：南京航空航天大学, 2007
[4]王红,齐雁楠.机组人员搭配协调性评价方法的研究[J].计算机工程与设计, 2006, 27（17）：3220-3223
[5]李巍.机组排班算法中指标权重确定的研究及应用[D].上海：同济大学, 2007
[6]李青.解决排班问题的多目标优化模型及算法研究[J].北京航空航天大学学报, 2003, 29（9）：270-274
[7]邵俊.基于遗传算法的机组任务配对研究[D].南京：南京航空航天大学, 2006
[8]王红，齐雁楠，刘金兰.分阶段飞行人员排班方法的研究[J].中国科技信息, 2006, 20：90-94
[9]石岩涛.一个实际指派问题的研究[J].运筹与管理, 2006, 15（4）：114-117
[10]赵红竹.基于自适应遗传算法的机组排班方法研究和应用[D].南京：南京航空航天大学, 2008
[11]李耀华,谭娜.飞机排班调度中机组指派优化模型及算法研究[J].计算机工程与应用, 2008, 44（34）：243-245
[12]宋静波.基于单亲遗传算法的飞行机组指派技术[J].哈尔滨商业大学学报, 2009，25（3）：311-314
[13]赵正佳.航空公司机组排班计划研究[J].运筹与管理, 2011, 20（6）：106-110
[14]于贵桃.南航机组排班系统的研究与应用[J].中国民航学院学报, 2003, 21（2）：79-83
[15]陆东银,夏洪山.模块化混合编程技术在机组排班系统中的应用[J].山东理工大学学报, 2010，24（2）：89-93
[16] Dennis Huisman, Albert P. M. A solution approach for dynamic vehicle and crew scheduling [J].European Journal of operational Research , 2004: 267-276
[17] Barnhart, Boland N. L., Charke L. W., et al. Flight string models for aircraft fleeting and routing[J].Transportation Science, 1998, 32:208-220
[18] Shaw C.C. A nee aircrew scheduling model for short-haul routes[J]. Journal of Air TransportationManagement, 2002,8:249-260
[19] Gopalakrishnan B, Johnson E.L. Airline crew scheduling: state-of-the-art [J]. Annals of OperationsResearch, 2005, 140:305-337
[20] Sydney C.K.C. Generating, scheduling and rostering of shift crew-duties: applications at the hongkong international airport [J]. European Journal of Operational Research, 2007, 177:1764-1778
[21] Mercier A, Soumis F. An integrate aircraft routing, crew scheduling and flight retiming model[J].Computers and Operations Research, 2007, 34(8):2251-2265
[22] Wedelin D. An algorithm for large scale 0-1 integer programming with application to airline crewscheduling[J]. Annals of Operations Research, 1995, 57:283-301
[23] Vance P.H., Barnhart C, Johnson E.L., et al. Airline crew scheduling: a new formulation anddecomposition algorithm[J]. Operations Research, 1997, 45(2):188-200
[24] Cordeau J, Stojkovic G, Soumis F, et al. Benders decomposition for simultaneous aircraft routing andcrew scheduling[J]. Transportation Science, 2001, 35:375-388
[25] Souai N, Teghem J. Genetic algorithm based approach for the integrated airline crew-pairing androstering problem[J]. European Journal of Operational Research, 2008
[26]卢慧.基于多Agent的机组配对算法及实现技术研究[D].南京：南京航空航天大学, 2006
[27] Campbell K.W., Durfee R.B., Hines G.S.“FedEx Generates Bid Lines Using Simulated Annealing.”Interfaces 27(2), 1-16, 1997
[28] Jarrah A.I., Diamond J.T.“The problem of Generation Crew Bidlines.”Interfaces 27(4), 49-64,1997
[29] Christou I.A.“A Two-Phase Genetic Algorithm for Large-Scale Bidline-Generation Problems at DeltaAir Lines.”Interfaces 29(5), 51-65,1999
[30]孙宏，文军.航空公司生产组织与计划[M].成都：西南交通大学出版社, 2008：1-5
[31]何光勤,罗风娥,马志刚.签派程序与方法[M].成都：西南交通大学出版社, 2004：41-45
[32] Dusan Teodorovic, Panta Lucic.“A fuzzy set theory approach to the aircrew rostering problem.”FuzzySets and Systems 95, 261-271, 1998
[33]中国民用航空局.民用航空器驾驶员,飞行教员和地面教员合格审定规则[Z]. 2004
[34]中国民用航空局.大型飞机公共航空运输承运人运行合格审定规则[Z]. 2010
[35]潘俊美.浅谈我国民航飞行员的激励问题[J].中国集体经济, 2008, 3：114-117
[36]王凌.智能优化算法及其应用[M].北京：清华大学出版社, 2001：37-40, 53-55
[37] Wedelin D. The Design of a 0-1 integer Optimizer and its Application in the Carmen System [J].European Journal of Operational Research, 1995, 87:722-730
[38]邢文训,谢金星.现代优化计算方法[M].北京：清华大学出版社, 2005：134-135
[39]邓成梁.运筹学的原理和方法[M].武汉：华中科技大学出版社, 2001：127-128
[40] Herbert Dawid, Johannes Kok nig, Christine Strauss. An Enhanced Rostering Model for AirlineCrews[J]. Computers & Operations Research, 2001, 28:671-688
[41] Michel Gamache, Francois Soumis, Gerald Marquis. A Column Generation Approach for Large-scaleAircrew Rostering Problems[J]. Operations Research, 1999
[42] Torsten Fahle. Constraint Programming Based Column Generation for Crew Assignment[J]. Journal ofHeuristics, 2002, 8:59-81
[43] Meinolf Sellmann. Crew Assignment via Constraint Programming: Integrating Column Generationand Heuristic Tree Search[J]. Annals of Operations Research, 2002,115:207-225
[44] Jesper Hansen, Tomas Liden. Group Construction for Airline Cabin Crew: Comparing ConstraintProgramming with Branch and Price[C]. CPAIOR, 2005:228-242
[45]周明，孙树栋.遗传算法原理及应用理[M].北京：国防工业出版社，2005：81-82,108-113
[46] Panta L. Simulated Annealing for The Multi-Objective Aircrew Rostering Problem[J]. TransportationResearch, 1999:19-45
[47] Timucin Ozdemi H. GraGA: A Graph Based Genetic Algorithm for Airline Crew Scheduling[J].Transportation Research, 2000:29-40
[48] Brindle A. Genetic Algorithms for Function Optimization[D]. Alberta: University of Alberta, 1981
[49] Back T. The interaction of Mutation Rate, Selection and Self-adaptation within Genetic Algorithms. In:Manner R AND Manderick B eds. Parallel Problem Solving Nature. Amstterdam, North Holland:Elsevier, 15-25
[50] Goldberg D.E. Genetic Algorithms in Search, Optimization, and machine learning[D]. Addison Wesley,1989
[51] Syswerda G. Uniform Crossover in Genetic Algorithms[J]. In: Third Int Conf on Genetic Algorithms,1989:2-9
[52] Starkweather T. A Comparison of Genetic Sequencing Operators. In: Fourth Int Conf on GeneticAlgorithms. Los Altos, CA: Morgan Kaufman Publishers, 1991:69-76
[53]张蕾.基于遗传算法的机组排班问题研究[D].天津：中国民用航空学院, 2005
[54] De Jong KA. Analysis of the Behavior of a Class of Genetic Adaptive Systems[D]. University ofMichigan, 1995:76-93
[55]韩生廉,武晓今,倪萌.组合优化问题中遗传算法的局限性及其改进模式[J].控制与决策, 2002,17（2）：219-224
[56]官兆.基于自适应遗传算法的服务工作流调度问题的研究[D].广州：中山大学, 2010
[57] Srinivas M., Patnaik L.M. Adaptive Probabilities of Crossover and Mutation in Genetic Algorithms.IEEE Trans on SMC 1994, 24(4):656-677
[58]王蕾,沈庭芝,招扬.一种改进的自适应遗传算法[J].系统工程与电子技术, 2002, 24（5）：76-78
[59]王红,张蕾.遗传算法在航空公司飞行人员排班中的应用研究[J].计算机工程与应用, 2006：220-222
[2]李建.航班机组自动编排研究及实现[D].南京：南京航空航天大学, 2008
[3]赵焕省.航班机组排班算法及应用技术研究[D].南京：南京航空航天大学, 2007
[4]王红,齐雁楠.机组人员搭配协调性评价方法的研究[J].计算机工程与设计, 2006, 27（17）：3220-3223
[5]李巍.机组排班算法中指标权重确定的研究及应用[D].上海：同济大学, 2007
[6]李青.解决排班问题的多目标优化模型及算法研究[J].北京航空航天大学学报, 2003, 29（9）：270-274
[7]邵俊.基于遗传算法的机组任务配对研究[D].南京：南京航空航天大学, 2006
[8]王红，齐雁楠，刘金兰.分阶段飞行人员排班方法的研究[J].中国科技信息, 2006, 20：90-94
[9]石岩涛.一个实际指派问题的研究[J].运筹与管理, 2006, 15（4）：114-117
[10]赵红竹.基于自适应遗传算法的机组排班方法研究和应用[D].南京：南京航空航天大学, 2008
[11]李耀华,谭娜.飞机排班调度中机组指派优化模型及算法研究[J].计算机工程与应用, 2008, 44（34）：243-245
[12]宋静波.基于单亲遗传算法的飞行机组指派技术[J].哈尔滨商业大学学报, 2009，25（3）：311-314
[13]赵正佳.航空公司机组排班计划研究[J].运筹与管理, 2011, 20（6）：106-110
[14]于贵桃.南航机组排班系统的研究与应用[J].中国民航学院学报, 2003, 21（2）：79-83
[15]陆东银,夏洪山.模块化混合编程技术在机组排班系统中的应用[J].山东理工大学学报, 2010，24（2）：89-93
[16] Dennis Huisman, Albert P. M. A solution approach for dynamic vehicle and crew scheduling [J].European Journal of operational Research , 2004: 267-276
[17] Barnhart, Boland N. L., Charke L. W., et al. Flight string models for aircraft fleeting and routing[J].Transportation Science, 1998, 32:208-220
[18] Shaw C.C. A nee aircrew scheduling model for short-haul routes[J]. Journal of Air TransportationManagement, 2002,8:249-260
[19] Gopalakrishnan B, Johnson E.L. Airline crew scheduling: state-of-the-art [J]. Annals of OperationsResearch, 2005, 140:305-337
[20] Sydney C.K.C. Generating, scheduling and rostering of shift crew-duties: applications at the hongkong international airport [J]. European Journal of Operational Research, 2007, 177:1764-1778
[21] Mercier A, Soumis F. An integrate aircraft routing, crew scheduling and flight retiming model[J].Computers and Operations Research, 2007, 34(8):2251-2265
[22] Wedelin D. An algorithm for large scale 0-1 integer programming with application to airline crewscheduling[J]. Annals of Operations Research, 1995, 57:283-301
[23] Vance P.H., Barnhart C, Johnson E.L., et al. Airline crew scheduling: a new formulation anddecomposition algorithm[J]. Operations Research, 1997, 45(2):188-200
[24] Cordeau J, Stojkovic G, Soumis F, et al. Benders decomposition for simultaneous aircraft routing andcrew scheduling[J]. Transportation Science, 2001, 35:375-388
[25] Souai N, Teghem J. Genetic algorithm based approach for the integrated airline crew-pairing androstering problem[J]. European Journal of Operational Research, 2008
[26]卢慧.基于多Agent的机组配对算法及实现技术研究[D].南京：南京航空航天大学, 2006
[27] Campbell K.W., Durfee R.B., Hines G.S.“FedEx Generates Bid Lines Using Simulated Annealing.”Interfaces 27(2), 1-16, 1997
[28] Jarrah A.I., Diamond J.T.“The problem of Generation Crew Bidlines.”Interfaces 27(4), 49-64,1997
[29] Christou I.A.“A Two-Phase Genetic Algorithm for Large-Scale Bidline-Generation Problems at DeltaAir Lines.”Interfaces 29(5), 51-65,1999
[30]孙宏，文军.航空公司生产组织与计划[M].成都：西南交通大学出版社, 2008：1-5
[31]何光勤,罗风娥,马志刚.签派程序与方法[M].成都：西南交通大学出版社, 2004：41-45
[32] Dusan Teodorovic, Panta Lucic.“A fuzzy set theory approach to the aircrew rostering problem.”FuzzySets and Systems 95, 261-271, 1998
[33]中国民用航空局.民用航空器驾驶员,飞行教员和地面教员合格审定规则[Z]. 2004
[34]中国民用航空局.大型飞机公共航空运输承运人运行合格审定规则[Z]. 2010
[35]潘俊美.浅谈我国民航飞行员的激励问题[J].中国集体经济, 2008, 3：114-117
[36]王凌.智能优化算法及其应用[M].北京：清华大学出版社, 2001：37-40, 53-55
[37] Wedelin D. The Design of a 0-1 integer Optimizer and its Application in the Carmen System [J].European Journal of Operational Research, 1995, 87:722-730
[38]邢文训,谢金星.现代优化计算方法[M].北京：清华大学出版社, 2005：134-135
[39]邓成梁.运筹学的原理和方法[M].武汉：华中科技大学出版社, 2001：127-128
[40] Herbert Dawid, Johannes Kok nig, Christine Strauss. An Enhanced Rostering Model for AirlineCrews[J]. Computers & Operations Research, 2001, 28:671-688
[41] Michel Gamache, Francois Soumis, Gerald Marquis. A Column Generation Approach for Large-scaleAircrew Rostering Problems[J]. Operations Research, 1999
[42] Torsten Fahle. Constraint Programming Based Column Generation for Crew Assignment[J]. Journal ofHeuristics, 2002, 8:59-81
[43] Meinolf Sellmann. Crew Assignment via Constraint Programming: Integrating Column Generationand Heuristic Tree Search[J]. Annals of Operations Research, 2002,115:207-225
[44] Jesper Hansen, Tomas Liden. Group Construction for Airline Cabin Crew: Comparing ConstraintProgramming with Branch and Price[C]. CPAIOR, 2005:228-242
[45]周明，孙树栋.遗传算法原理及应用理[M].北京：国防工业出版社，2005：81-82,108-113
[46] Panta L. Simulated Annealing for The Multi-Objective Aircrew Rostering Problem[J]. TransportationResearch, 1999:19-45
[47] Timucin Ozdemi H. GraGA: A Graph Based Genetic Algorithm for Airline Crew Scheduling[J].Transportation Research, 2000:29-40
[48] Brindle A. Genetic Algorithms for Function Optimization[D]. Alberta: University of Alberta, 1981
[49] Back T. The interaction of Mutation Rate, Selection and Self-adaptation within Genetic Algorithms. In:Manner R AND Manderick B eds. Parallel Problem Solving Nature. Amstterdam, North Holland:Elsevier, 15-25
[50] Goldberg D.E. Genetic Algorithms in Search, Optimization, and machine learning[D]. Addison Wesley,1989
[51] Syswerda G. Uniform Crossover in Genetic Algorithms[J]. In: Third Int Conf on Genetic Algorithms,1989:2-9
[52] Starkweather T. A Comparison of Genetic Sequencing Operators. In: Fourth Int Conf on GeneticAlgorithms. Los Altos, CA: Morgan Kaufman Publishers, 1991:69-76
[53]张蕾.基于遗传算法的机组排班问题研究[D].天津：中国民用航空学院, 2005
[54] De Jong KA. Analysis of the Behavior of a Class of Genetic Adaptive Systems[D]. University ofMichigan, 1995:76-93
[55]韩生廉,武晓今,倪萌.组合优化问题中遗传算法的局限性及其改进模式[J].控制与决策, 2002,17（2）：219-224
[56]官兆.基于自适应遗传算法的服务工作流调度问题的研究[D].广州：中山大学, 2010
[57] Srinivas M., Patnaik L.M. Adaptive Probabilities of Crossover and Mutation in Genetic Algorithms.IEEE Trans on SMC 1994, 24(4):656-677
[58]王蕾,沈庭芝,招扬.一种改进的自适应遗传算法[J].系统工程与电子技术, 2002, 24（5）：76-78
[59]王红,张蕾.遗传算法在航空公司飞行人员排班中的应用研究[J].计算机工程与应用, 2006：220-222