航空公司不正常航班恢复模型及算法研究
摘要
恶劣天气、飞机故障、空中流量控制等外界条件的不确定性常常造成航班计划不能正常执行,航班不正常对旅客造成了很大的不便,也成为航空公司提高服务质量,降低运营成本的一大障碍,不正常航班计划恢复正是针对这一问题提出的。不正常航班计划恢复问题是一个实时大规模整数规划问题,其变量和约束条件复杂,目前能够满足航空公司实践需要的研究成果很少。由航空公司资助开发的航班计划恢复算法,具有保密性和专用性,而且不同航空公司的运作机制具有很大差异,目前还没有商业化的软件供航空公司使用。我国对不正常航班计划恢复问题的研究处于起步阶段,航班计划恢复工作依然是由签派人员手工完成,很难在较短的时间内实现资源的优化配置。本文的目的就是采用数学方法描述和求解不正常航班计划恢复问题。本文的主要研究工作包括以下几个部分:
1)取消航班问题。取消航班是不正常航班计划恢复过程中经常遇到的一个调度问题:给出多个建议的取消航班起点和终点对,求最优的取消航班路径。将Floyd‐Warshall算法应用到取消航班问题中,为取消航班设计了求解算法,使签派人员在取消航班决策时能够快速有效的获得优化方案。
2)飞机路线恢复问题。飞机路线恢复问题是典型的资源指派问题,本文从目标函数、约束条件两个方面改进资源指派数学模型。构造了两个不同的目标函数,一是旅客延误时间最小,二是航空公司损失最小。旅客延误时间最小目标函数中引入了延误权重因子,在保证总延误时间最短的情况下克服了少数航班被分配长时间延误的不足;航空公司损失最小目标函数改变了以往延误成本的计算方法,并首次引入了旅客失望溢出成本的概念。约束条件增加了机场设施和天气条件对飞机的起降约束、不出现超售、定检约束和重要航班优先执行。提出了逐延误指派算法对模型求解,逐延误指派算法按照签派人员调整航班的思路启发式地恢复飞机路线,可快速获得问题的可行解。案例测试显示,该算法能够获得比签派人员手工调整优化、高效的恢复方案。
3)机组恢复问题。机组是航空公司除飞机以外的第二个重要资源,在飞机路线恢复完成后,如果机组无法到位,航班会依旧延误。机组恢复就是给完成了飞机指派的航班分配合适的机组。本文为机组恢复问题构造了数学模型,以加机组使用成本最小为目标函数,充分考虑了机组执行任务的约束条件,采用蚁群算法对模型求解,在蚁群算法中引入蚂蚁种类参数对蚁群算法改进,使之适合机组恢复问题的求解需要。案例测试显示,设计的模型和算法能够满足机组恢复的实际要求。
4)一体化航班计划恢复问题。目前求解航班恢复问题,采用的是分阶段方法:首先恢复飞机路线,然后是机组路线,最后将受影响的旅客重新指派到相应的航班上。一体化航班恢复是针对这几个问题的综合恢复,目前还没有能够在计算机上实现。一体化航班恢复属于大规模数学规划问题,本文给出了描述一体化航班恢复问题的数学模型,由于问题规模较大且变量和约束条件复杂,直接求解无疑是困难的,采用Benders’分解算法对模型求解,将一体化航班计划恢复问题分解为一个限制主问题和三个子问题,限制主问题是航班时刻表恢复问题,子问题分别是飞机路线恢复、机组恢复和旅客路线恢复问题。给出了各个子问题和对偶问题的数学表达,求解子问题及对偶问题,将产生的可行割或优化割反馈回限制主问题,迭代直到获得主问题的最优解。给出了算法的详细求解步骤并编码实现。最后案例测试显示算法能够实时地给出较为满意的结果。
Bad weather, aircraft failures, air traffic control and other external conditions of uncertainty often resulted in the normal flight schedules cannot be implemented, irregular flights cause much inconvenience to the passengers, and it has also become an obstacle to the improving service quality and reducing operational costs for airline, the irregular flight recovery is made to solve this problem. Irregular flight recovery is a real-time, large-scale and integer programming problem, it has complex variables and constraints, the works that can be used in airline practice is less, and the operating mechanisms of the different airlines are also different, the algorithms of flight schedule recovery, which are funded by several famous airline companies, are confidential and exclusive, we have not found commercial software in market yet. Nowadays, the research of irregular flight recovery in China is just at the early stage, flight recovery work is still done manually by dispatchers, and it is difficult to allocate the resources in short time and optimal way. The purpose of this paper is to use mathematical methods to describe and solve the problem of irregular flight recovery. This major research work includes the following sections.
1) The cancellation of flight. The cancellation of flights is a rescheduling problem in flight recovery decision which is often encountered: advising one more pairs of origination and destintion, to find an optimal cancellation path. In this thesis, Floyd-Warshall algorithm is applied to solve cancellation problem, the detail of algorithm is described, and case shows it can get optimization solutions quickly and efficiently.
2) The aircraft route recovery. Aircraft route recovery is a typical resource assignment problem, this thesis present an improved resource assignment mathematical models from objective function and constraints. Two different objective functions have been constructed, the one is the shortest of passenger delays,and the other is the smallest delay loss of airlines. We introduce a weight factor to balance the passenger delays in the first objective function, to overcome the shortage of some flights being allocated long delays. In the second objective function, it is about airline loss in the process of irregular flight recovery, we present a new method to caculate the airline cost, and draw a definifion of Passengers Disappointed Spilling Cost. Much more constraints has considered, such as the facilities and weather conditions in airport, no overbooking, aircraft maintainance, and important flight first. A chasing delay assignment algorithm is proposed to solve the model. The algorithm restore the aircraft routes according to the idea of dispatchers in the process of resuming flight schedules, and the detail is presented step by step. Cases show it can quickly obtain near optimal solution, and the solution is better than given by dispatchers.
3) The crew recovery. Crew is the second important resources in airlines. Even the aircraft route is restored perfectly, if a crew is not in the right place, flights still delay. The problem of crew recovery is to assign appropriate crew to flight duties after that duties have been allocated right aircraft already. This thesis introduce a mathematical model to solve this problem. The objective function is to minimize the crew loss in the disrupted flight schedule recovery, the requistite constraints have been taken into account in the model to describe the crew recovery problem. Ant colony algorithm is developed for solving the model, and a new concept of ant species is proposed to fit the crew type in ant colony algorithm. Computational experiment has shown that the designed algorithm can meet the practical requirements for crew recovery.
4) Integrated flight recovery. Recovery models today solve flight recovery problem in a phased approach. First, the aircraft routing is restored, then crew pairings are restored. Finally affected passengers are reassigned accordingly. Integrated flight recovery has been the focus of a number of studies, yet it has never been solved computationally. Integrated flight recovery is an instance of a large-scale mathematical program. In this thesis, mathematical model is presented to describe the integrated flight recovery problem. Given the large-scale nature, and variables and constraints are complex, it is extremely difficult to solve the model integrating all components in a suitable runtime. By a Benders’decomposition method, the model is decomposed into one restricted main problem and three sub-problems: schedule recovery, aircraft route recovery, crew recovery, and passenger itinerary recovery. The sub-problems and its dual problem produce feasible cut or optimal cut, and fed the cut back to the main issues, the progressive loops until the main problem get its optimal solution. The detail of algorithm is presented step by step and run it in computer. Cases show that the algorithms can provide a satisfied solution in a suitable runtime.
1)取消航班问题。取消航班是不正常航班计划恢复过程中经常遇到的一个调度问题:给出多个建议的取消航班起点和终点对,求最优的取消航班路径。将Floyd‐Warshall算法应用到取消航班问题中,为取消航班设计了求解算法,使签派人员在取消航班决策时能够快速有效的获得优化方案。
2)飞机路线恢复问题。飞机路线恢复问题是典型的资源指派问题,本文从目标函数、约束条件两个方面改进资源指派数学模型。构造了两个不同的目标函数,一是旅客延误时间最小,二是航空公司损失最小。旅客延误时间最小目标函数中引入了延误权重因子,在保证总延误时间最短的情况下克服了少数航班被分配长时间延误的不足;航空公司损失最小目标函数改变了以往延误成本的计算方法,并首次引入了旅客失望溢出成本的概念。约束条件增加了机场设施和天气条件对飞机的起降约束、不出现超售、定检约束和重要航班优先执行。提出了逐延误指派算法对模型求解,逐延误指派算法按照签派人员调整航班的思路启发式地恢复飞机路线,可快速获得问题的可行解。案例测试显示,该算法能够获得比签派人员手工调整优化、高效的恢复方案。
3)机组恢复问题。机组是航空公司除飞机以外的第二个重要资源,在飞机路线恢复完成后,如果机组无法到位,航班会依旧延误。机组恢复就是给完成了飞机指派的航班分配合适的机组。本文为机组恢复问题构造了数学模型,以加机组使用成本最小为目标函数,充分考虑了机组执行任务的约束条件,采用蚁群算法对模型求解,在蚁群算法中引入蚂蚁种类参数对蚁群算法改进,使之适合机组恢复问题的求解需要。案例测试显示,设计的模型和算法能够满足机组恢复的实际要求。
4)一体化航班计划恢复问题。目前求解航班恢复问题,采用的是分阶段方法:首先恢复飞机路线,然后是机组路线,最后将受影响的旅客重新指派到相应的航班上。一体化航班恢复是针对这几个问题的综合恢复,目前还没有能够在计算机上实现。一体化航班恢复属于大规模数学规划问题,本文给出了描述一体化航班恢复问题的数学模型,由于问题规模较大且变量和约束条件复杂,直接求解无疑是困难的,采用Benders’分解算法对模型求解,将一体化航班计划恢复问题分解为一个限制主问题和三个子问题,限制主问题是航班时刻表恢复问题,子问题分别是飞机路线恢复、机组恢复和旅客路线恢复问题。给出了各个子问题和对偶问题的数学表达,求解子问题及对偶问题,将产生的可行割或优化割反馈回限制主问题,迭代直到获得主问题的最优解。给出了算法的详细求解步骤并编码实现。最后案例测试显示算法能够实时地给出较为满意的结果。
Bad weather, aircraft failures, air traffic control and other external conditions of uncertainty often resulted in the normal flight schedules cannot be implemented, irregular flights cause much inconvenience to the passengers, and it has also become an obstacle to the improving service quality and reducing operational costs for airline, the irregular flight recovery is made to solve this problem. Irregular flight recovery is a real-time, large-scale and integer programming problem, it has complex variables and constraints, the works that can be used in airline practice is less, and the operating mechanisms of the different airlines are also different, the algorithms of flight schedule recovery, which are funded by several famous airline companies, are confidential and exclusive, we have not found commercial software in market yet. Nowadays, the research of irregular flight recovery in China is just at the early stage, flight recovery work is still done manually by dispatchers, and it is difficult to allocate the resources in short time and optimal way. The purpose of this paper is to use mathematical methods to describe and solve the problem of irregular flight recovery. This major research work includes the following sections.
1) The cancellation of flight. The cancellation of flights is a rescheduling problem in flight recovery decision which is often encountered: advising one more pairs of origination and destintion, to find an optimal cancellation path. In this thesis, Floyd-Warshall algorithm is applied to solve cancellation problem, the detail of algorithm is described, and case shows it can get optimization solutions quickly and efficiently.
2) The aircraft route recovery. Aircraft route recovery is a typical resource assignment problem, this thesis present an improved resource assignment mathematical models from objective function and constraints. Two different objective functions have been constructed, the one is the shortest of passenger delays,and the other is the smallest delay loss of airlines. We introduce a weight factor to balance the passenger delays in the first objective function, to overcome the shortage of some flights being allocated long delays. In the second objective function, it is about airline loss in the process of irregular flight recovery, we present a new method to caculate the airline cost, and draw a definifion of Passengers Disappointed Spilling Cost. Much more constraints has considered, such as the facilities and weather conditions in airport, no overbooking, aircraft maintainance, and important flight first. A chasing delay assignment algorithm is proposed to solve the model. The algorithm restore the aircraft routes according to the idea of dispatchers in the process of resuming flight schedules, and the detail is presented step by step. Cases show it can quickly obtain near optimal solution, and the solution is better than given by dispatchers.
3) The crew recovery. Crew is the second important resources in airlines. Even the aircraft route is restored perfectly, if a crew is not in the right place, flights still delay. The problem of crew recovery is to assign appropriate crew to flight duties after that duties have been allocated right aircraft already. This thesis introduce a mathematical model to solve this problem. The objective function is to minimize the crew loss in the disrupted flight schedule recovery, the requistite constraints have been taken into account in the model to describe the crew recovery problem. Ant colony algorithm is developed for solving the model, and a new concept of ant species is proposed to fit the crew type in ant colony algorithm. Computational experiment has shown that the designed algorithm can meet the practical requirements for crew recovery.
4) Integrated flight recovery. Recovery models today solve flight recovery problem in a phased approach. First, the aircraft routing is restored, then crew pairings are restored. Finally affected passengers are reassigned accordingly. Integrated flight recovery has been the focus of a number of studies, yet it has never been solved computationally. Integrated flight recovery is an instance of a large-scale mathematical program. In this thesis, mathematical model is presented to describe the integrated flight recovery problem. Given the large-scale nature, and variables and constraints are complex, it is extremely difficult to solve the model integrating all components in a suitable runtime. By a Benders’decomposition method, the model is decomposed into one restricted main problem and three sub-problems: schedule recovery, aircraft route recovery, crew recovery, and passenger itinerary recovery. The sub-problems and its dual problem produce feasible cut or optimal cut, and fed the cut back to the main issues, the progressive loops until the main problem get its optimal solution. The detail of algorithm is presented step by step and run it in computer. Cases show that the algorithms can provide a satisfied solution in a suitable runtime.
引文
[1]中国民用航空局规划发展司.中国民航统计年鉴[R].中国民用航空局,2007.
[2] Ananda R,Nirup K,Yu G. System Operations Advisor: A Real-Time Decision Support System for Managing Airline Operations at United Airlines,Interfaces[J]. 1996, 2: 50-58.
[3] Jon Petersen Ellis L. Johnson, An Optimization Approach to Airline Integrated Recovery. Georgia Institute of Technology Georgia State,2008.
[4] Barnhart C. Branch-and-Price:Column Generation for Solving Huge Integer Programs,Operations Research[J]. 1998,46(3): 316-329.
[5] D Teodorovic,S Guberinic. Optimal Dispatching Strategy on an Airline Network after a Schedule Perturbation,"European journal of operational research"[J]. 1984,15(2): 178-182.
[6] Teodorovic D. Airline Operations Research. New York::Gordon and breach Science Publishers,1988.
[7] Gershkoff. I, Aircraft Shortage Evaluator, in ORSA/TIMS. joint national meeting. St. Louis:MO,1987.
[8] Ahmad I.Z,Jarrah,Yu Gang. A Decision Support Framework for Airline Flight Cancellations and Delays,Transportation Science[J]. 1993,27: 266-280.
[9] Kanafani Cao J. A Real-Time Decision Support for Integration of Airline Flight Cancellations and Delays, Part I,Transportation Planning and Technology[J]. 1997, 20: 183-199.
[10] Kanafani Cao J. A Real-Time Decision Support for Integration of Airline Flight Cancellations and Delays, Part Ii: Algorithms and Computational Experiments Transportation Planning and Technology[J]. 1997,20: 201-217.
[11] M Argüello, F,J Bard, F,Yu Gang. A Grasp for Aircraft Routing in Response to Groundings and Delays.Journal of Combinatorial Optimization[J]. 1997,5:211-228.
[12] Resende M.G.C. in INFORMS Spring meeting[C]. San Diego, California, USA,1997.
[13] Arguello M.F,Bard J.F,Yu G. Models and Methods for Managing Airline Irregular Operations Aircraft Routing. In : Yu,G.(Ed),Operations Research in the Airline Industry[M]. 1997,1-45.
[14] Yan S.,Yang D. A Decision Support Framework for Handling Schedule Perturbations,Transportation Research, Part B: Methodology[J]. 1996,30(3): 405-419.
[15] Magnanti L.T. Ahuja K.R., Orlin B.J. Network Flows[C]. New Jersey:Prentice Hall,1993.
[16] Young H. Yan S. A Decision Support Framework for Multi-Fleet Routing and Multi-Stop Flight Scheduling,Transportation Research, Part A: Policy and Planning[J]. 1996, 30: 379-398.
[17] Tu Y. Yan S. Multifleet Routing and Multistop Flight Scheduling for Schedule Perturbation,European Journal of Operational Research[J]. 1997,103: 155-169.
[18] Yan S.,Lin C. Airline Scheduling for the Temporary Closure of Airports Transportation science[J]. 1997,31: 72-82.
[19] Bard J.F. Thengvall B.G., Yu G. Multiple Fleet Aircraft Schedule Recovery Following Hub Closures, Transportation research Part A[J]. 2001,35: 289-308.
[20] Bard J.F. Thengvall B.G., Yu G. Balancing User Preferences for Aircraft Schedule Recovery During Irregular Operations IIE Transaction on operations engineering [J]. 2000,32(3): 181-193.
[21] Fisher M.L. The Lagrangian Relaxation Method for Solving Integer Programming Problems Management science[J]. 1981,27: 1-18.
[22] Paulose S. Terrab M. Dynamic Strategic and Tactical Air Traffic Flow Control[C]. in IEEE International Conference on Systems, Man and Cybernetics,1992.
[23] Bard J.F. Thengvall B.G., Yu G. A Bundle Algorithm Approach for the Aircraft Schedule Recovery Problem During Hub Closures,Transportation science[J]. 2003, 37(4): 392-407.
[24] Yu Gang. Operations Research in the Airline Industry[M]. Boston, MA: Kluwer Academic Publishers,1997.
[25]姚韵.航空公司不正常航班管理和调度算法研究[D].南京航空航天大学博士论文.2006.
[26]朱金福.航空运输规划.西安:西北工业大学出版社,2009.
[27]孙宏.航空公司飞机排班问题:模型及算法研究[D].西南交通大学博士论文.2003.
[28]徐肖豪,李雄.航班地面等待模型中的延误成本分析与仿真,南京航空航天大学学[J]. 2006,38(1): 115-121.
[29]谢进一.上海航空公司运行控制体系研究,南京航空航天大学工程硕士学位[D].2006
[30]马正平.机场航班延误优化模型,清华大学学报(自然科学版)[J]. 2004,44(4): 474-477.
[31]田晓东.如何提高航班运行的正常性,中国民用航空[J]. 2004,8: 23-25.
[32]田振才都业富.民航航班延误成本的上升趋势,中国民用航空[J]. 2004,10: 60-62
[33]沙宝亮.航空公司服务质量问题的成因分析,世界标准化与质量管理[J]. 2005,7: 34-36.
[34] E Johnson, L. Lettovsky, G. Nemhauser, R. Pandit,S. Querido, Final Report to Northwest Airlines on the Crew Recovery Problem. 1994, The Logistic Institute, Georgia Institute of Technology, Atlanta, GA.
[35] D Teodorovic,G Stojkovic. Model to Reduce Airline Schedule Disturbances, Journal of Transportation Engineering[J]. 1995,121: 324–331.
[36] D M, Clarke. Irregular Airline Operations: A Review of the State-of-the-Practice in Airline Operations Control Centers,Journal of Air Transport Management[J]. 1998, 4: 67–76.
[37] W. W. Monroe,H. D. Chu, Real-Time Crew Rescheduling at American Airlines[C], Presentation at INFORMS,1995: New Orleans,2003.
[38] G. Stojkovic, F. Soumis, and J. Desrosiers. The Operational Airline Crew Scheduling Problem.Transportation Science [J]. 1998,32: 232–245.
[39] Wei.G,G. Yu. Optimization Model and Algorithm for Crew Management During Airline Irregular Operations,Journal of Combinatorial Optimization[J]. 1997, 1: 305–321.
[40] Lettovsky.L,Johnson E,Nemhauser G..Airline Crew Recovery. Transportation Science[J]. 2000,34: 337-348.
[41] Goutham Ekollu Ahmed Abdelghany, Ram Narasimhan and Khaled Abdelghany. A Proactive Crew Recovery Decision Support Tool for Commercial Airlines During Irregular Operations,Annals of Operations Research[J]. 2004,127: 309-331.
[42] Medard C.P.,N. Sawhney, Airline Crew Scheduling: From Planning to Operations, in Carmen Research and Technology Report. 2004, Carmen Systems AB: Goteborg, Sweden.
[43] Knut Haase Rudiger Nissen. Duty-Period-Based Network Model for Crew Rescheduling in European Airlines,Springer Science + Business Media,[J]. 2006,9: 255–278.
[44] L. Suhl Yufeng Guo, M.P Thiel, Solving the Airline Crew Recovery Problem by a Genetic Algorithm with Local Improvement, in Technical report. WP0408, at DS&OR Lab, University of Paderborn: Germany,2004.
[45] R. Anbil, E. Gelman, B. Patty. Recent Advances in Crew-Pairing Optimization at American Airlines,Interfaces, 1991,2(1): 62-74.
[46] G. Desaulniers, J. Desrosiers, Y. Dumas. Crew Pairing at Air France,European Journal of Operational Research[J]. 1997,97: 220-244.
[47] G. Wei, G. Yu, and M. Song,. Optimization Model and Algorithm for Crew Management During Airline Irregular Operations,Journal of Combinatorial Optimization[J]. 1997,1(3): 305-321.
[48] Teodorovic D.,Stojkovic G. Model to Reduced Airline Schedule Disturbances. Journal of Transportation Engineering[J]. 1995,4: 324-331.
[49]韩健解可新.最优化方法.天津:天津大学出版社,2004.
[50]周志忠.飞行运行实时优化控制研究[D].北京航空航天大博士论文,2001.
[51] L Lettovsky. Airline Operations Recovery: An Optimization Approach 1997.
[52]刘德刚.航空公司实时飞机和机组调配问题的研究[D].中国科学院数学与系统科学研究所博士论文,2002.
[53]中国民用航空总局,航班延误经济补偿指导意见. 2004.
[54]上海航空公司,上海航空公司签派调整手册. 2000.
[55]杨惠.关于《航班延误经济补偿指导意见》的几个问题,中国民航学院学报[J]. 23(1): 49-53,2005.
[56]航班延误原因分析. Available from: www.travel.sohu.com,2008.
[57]中国民航局.关于2009年航班正常情况的通报.2009.
[58] R.G.Busacker,P.G.Gowen, A Procedure for Determining a Family of Minimum Cost Flow Patterns, in Operations Research Office Technical Report 15. Johns Hopking University,1961.
[59] Yu Gang. Operations Research in the Airline Industry:A Decision Support Framework for Airline Flight Cancellations and Delays. Boston,MA: Kluwer Academic Publishers,1997.
[60]白凤.不正常航班的飞机和机组调度研究[D],南京航空航天大学硕士论文,2010.
[61] Mathur Apurva,Paul John,Clarke, How Healthy Is Your operation. Http://Www.Agifors.Org/Index.Jsp. Agifors,2005.
[62] Etschmaier M.M.,Mathaisei D.F.X. Airline Scheduling: An Overview. Transportation science[J].1985:(2).
[63]邢文训,谢金星.现代优化计算方法.北京:清华大学出版社. 2003,247-294,.
[64]卢开澄,卢华明,图论及其应用(第二版).北京:清华大学出版社,1995.
[65]苏治中周亚玲. Delphi开发实用编程200例.北京:中国铁道出版社,2006.
[66]民航局.民航局关于机场收费标准的建议. http://www.caac.gov.cn/,2005.
[67] A.Jarrah,J.T.Diamond. The Problem of Generating Crew Bidlines,Interfaces[J]. 1997,27(4): 49-64,.
[68] Dorigo M,Maniezzo V,Colomi A. The Ant System:Optimization by a Colony of Cooperating Agents,IEEE Transactions on systems,Man,and Cybernetics-Part B[J]. 1996,26(1): 29- 41.
[69] Colorni A,Dorigo M,Manlezzo V. Distributed Optimization by Ant Colonies. in Proceedings of ECAL91-European Conference on Artificial Life. Paris,France: Elsevier Publishing,1991.
[70]张纪会,高齐圣,徐心和.自适应蚁群算法,控制理论与应用[J]. 2000,17(1): l-5.
[71]刘士新,宋健海,唐加福.蚁群最优化模型、算法及应用综述,系统工程学报[J]. 2004, 19(5): 496-502.
[72] Dorigo M,Bonabeau E,Theraulaz G. Ant Algorithms and Stigmer Future Generation Computer Systems[J]. 2000,16: 851-871.
[73] Bonabeau E,Dofigo M,Theraulaz G. Inspiration for Optimization from Social Insect Behaviourl,Nature[J]. 2000,406: 39-42.
[74] Dofigo M,Caro G D,Gambardella L M. Anc Algorithms for Discrete Optimization, Artificial Life[J]. 1999,5(3): 137—17.
[75] Martin M,Chopard B,Albuquerque P. Formation of an Ant Cemetery:Swarm Intelligence of Statistical Accidentl,Future Generation Computer Systems[J]. 2002,18: 893- 901.
[76] Stüezle T,Dorigo M. A Short Convergence Proof for a Class of Ant Colony Optimization Algorithms,IEEE Transactions on Evolutionary Computation[J]. 2002,6(4): 358.-364.
[77]权光日.集合覆盖问题的启发函数算法,软件学报[J]. 1998,9(2): 155-160.
[78] Youshikawa M. A Path-Based Approach to Storage and Retrieval of Xml Documents Using Relational Database.,ACM Trans.Internet Technology[J]. 2001,110-141.
[79] Wen Lun, The Design of Efficient Xml Document Model.In:Proceedings Ofteh First Intemational Conference on Machine Leaming and Cybemetis. 2002.: Beijing. p. 1102-1106.
[80] Mhand Hifi. A Neural Network for the Minimum Set Covering Problem, Chaos, Solitons and Fractals [J]. 2000,11:2079-2089.
[81] Uwe Aickelin. An Indirect Genetic Algorithm for Set Covering Problems,Journal of the Operational Research Society[J]. 2002,53(10): 1118-1126.
[82] Fernando C.Gomes. Experimental Analysis of Approximation Algorithms for the Vertex Cover and Set Covering Problems,Computer&Operations Research[J]. 2006,33(7): 3520-3534.
[83]胡小兵.蚁群优化原理、理论及其应用研究[D],重庆大学博士学位论文.2004.
[84] R Schirru L Machado. The Ant-Q Algorithm Applied to the Nuclear Reload Problem Annals Nuclear Energy[J]. 2002,29(12): 1455-1470.
[85]张纪会吴庆洪,徐心和.具有变异特征的蚁群算法,计算机研究与发展[J]. 1999,36(10):1240-1245.
[86] G. Yu,A Rakshit,N Krishnamurthy. System Operations Advisor: A Real-Time Decision Support System for Managing Airline Operations at United Airlines, Interfaces. 1996:50-58.
[87] Benders.J.F. Partitioning Procedures for Solving Mixed Variables Programming Problems,numerische mathematics[J]. 1962: 4: 238-252.
[88] Mário V F P Silvio B, Sérgio G. A New Bendersdecomposition Approach to Solve Powertransmission Network Design Problems,IEEE Transactions on Power Systems[J]. 2001,16(2): 235-240.
[89]高振,唐立新. Clsp问题的分枝定价算法,东北大学学报(自然科学版)[J]. 2003,24(1): 11-15.
[90]陈宝林.最优化理论与算法.北京:清华大学出版社,2005.
[91]李换琴张可村.工程优化方法及应用.西安:西安交通大学出版社. 282-286,2007.
[92]张光澄.非线性最优化计算方法.北京:高等教育出版社. 217-220,2005.
[93] Stefan Ulbrich Michael Ulbrich Primal-Dual Interior-Point Methods for Pde-Constrained Optimization,Math. Program., Ser. B[J]. 2009,117: 435-485.
[94] Yurii Nesterov. Primal-Dual Subgradient Methods for Convex Problems,Math. Program., Ser. B[J]. 2009,120: 221-259.
[95] Cynthia Barnhart. Column Generation for Solving Huge Integer Programs Operations Research[J]. 1998,46(3): 316-329.
[96] Wilbert E. Wilhelm A. Technical Review of Column Generation in Integer Programming Optimization and Engineering[J]. 2001,2:159-200.
[97]甘应爱等.运筹学.北京:清华大学出版社,2007.
[98] Michel Bierlaire,Niklaus Eggenberg, Column Generation Methods for Disrupted Airline Schedules, in.
[2] Ananda R,Nirup K,Yu G. System Operations Advisor: A Real-Time Decision Support System for Managing Airline Operations at United Airlines,Interfaces[J]. 1996, 2: 50-58.
[3] Jon Petersen Ellis L. Johnson, An Optimization Approach to Airline Integrated Recovery. Georgia Institute of Technology Georgia State,2008.
[4] Barnhart C. Branch-and-Price:Column Generation for Solving Huge Integer Programs,Operations Research[J]. 1998,46(3): 316-329.
[5] D Teodorovic,S Guberinic. Optimal Dispatching Strategy on an Airline Network after a Schedule Perturbation,"European journal of operational research"[J]. 1984,15(2): 178-182.
[6] Teodorovic D. Airline Operations Research. New York::Gordon and breach Science Publishers,1988.
[7] Gershkoff. I, Aircraft Shortage Evaluator, in ORSA/TIMS. joint national meeting. St. Louis:MO,1987.
[8] Ahmad I.Z,Jarrah,Yu Gang. A Decision Support Framework for Airline Flight Cancellations and Delays,Transportation Science[J]. 1993,27: 266-280.
[9] Kanafani Cao J. A Real-Time Decision Support for Integration of Airline Flight Cancellations and Delays, Part I,Transportation Planning and Technology[J]. 1997, 20: 183-199.
[10] Kanafani Cao J. A Real-Time Decision Support for Integration of Airline Flight Cancellations and Delays, Part Ii: Algorithms and Computational Experiments Transportation Planning and Technology[J]. 1997,20: 201-217.
[11] M Argüello, F,J Bard, F,Yu Gang. A Grasp for Aircraft Routing in Response to Groundings and Delays.Journal of Combinatorial Optimization[J]. 1997,5:211-228.
[12] Resende M.G.C. in INFORMS Spring meeting[C]. San Diego, California, USA,1997.
[13] Arguello M.F,Bard J.F,Yu G. Models and Methods for Managing Airline Irregular Operations Aircraft Routing. In : Yu,G.(Ed),Operations Research in the Airline Industry[M]. 1997,1-45.
[14] Yan S.,Yang D. A Decision Support Framework for Handling Schedule Perturbations,Transportation Research, Part B: Methodology[J]. 1996,30(3): 405-419.
[15] Magnanti L.T. Ahuja K.R., Orlin B.J. Network Flows[C]. New Jersey:Prentice Hall,1993.
[16] Young H. Yan S. A Decision Support Framework for Multi-Fleet Routing and Multi-Stop Flight Scheduling,Transportation Research, Part A: Policy and Planning[J]. 1996, 30: 379-398.
[17] Tu Y. Yan S. Multifleet Routing and Multistop Flight Scheduling for Schedule Perturbation,European Journal of Operational Research[J]. 1997,103: 155-169.
[18] Yan S.,Lin C. Airline Scheduling for the Temporary Closure of Airports Transportation science[J]. 1997,31: 72-82.
[19] Bard J.F. Thengvall B.G., Yu G. Multiple Fleet Aircraft Schedule Recovery Following Hub Closures, Transportation research Part A[J]. 2001,35: 289-308.
[20] Bard J.F. Thengvall B.G., Yu G. Balancing User Preferences for Aircraft Schedule Recovery During Irregular Operations IIE Transaction on operations engineering [J]. 2000,32(3): 181-193.
[21] Fisher M.L. The Lagrangian Relaxation Method for Solving Integer Programming Problems Management science[J]. 1981,27: 1-18.
[22] Paulose S. Terrab M. Dynamic Strategic and Tactical Air Traffic Flow Control[C]. in IEEE International Conference on Systems, Man and Cybernetics,1992.
[23] Bard J.F. Thengvall B.G., Yu G. A Bundle Algorithm Approach for the Aircraft Schedule Recovery Problem During Hub Closures,Transportation science[J]. 2003, 37(4): 392-407.
[24] Yu Gang. Operations Research in the Airline Industry[M]. Boston, MA: Kluwer Academic Publishers,1997.
[25]姚韵.航空公司不正常航班管理和调度算法研究[D].南京航空航天大学博士论文.2006.
[26]朱金福.航空运输规划.西安:西北工业大学出版社,2009.
[27]孙宏.航空公司飞机排班问题:模型及算法研究[D].西南交通大学博士论文.2003.
[28]徐肖豪,李雄.航班地面等待模型中的延误成本分析与仿真,南京航空航天大学学[J]. 2006,38(1): 115-121.
[29]谢进一.上海航空公司运行控制体系研究,南京航空航天大学工程硕士学位[D].2006
[30]马正平.机场航班延误优化模型,清华大学学报(自然科学版)[J]. 2004,44(4): 474-477.
[31]田晓东.如何提高航班运行的正常性,中国民用航空[J]. 2004,8: 23-25.
[32]田振才都业富.民航航班延误成本的上升趋势,中国民用航空[J]. 2004,10: 60-62
[33]沙宝亮.航空公司服务质量问题的成因分析,世界标准化与质量管理[J]. 2005,7: 34-36.
[34] E Johnson, L. Lettovsky, G. Nemhauser, R. Pandit,S. Querido, Final Report to Northwest Airlines on the Crew Recovery Problem. 1994, The Logistic Institute, Georgia Institute of Technology, Atlanta, GA.
[35] D Teodorovic,G Stojkovic. Model to Reduce Airline Schedule Disturbances, Journal of Transportation Engineering[J]. 1995,121: 324–331.
[36] D M, Clarke. Irregular Airline Operations: A Review of the State-of-the-Practice in Airline Operations Control Centers,Journal of Air Transport Management[J]. 1998, 4: 67–76.
[37] W. W. Monroe,H. D. Chu, Real-Time Crew Rescheduling at American Airlines[C], Presentation at INFORMS,1995: New Orleans,2003.
[38] G. Stojkovic, F. Soumis, and J. Desrosiers. The Operational Airline Crew Scheduling Problem.Transportation Science [J]. 1998,32: 232–245.
[39] Wei.G,G. Yu. Optimization Model and Algorithm for Crew Management During Airline Irregular Operations,Journal of Combinatorial Optimization[J]. 1997, 1: 305–321.
[40] Lettovsky.L,Johnson E,Nemhauser G..Airline Crew Recovery. Transportation Science[J]. 2000,34: 337-348.
[41] Goutham Ekollu Ahmed Abdelghany, Ram Narasimhan and Khaled Abdelghany. A Proactive Crew Recovery Decision Support Tool for Commercial Airlines During Irregular Operations,Annals of Operations Research[J]. 2004,127: 309-331.
[42] Medard C.P.,N. Sawhney, Airline Crew Scheduling: From Planning to Operations, in Carmen Research and Technology Report. 2004, Carmen Systems AB: Goteborg, Sweden.
[43] Knut Haase Rudiger Nissen. Duty-Period-Based Network Model for Crew Rescheduling in European Airlines,Springer Science + Business Media,[J]. 2006,9: 255–278.
[44] L. Suhl Yufeng Guo, M.P Thiel, Solving the Airline Crew Recovery Problem by a Genetic Algorithm with Local Improvement, in Technical report. WP0408, at DS&OR Lab, University of Paderborn: Germany,2004.
[45] R. Anbil, E. Gelman, B. Patty. Recent Advances in Crew-Pairing Optimization at American Airlines,Interfaces, 1991,2(1): 62-74.
[46] G. Desaulniers, J. Desrosiers, Y. Dumas. Crew Pairing at Air France,European Journal of Operational Research[J]. 1997,97: 220-244.
[47] G. Wei, G. Yu, and M. Song,. Optimization Model and Algorithm for Crew Management During Airline Irregular Operations,Journal of Combinatorial Optimization[J]. 1997,1(3): 305-321.
[48] Teodorovic D.,Stojkovic G. Model to Reduced Airline Schedule Disturbances. Journal of Transportation Engineering[J]. 1995,4: 324-331.
[49]韩健解可新.最优化方法.天津:天津大学出版社,2004.
[50]周志忠.飞行运行实时优化控制研究[D].北京航空航天大博士论文,2001.
[51] L Lettovsky. Airline Operations Recovery: An Optimization Approach 1997.
[52]刘德刚.航空公司实时飞机和机组调配问题的研究[D].中国科学院数学与系统科学研究所博士论文,2002.
[53]中国民用航空总局,航班延误经济补偿指导意见. 2004.
[54]上海航空公司,上海航空公司签派调整手册. 2000.
[55]杨惠.关于《航班延误经济补偿指导意见》的几个问题,中国民航学院学报[J]. 23(1): 49-53,2005.
[56]航班延误原因分析. Available from: www.travel.sohu.com,2008.
[57]中国民航局.关于2009年航班正常情况的通报.2009.
[58] R.G.Busacker,P.G.Gowen, A Procedure for Determining a Family of Minimum Cost Flow Patterns, in Operations Research Office Technical Report 15. Johns Hopking University,1961.
[59] Yu Gang. Operations Research in the Airline Industry:A Decision Support Framework for Airline Flight Cancellations and Delays. Boston,MA: Kluwer Academic Publishers,1997.
[60]白凤.不正常航班的飞机和机组调度研究[D],南京航空航天大学硕士论文,2010.
[61] Mathur Apurva,Paul John,Clarke, How Healthy Is Your operation. Http://Www.Agifors.Org/Index.Jsp. Agifors,2005.
[62] Etschmaier M.M.,Mathaisei D.F.X. Airline Scheduling: An Overview. Transportation science[J].1985:(2).
[63]邢文训,谢金星.现代优化计算方法.北京:清华大学出版社. 2003,247-294,.
[64]卢开澄,卢华明,图论及其应用(第二版).北京:清华大学出版社,1995.
[65]苏治中周亚玲. Delphi开发实用编程200例.北京:中国铁道出版社,2006.
[66]民航局.民航局关于机场收费标准的建议. http://www.caac.gov.cn/,2005.
[67] A.Jarrah,J.T.Diamond. The Problem of Generating Crew Bidlines,Interfaces[J]. 1997,27(4): 49-64,.
[68] Dorigo M,Maniezzo V,Colomi A. The Ant System:Optimization by a Colony of Cooperating Agents,IEEE Transactions on systems,Man,and Cybernetics-Part B[J]. 1996,26(1): 29- 41.
[69] Colorni A,Dorigo M,Manlezzo V. Distributed Optimization by Ant Colonies. in Proceedings of ECAL91-European Conference on Artificial Life. Paris,France: Elsevier Publishing,1991.
[70]张纪会,高齐圣,徐心和.自适应蚁群算法,控制理论与应用[J]. 2000,17(1): l-5.
[71]刘士新,宋健海,唐加福.蚁群最优化模型、算法及应用综述,系统工程学报[J]. 2004, 19(5): 496-502.
[72] Dorigo M,Bonabeau E,Theraulaz G. Ant Algorithms and Stigmer Future Generation Computer Systems[J]. 2000,16: 851-871.
[73] Bonabeau E,Dofigo M,Theraulaz G. Inspiration for Optimization from Social Insect Behaviourl,Nature[J]. 2000,406: 39-42.
[74] Dofigo M,Caro G D,Gambardella L M. Anc Algorithms for Discrete Optimization, Artificial Life[J]. 1999,5(3): 137—17.
[75] Martin M,Chopard B,Albuquerque P. Formation of an Ant Cemetery:Swarm Intelligence of Statistical Accidentl,Future Generation Computer Systems[J]. 2002,18: 893- 901.
[76] Stüezle T,Dorigo M. A Short Convergence Proof for a Class of Ant Colony Optimization Algorithms,IEEE Transactions on Evolutionary Computation[J]. 2002,6(4): 358.-364.
[77]权光日.集合覆盖问题的启发函数算法,软件学报[J]. 1998,9(2): 155-160.
[78] Youshikawa M. A Path-Based Approach to Storage and Retrieval of Xml Documents Using Relational Database.,ACM Trans.Internet Technology[J]. 2001,110-141.
[79] Wen Lun, The Design of Efficient Xml Document Model.In:Proceedings Ofteh First Intemational Conference on Machine Leaming and Cybemetis. 2002.: Beijing. p. 1102-1106.
[80] Mhand Hifi. A Neural Network for the Minimum Set Covering Problem, Chaos, Solitons and Fractals [J]. 2000,11:2079-2089.
[81] Uwe Aickelin. An Indirect Genetic Algorithm for Set Covering Problems,Journal of the Operational Research Society[J]. 2002,53(10): 1118-1126.
[82] Fernando C.Gomes. Experimental Analysis of Approximation Algorithms for the Vertex Cover and Set Covering Problems,Computer&Operations Research[J]. 2006,33(7): 3520-3534.
[83]胡小兵.蚁群优化原理、理论及其应用研究[D],重庆大学博士学位论文.2004.
[84] R Schirru L Machado. The Ant-Q Algorithm Applied to the Nuclear Reload Problem Annals Nuclear Energy[J]. 2002,29(12): 1455-1470.
[85]张纪会吴庆洪,徐心和.具有变异特征的蚁群算法,计算机研究与发展[J]. 1999,36(10):1240-1245.
[86] G. Yu,A Rakshit,N Krishnamurthy. System Operations Advisor: A Real-Time Decision Support System for Managing Airline Operations at United Airlines, Interfaces. 1996:50-58.
[87] Benders.J.F. Partitioning Procedures for Solving Mixed Variables Programming Problems,numerische mathematics[J]. 1962: 4: 238-252.
[88] Mário V F P Silvio B, Sérgio G. A New Bendersdecomposition Approach to Solve Powertransmission Network Design Problems,IEEE Transactions on Power Systems[J]. 2001,16(2): 235-240.
[89]高振,唐立新. Clsp问题的分枝定价算法,东北大学学报(自然科学版)[J]. 2003,24(1): 11-15.
[90]陈宝林.最优化理论与算法.北京:清华大学出版社,2005.
[91]李换琴张可村.工程优化方法及应用.西安:西安交通大学出版社. 282-286,2007.
[92]张光澄.非线性最优化计算方法.北京:高等教育出版社. 217-220,2005.
[93] Stefan Ulbrich Michael Ulbrich Primal-Dual Interior-Point Methods for Pde-Constrained Optimization,Math. Program., Ser. B[J]. 2009,117: 435-485.
[94] Yurii Nesterov. Primal-Dual Subgradient Methods for Convex Problems,Math. Program., Ser. B[J]. 2009,120: 221-259.
[95] Cynthia Barnhart. Column Generation for Solving Huge Integer Programs Operations Research[J]. 1998,46(3): 316-329.
[96] Wilbert E. Wilhelm A. Technical Review of Column Generation in Integer Programming Optimization and Engineering[J]. 2001,2:159-200.
[97]甘应爱等.运筹学.北京:清华大学出版社,2007.
[98] Michel Bierlaire,Niklaus Eggenberg, Column Generation Methods for Disrupted Airline Schedules, in
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |