摘要
航班运行调度是指调度飞机与安排机组人员的生产资源配置工作，以落实航班计划的具体实施。航班运行调度工作一直存在安全与成本的矛盾：首先必须考虑航班运行安全因素，使执行航班飞行任务的飞机能够按规定完成例行检修，且机组人员值勤的飞行时间、值勤时间以及休息时间严格满足有关规章条例要求；在确保运行安全基础上，需要考虑航班运行成本因素，优化航班运行过程中的飞机日利用率与机组资源利用效率。妥善解决这一对矛盾对于航空公司组织生产运营、完成生产计划，以及实现飞机与机组人员等关键资源的优化配置有着至关重要的意义。为此，本文在详细深入分析国内外研究现状和我国航空公司运行特点基础上，结合民航当局有关航班运行管理规章，重点研究航班运行调度过程中的飞机排班问题和机组排班问题。出于降低问题复杂性、提高航班运行调度计划编排效率以及便于局部调整计划考虑，本文将机组排班问题分解成勤务组编排和机组轮班两个子问题分别进行研究。
关于飞机排班问题，建立协同多任务分配方法，为每一架飞机指派每天的航班飞行任务和必要的例行检修任务，在确保航班运行安全基础上，提高飞机日利用率。首先，分析例行检修约束，构建飞机日利用率优化模型。随后，运用分枝定价算法求解。算法引入检修节点、虚拟飞机源节点以及剩余飞行时间的定义，将协同多任务分配过程表示为分区间的生成飞机路径，通过迭代求解由部分飞机路径构成的限制主问题，以及寻找飞机路径以改进目标值的定价问题，获得线性松弛问题的最优解；给出多种分枝方法划分解空间，以删除分数解，生成飞机排班计划。最后以实际航班计划为例，验证所提出的模型与算法的有效性。
关于勤务组编排问题，考虑机组配置多样性，提出协同多任务分配方法，为每一个航段分配合适的机组配置，并严格遵循相应人员配置的机组需满足的编排约束，将航段组织为机组资源利用效率较高的勤务组。首先，根据不同人员配置的机组需满足的休息要求，为每一种机组配置构建相应的连接网络，通过由不同连接网络生成飞行路径实现协同多任务分配。其次，建立满足值勤期限制和飞行时间限制、优化机组资源利用效率的数学模型，使用分枝定价算法求解。并基于遵循时间限制因机组配置不同而各异但有序的特点，提出机组配置修正算子，以提高算法寻优效率。最后，选择与飞机排班问题相同的算例，验证所给的模型和算法的有效性。
关于机组轮班问题，研究机组稳定性最优的轮班计划，将勤务组衔接为机组人员搭配相对固定的轮班任务，以提高机组人员满意度。首先，在分析机组轮班规则基础上，为每一个机型、基地以及机组人员岗位职级构建相应的连接网络，建立以执行勤务组计划所需机组人员数量最少为优化目标的数学模型，采用分枝定价算法求解。随后，给出机组稳定性的定义及其量化方法，针对不同岗位职级分别建立满足轮班任务数量约束，并优化机组稳定性的数学模型，设计启发式迭代算法，编排尽量减少机组人员构成发生变化的机组轮班计划。最后，根据勤务组编排问题的求解结果进行算例验证分析。
本文通过以上三大部分的研究，给出了飞机排班、勤务组编排和机组轮班的调度模型和求解算法，实现了航班运行调度计划编排。
Flight operation scheduling is the allocation of aircraft and crew resources to implement theflight schedule. The contradiction between flight safety and operational cost is a key problem duringflight operation, i.e., to establish a safe environment, aircrafts must accomplish routine maintenancetasks, and crew pairings must satisfy with the rules and regulations of working and rest, and then theutilization rate of aircraft and crew resources should be optimized to reduce the operational cost.Solving the contradiction properly is important for organizing production operations and completingproduction plans. By planning and organizing carefully, the allocation of aircraft and crew resourcescan be optimized. After analyzing the flight operation scheduling studies at home and abroad, theoperating characteristics of airlines, the regulations published by airlines and civil aviationadministration of China, the aircraft scheduling problem and crew scheduling problem during flightoperation scheduling are investigated in this dissertation. According to the complexity of crewscheduling problem and the efficiency of planning and modifying, it is often tackled by breaking intocrew pairing and crew assignment subproblems.
To ensure the safety of flight operation and increase the aircraft utilization, a coordinatedmulti-tasking method is established for aircraft scheduling, which assigns flights and necessaryroutine maintenance tasks for each aircraft. The approach applies branch-and-price algorithm to themathematical model with routine maintenance constraints, aiming to optimize the utilization ofaircrafts. According to the definitions of maintenance node, virtual source node for aircrafts andremaining flight time, the algorithm formulates the assigning flights and routine maintenance tasks asgenerating routes partly. After several iterations of solving a restrict master problem containing asubset of routes and a pricing problem generating new routes with negative reduced cost, an optimalsolution to the linear programming relaxation problem is obtained. To acquire the integer solution,several dedicated branching schemes are proposed. Then the aircraft scheduling is formed. Simulationresults show that the proposed approach can solve the aircraft scheduling problem effectively.
Considering the diversity of crew configuration, the method of coordinated multi-tasking isintroduced for crew pairing problem, which assigns a suitable number of crew members with differentranks for each flight leg, and generates pairings formed by flight legs based on the restrictions andrequirements for the corresponding personnel-allocated crew. As a result, a secure environment isestablished, and the utilization rate of crew resource is optimized. Taking into consideration of the rest period requirements for differently allocated crews, a scheduling network is constructed for each crewconfiguration. Besides, a feasible pairing associated with one type of personnel allocation isrepresented as a route generated from the corresponding network. Thereafter, the approach appliesbranch-and-price algorithm to the cost optimization model with duty period and flight timerestrictions, targeting to optimize the utilization rate of crew resource. According to the different andorderly time restrictions obeyed by differently configured crews, an operator is introduced to assign aproper crew configuration for pairings, which augments the efficiency of optimization. With the sameexamples as aircraft scheduling problem, simulation results show that the crew pairing problem cansolved effectively.
For crew assignment problem, the schedule that is most crew-stable is researched. By generatingtasks consisting of pairings which avoid frequent team changes, the satisfaction of crew members canbe increased. After analyzing regulations and restrictions, a scheduling network is established for eachbase, fleet and crew rank. In addition, the approach applies branch-and-price algorithm to the costoptimization model, aiming to minimize the number of crew members. Subsequently, crew stability isdefined and quantified. With the definition, a mathematical model is established, that is used tomaximize the stability of crew while satisfying the number constraint of tasks. According tobranch-and-price algorithm, a heuristic iterative algorithm is designed to solve this problem. Takingresults of crew pairing problem as examples, the effective of the proposed model and approach areanalyzed.
Accordingly, optimization models and algorithms are established for aircraft scheduling problem,crew pairing problem and crew assignment problem, which enables the planning of flight operationscheduling ultimately.
引文
[1]中国民用航空局.2011年民航行业发展统计公告[EB/OL], http://www.caac.gov.cn/I1/K3/201205/P020120507306080305446.pdf.
[2]国务院.国务院关于促进民航业发展的若干意见. http://www.gov.cn/zwgk/2012-07/12/content_2181497.htm.
[3]朱星辉.航空公司航班计划优化设计研究,[博士学位论文].南京:南京航空航天大学,2009.
[4]中国民用航空局.中国民用航空发展第十二个五年规划[EB/OL], http://www.caac.gov.cn/I1/I2/201105/t20110509_39615.html.
[5]朱新艳.航空公司飞行员流失预警管理研究,[博士学位论文].武汉:武汉理工大学,2010.
[6]中国民用航空局.中国民用航空发展第十一个五年规划[EB/OL], http://www.caac.gov.cn//I1/I2/200612/t20061204_717.html.
[7]孙宏,张培文,胡海青, et al.航空公司机组飞行实力利用率影响因素分析[J].交通运输工程与信息学报,2010,8(2):1-5.
[8]赵秀丽.航空公司不正常航班恢复模型及算法研究,[博士学位论文].南京:南京航空航天大学,2010.
[9]夏洪山.现代航空运输管理[M].北京:科学出版社,2012.
[10]孙宏.航空公司飞机排班问题:模型及算法研究,[博士学位论文].成都:西南交通大学,2003.
[11] Mackworth A K, Freuder E C. The Complexity of some polynomial network consistencyalgorithms for constraint satisfaction problems[J]. Artificial Intelligence,1985,25(1):65-74.
[12] Gopalan R, Talluri K T. The aircraft maintenance routing problem[J]. Operations Research,1998,46(2):260-271.
[13] Talluri K T. The four-day aircraft maintenance routing problem[J]. Transportation Science,1998,32(1):43-53.
[14] Sriram C, Haghani A. An optimization model for aircraft maintenance scheduling andre-assignment[J]. Transportation Research Part A: Policy and Practice,2003,37(1):29-48.
[15] Clarke L, Johnson E, Nemhauser G, et al. The aircraft rotation problem[J]. Annals of OperationsResearch,1997,69(0):33-46.
[16] Guay E L, Desaulniers G, Soumis F. Aircraft routing under different business process[J]. Journalof Air Transport Management,2010,16(5):258-263.
[17]肖东喜,朱金福.飞机排班中航班环的动态构建方法[J].系统工程,2007,25(11):19-25.
[18]李耀华,谭娜,郝贵和.飞机排班航班串编制模型及算法研究[J].系统仿真学报,2008,20(3):612-615.
[19]朱星辉,朱金福,高强.基于约束编程的飞机排班问题研究[J].交通运输系统工程与信息,2011,11(6):151-156.
[20]孙宏,杜文,徐杰.最小费用最大流模型在航班衔接问题中的应用[J].南京航空航天大学学报,2001,33(5):478-481.
[21] Gr nkvist M. Accelerating column generation for aircraft scheduling using constraintpropagation[J]. Computer&Operation Research,2006,33(10):2918-2934.
[22] Gr nkvist M. The tail assignment problem[D]. G teborg: Department of Computer Science andEngineering, Chalmers University of Technology and G teborg University,2005.
[23] Gabteni S, Gr nkvist M. A hybrid column generation and constraint programming optimizer forthe tail assignment problem[A]. Beck J K, Smith B M, Integration of AI and OR Techniques inConstraint Programming for Combinatorial Optimization Problems-Third International Conference,Berlin Germany: Springer-Verlag,,2006:89-103.
[24] Gabteni S, Gr nkvist M. Combining column generation and constraint programming to solve thetail assignment problem[J]. Annals of Operations Research,2009,171(1):61-76.
[25] Gr nkvist M, Kjerrstr m J. Tail assignment in practice[J]. Operations Research Proceedings,2005,2004(5):166-173.
[26] Gr nkvist M. A constraint programming model for tail assigment[A]. Régin J C, Rueher M.Integration of AI and OR Techniques in Constraint Programming for Combinational OptimizationProblems. Berlin Germany: Springer-Verlag,2004:142-156.
[27] Otten L, Gr nkvist M, Dubhashi D. Randomization in constraint programming for airlineplanning[A]. Principles and Practice of Constraint Programming-CP2006. Berlin Germany:Springer-Verlag,2006:406-420.
[28]孙宏,杜文.飞机排班数学规划模型[J].交通运输工程学报.2004,4(3):117-120.
[29]孙宏,杜文.航空公司飞机排班问题的分阶段指派算法[J].系统工程学报.2003,18(2):168-172.
[30]孙宏,杜文.航空公司飞机排班问题的排序模型及算法[J].系统工程理论方法应用.2002,11(3):244-247.
[31]孙宏,文军,徐杰.基于均衡使用要求的飞机排班算法[J].西南交通大学学报.2004,39(5):569-572.
[32]孙宏.应用网络流模型解决航班衔接问题[J].西南交通大学学报.2002,37(2):223-226.
[33]郑芸.航空公司小规模机群飞机排班问题的数学模型和算法研究,[硕士学位论文].天津:中国民用航空学院,2006.
[34]徐海荣,张兴媛,胡盛斌.差值排序算法在飞机排班问题中的应用[J].计算机应用与软件.2010,27(1):81-82.
[35]廖峰.航空公司飞机智能化排班问题的研究,[硕士学位论文].成都:电子科技大学,2010.
[36]李耀华,谭娜.飞机指派问题优化模型及算法研究[J].控制工程.2010,17(2):209-212.
[37]吴东华,夏洪山.基于多目标模糊线性规划求解方法的飞机排班问题研究[J].计算机科学.2012,39(1):234-237.
[38] Moudaini W E, Camino F M. A dynamic approach for aircraft assignment and maintenancescheduling by airlines[J]. Journal of Air Transport Management,2000,6(4):233-237.
[39] Papakostas N, Papachatzakis P, Xanthakis V, et al, Chryssolouris G. An approach to operationalaircraft maintenance planning[J]. Decision Support Systems,2010,48(4):604-612.
[40] Sarac A, Batta R, Rump C M. A branch-and-price approach for operational aircraft maintenancerouting[J]. European Journal of Operational Research,2006,175(3):1850-1869.
[41] Beasley J E, Cao B. A tree search algorithm for the crew scheduling problem[J]. EuropeanJournal of Operation Research,1996,94(3):517-526.
[42] Anbil R, Gelman E, Patty B, et al. Recent advances in crew-pairing optimization at AmericanAirlines[J]. Interfaces,1991,21(1):62-74.
[43] Anbil R, Tanga R, Johnson E L. A global approach to crew-pairing optimization[J]. IBM SystemsJournal,1992,31(1):71-78.
[44] Chu H D, Gelman E, Johnson E L. Solving large scale crew scheduling problems. EuropeanJournal of Operational Research,1997,97(2):260-268.
[45] Anbil R, Forrest J J, Pulleyblank W R. Column generation and the airline crew pairing problem.Documenta Mathematica,1998,3(0):677-686.
[46] Tran V H, Reinelt G, Bock H G. BoxStep methods for crew pairing problems[J]. Optimizationand Engineering,2006,7(1):33-46.
[47] Hjorring C, Hansen J. Column generation with a rule modelling language for airline crewpairing[A]. Proceedings of the34th annual conference of the operational research society of NewZealand, Hamilton New Zealand,1999:133–142.
[48] Subramanian S, Sherali H D. An effective deflected subgradient optimization scheme forimplementing column generation for large-scale airline crew scheduling prolems[J]. INFORMSJournal on Computing,2008,20(4):565-578.
[49] Bornd rfer R, Schelten U, Schlechte T, et al. A column generation approach to airline crewscheduling[R]. Lufthansa Systems Berlin, ZIB-Report05-37,2005.
[50] Yan S, Tung T T, Tu Y P. Optimal construction of airline individual crew pairings[J].Computer&Operations Research,2002,29(4):341-363.
[51] Yan Shangyao, Chang Jeichi. Airline cockpit crew scheduling[J]. European Journal ofOperational Research,2002,136(3):501-511.
[52] Levine D. Application of a hybrid genetic algorithm to airline crew scheduling[J]. Computer andOperations Research,1996,23(6):547-558.
[53] Wedelin D. The design of a0-1integer optimizer and its application in the Carmen system[J].European Journal of Operational Research,1995,87(3):722-730.
[54] Kornilakis H, Stamatopoulos P. Crew pairing optimization with genetic algorithm[A]. Vlahavas IP, Spyropoulos C D, SETN ‘02Proceedings of the Second Hellenic Conference on AI: Methods andApplications of Artificial Intelligence, London UK: Springer-Verlag,2002:109-120.
[55] Weinert E T, Proksch M. Best practice simulated annealing for the airline crew schedulingproblem[J]. Journal of Heuristics,1999,5(4):419-436.
[56]石丽娜,唐小卫.基于二次遗传算法的机组任务配对问题研究[J].计算机工程与设计,2008,29(5):1244-1247.
[57]邵俊.基于遗传算法的机组任务配对研究,[硕士学位论文].南京:南京航空航天大学,2006.
[58]赵正佳.航空公司机组排班计划研究[J].运筹与管理,2011,20(6):106-113.
[59] Karadag A A, Dengiz B. A hybrid approach of heuristic and exact method for crew pairingproblem[A]. Hirosato, Computers&Industrial Engineering, Piscataway USA: IEEE,2010:1-6.
[60] Santos A G, Mateus G R. General hybrid column generation algorithm for crew schedulingproblems using genetic algorithm[A]. Tyrrell, IEEE Congress on Evolutionary Computation,Piscataway USA: IEEE,2009:1799-1806.
[61] Guang-Feng Deng, Lin W T. Ant colony optimization-based algorithm for airline crewscheduling problem[J]. Expert Systems with Applications,2011,38(5):5787-5793.
[62] Kotecha K, Sanghani G, Gambhava N. Genetic algorithm for airline crew scheduling problemusing cost-based uniform crossover[A]. Manandhar S, Applied Computing. Berlin Germany:Springer-Verlag,2004:84-91.
[63] Ozdemir H T, Mohan C K. Flight graph based genetic algorithm for crew scheduling inairlines[J]. Information Sciences,2001,133(3-4):165-173.
[64] Jones D R. Development of an automated airline crew bid generation system[J]. Interfaces,1989,19(4):44-51.
[65] Jarrah A I Z, Diamond J T. The problem of generating crew bidlines[J]. Interfaces,1997,27(4):49-64.
[66] Boubaker K, Desaulniers G, Elhallaoui I. Bidline scheduling with equity by heuristic dynamicconstraint aggregation[J]. Transportation Research Part B: Methodological,2010,44(1):50-61.
[67] Christou I T, Zakarian A, Liu J M, et al. A two-phase genetic algorithm for large-scalebidline-generation problems at Delta Air Lines[J]. Interfaces,1999,29(5):51-65.
[68] Campbell K W, Durfee R B, Hines G S. FedEx generates bid lines using simulated annealing[J].Interfaces,1997,27(2):1-16.
[69] Weir J D, Johnson E L. A three-phase approach to solving the bidline problem[J]. Annals ofOperations Research,2004,127:283-308.
[70] Ryan D M. The solution of massive generalized set partitioning problems in aircrew rostering[J].Journal of the Operational Research Society,1992,43(5):459-467.
[71] Dawid H, K nig J, Strauss C. An enhanced rostering model for airline crews[J].Computers&Operation Research,2001,28(7):671-688.
[72] Mason A J. Elastic constraint branching, the Wedelin/Carmen lagrangian heuristic and integerprogramming for personnel scheduling[J].Annals of Operations Research,2001,108(0):239-276.
[73] Fahle T, Junker U, Karisch S E, et al. Constraint programming based column generation for crewassignment[J]. Journal of Heuristics,2002,8(1):59-81.
[74] Cappanera P, Gallo G. A multicommodity flow approach to the crew rostering problem[J].Operations Research,2004,52(4):583-596.
[75] Anantaram C, Joshi P, Deshpande K, et al. Crew rostering system an expert system forscheduling crew for Indian Airlines[A]. The Ninth Conference on Artificial Intelligence forApplications, Piscataway USA: IEEE,1993:63-70.
[76] Maenhout B, Vanhoucke M. A hybrid scatter search heuristic for personalized crew rostering inthe airline industry[J]. European Journal of Operational Research,2010,206(1):155-167.
[77] Kohl N, Karisch S E. Airline crew rostering: problem types, modeling, and optimization[J].Annals of Operations Research,2004,127(1-4):223-257.
[78] Augustsson L. Partial evaluation in aircraft crew planning[A]. John P G, Charles C, Michael B A,Proceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based ProgramManipulation, New York USA: ACM,1997:127-136.
[79] Hjorring C A, Karisch S E, Kohl N. Carmen systems’ recent advances in crew scheduling[A].Proceedings of the39th Annual AGIFORS Symposium, New Orleans USA,1999:404-420.
[80] Kharraziha H, Ozana M, Apjuth S. Large Scale crew rostering[R]. Carmen Research andTechnology Report CRTR-0305, Carmen Systems AB, Gothenburg, Sweden,2003.
[81] Lu i P, Teodorovi D. Simulated annealing for the multi-objective aircrew rostering problem[J].Transportation Research Part A: Policy and Practice,1999,33(1):19-45.
[82] Teodorovi D, Lu i P. A fuzzy set theory approach to the aircrew rostering problem[J]. Fuzzysets and systems,1998,95(3):261-271.
[83] Moudani W E, Cosenza C A N, Coligny M D, et al. A bi-criterion approach for the airlines crewrostering problem[A]. Kalyanmoy D, Evolutionary Multi-Criterion Optimization. First InternationalConference, Berlin Germany: Springer-Verlag,2001:486-500.
[84] Moudani W E, Cosenza C A N, Camino F M. An intelligent approach for solving the airlinescrew rostering problem[A]. Proceedings ACS/IEEE International Conference on Computer Systemsand Applications, Piscataway USA: IEEE,2001:73-79.
[85] Thiel M P. Team-oriented airline crew rostering for cockpit personnel[J]. Computer-aidedSystems in Public Transport,2008,600(1):91-114.
[86] Thiel M P, Mellouli T, Yufeng Guo. Partially integrated airline crew scheduling for team-orientedrostering[J]. Operations Research Proceedings,2004,2004(1):452-460.
[87]赵宇,许保光.基于飞行品质数据的飞行员调度模型研究[J].中国管理科学,2008,16(4):69-76.
[88]李耀华,谭娜.飞机排班调度中机组指派优化模型及算法研究[J].计算机工程及应用,2008,44(34):243-245.
[89]王红,张蕾.遗传算法在航空公司飞行人员排班中的应用研究[J].计算机工程及应用,2006,10(0):220-222.
[90]李青,张军,张学军.解决排班问题的多目标优化模型及算法研究[J].北京航空航天大学学报,2003,29(9):821-824.
[91]宋静波.基于单亲遗传算法的飞行机组指派技术[J].哈尔滨商业大学学报,2009,25(3):311-313.
[92]张应辉,饶云波,周明天.模拟“退火”算法在多目标航空公司职员排班系统中的应用[J].计算机应用,2006,26(8):2001-2004.
[93]林红,饶云波,李勇.遗传算法在乘务员排班系统中的应用[J].计算机技术与发展,2007,17(1):199-202.
[94]饶云波.航空公司乘务员排班系统的优化算法研究与设计实现,[硕士学位论文].成都:电子科技大学,2006.
[95]陈骏,刘维光. GASA混合算法在航空公司乘务员排班系统中的应用[J].计算机工程与设计,2008,29(1):203-205.
[96] Zhang Yinghui, Rao Yunbo, Zhou mingtian. GASA Hybrid Algorithm Applied in Airline CrewRostering System[J]. Tsinghua Science and Technology,2007,12(S1):255-259.
[97]陈侨.机组乘务员自动排班系统与算法应用,[硕士学位论文].广州:华南理工大学,2011.
[98] Qiao Chen, Lim A, Wenbin Zhu. A greedy heuristic for airline crew rostering: unique challengesin a large airline in China[A]. Mehrotra K G, Mohan C K., Oh J C, Varshney P K, Ali M,24thInternational Conference on Industrial Engineering and Other Applications of Applied IntelligentSystems, Berlin Germany: Springer-Verlag,2011:237-245.
[99]王红,齐雁楠,刘金兰.分阶段飞行人员排班方法的研究[J].交通运输,2006,20:103-107.
[100]王红,齐雁楠.机组人员搭配协调性评价方法的研究[J].计算机工程与设计,2006,27(17):3220-3222.
[101] Byrne J. A preferential bidding system for technical aircrew[A]. Proceeding of the28thAGIFORS Symposium, New Seabury USA: AGIFORS,1988:87-99.
[102] Moore R, Evans J, Ngo H. Computerized tailored blocking[A]. Proceeding of the EighteenthAGIFORS Symposium, Vancouver Canada: AGIFORS,1978:343-361.
[103] Gamache M, Soumis F, Villeneuve D. The preferential bidding system at Air Canada[J].Transportation Science,1998,32(3):246-255.
[104] Gamache M, Hertz A, Ouellet J O. A graph coloring model for a feasibility problem in monthlycrew scheduling with preferential bidding[J]. Computers&Operation Research,2007,34(8):2384-2395.
[105] Achour H, Gamache M, Soumis F, et al. An exact solution approach for the preferential biddingsystem problem in the airline industry[J]. Transportation Science,2007,41(3):354-365.
[106] Teodorovic D,Guberinic S. Optimal dispatching strategy on an airline network after a scheduleperturbation[J]. European Journal of Operational Research,1984,15(2):178-182.
[107] Gershkoff I. Aircraft Shortage Evaluator[A].ORSA/TIMS joint national meeting, St. Louis: MO,1987.
[108] Jarrah A I Z, Yu G, Krishnamurthy N, et al. A decision support framework for airline flightcancellations and delays[J]. Transportation Science,1993,27(3):266-280.
[109] Jia-Ming Cao, Kanafani A. Real-time decision support for integration of airline flightcancellations and delays, part I: mathematical formulations[J]. Transportation Planning andTechnology,1997,20(3):183-199.
[110] Jia-Ming Cao, Kanafani A. Real-time decision support for integration of airline flightcancellations and delays,part II: algorithms and computational experiments[J]. TransportationPlanning and Technology,1997,20:201-217.
[111] Argüello M F, Bard J F, Yu G. A GRASP for aircraft routing in response to groundings anddelays[J]. Journal of Combinatorial Optimization,1997,1(3):211–228.
[112] Benjamin G. T., Yu G., Jonathan F. B. Multiple fleet aircraft schedule recovery following hubclosures[J]. Transportation Research,2001,35(4):289-308.
[113] Liu T K, Jeng C R, Liu Y T, et al, Applications of multi-objective evolutionary algorithm toairline disruption management[A]. IEEE International Conference on Systems, Man and Cybernetics,Piscataway USA: IEEE,2006:4130-4135.
[114] Liu T K, Jeng C R, Chang Y H, Disruption management of an inequality-based multi-fleetairline schedule by a multi-objective genetic algorithm[J]. Transportation Planning and Technology,2008,31(6):613-639.
[115]姚韵.航空公司不正常航班管理和调度算法研究,[博士学位论文].南京:南京航空航天大学,2006.
[116]赵秀丽,朱金福,郭梅.不正常航班延误调度模型及算法[J].系统工程理论与实践,2008,4:129-134.
[117] Lettovsky L, Johnson E L, Nemhauser G L. Airline Crew Recovery[J]. Transportation Science,2000,34(4):337-348.
[118] Yu G, Argüello M, Gao S, et al. A New Era for Crew Recovery at Continental Airlines[J].INTERFACES,2003,33(1):5-22.
[119] Guo Wei, Gang Yu, Mark S. Optimization model and algorithm for crew management duringairline irregular operations[J]. Journal of Combinatorial Optimization,1997,1(3):305-321.
[120] Yufeng Guo, A decision support framework for the airline crew schedule disruptionmanagement with strategy mapping[J]. Operations Research Proceedings,2005,2004(5):158-165.
[121] Abdelghany K F, Abdelghany A F, Ekollu G. An Integrated Decision Support Tool for AirlinesSchedule Recovery during Irregular Operations[J]. European Journal of Operational Research,2008,185(2):825-848.
[122]刘德刚.航空公司实时飞机和机组调配问题的研究,[博士学位论文].北京:中国科学院数学与系统科学研究所,2002.
[123]周志忠.飞行运行控制实时优化研究,[博士学位论文].北京:北京航空航天大学,2001.
[124] Teodorovic D., Stojkovic G. Model to Reduce Airline Scheduling Distubrances[J]. Journal ofTransportation Engineering,1995,121(4):324-331.
[125] Shaw Ching Chang.A new aircrew-scheduling model for short-haul routes[J]. Journal of AirTransport Management,2002,8(4):249-260.
[126] Bard J F, Gang Yu, Argüelles M, Optimizing aircraft routings in response to groundings anddelays[J]. IIE Transactions,2001,33(10):931-947.
[127] Eggenberg N, Salani M, Bierlaire M. Constraint-specific recovery network for solving airlinerecovery problems[J]. Computers&Operations Research,2010,37(6):1014-1026.
[128] Medard C P, Sawhney N. Airline Crew Scheduling from Planning to Operations[J]. EuropeanJournal of Operational Research,2007,16(3):1013-1027.
[129] Ehrgott M, Ryan D M. Constructing Robust Crew Schedules with Bicriteria Optimization[J].Journal of Multi-Criteria Decision Analysis,2002,11(3):139-150.
[130] Lan S, Clarke J P, Barnhart C. Planning for Robust Airline Operations: Optimizing AircraftRoutings and Flight Departure Times to Minimize Passenger Disruptions[J]. Transportation Science,2006,40(1):15-28.
[131] Tekiner H, Birbil S I, Bülbül K. Robust Crew Pairing for Managing Extra Flights[J]. Computers&Operations Research,2009,36(6):2031-2048.
[132]牟德一,王志新,夏群.基于机组延误概率的鲁棒性机组配对问题.系统管理学报,2011,20(2):207-212.
[133] Mercier A, Soumis F. An integrated aircraft routing, crew scheduling and flight retimingmodel[J]. Computer&Operations Research,2007,34(8):2251-2265.
[134] Weide O, Ryan D, Ehrgott M. An iterative approach to robust and integrated aircraft routing andcrew scheduling[J]. Computer&Operations Research,2010,37(5):833-844.
[135] Saddoune M, Desaulniers G, Elhallaoui I, et al. Integrated airline crew scheduling: Abi-dynamic constraint aggregation method using neighborhoods[J]. European Journal of OperationalResearch,2011,212(3):445-454.
[136]孙宏,张翔,徐杰.航空公司机队集中调度理论研究[J].中国管理科学,2008, Vol.16, No.1:86-89.
[137]张宁.中国民用航空公司战略成本分析,[硕士学位论文].青岛:中国海洋大学,2007.
[138]许宏.浅析机队配置因素[J].管理,1998,197:59-60.
[139]朱金福.航空运输规划[M].西安:西北工业大学出版社,2009.
[140] Barnhart C, Johnson E L, Nemhauser G L, et al. Branch-and-Price: column generation forsolving huge integer programs[J]. Operations Research,1998,46(3):316-329.
[141]钱颂迪.运筹学[M].北京:清华大学出版社,2000.
[142] Martins E Q V, Santos J L E. The labeling algorithm for the multiobjective shortest pathproblem[R]. CISUC Technical Report TR99/005, University of Coimbra, Coimbra, Portugal,1999.
[143] Ioachim I, Gélinas S, Soumis F, Desrosiers J. A dynamic programming algorithm for theshortest path poblem with time windows and linear node costs[J]. Networks,1998,31(3):193-204.
[144] Falkner J C, Ryan D M. A bus crew scheduling system using a set partitioning model[J]. ASIAPACIFIC J. OPER. RES.,1987,4(1):39-56.
[145] Ryan D M, Foster B A. An integer programming approach to scheduling[A]. Wren A, ComputerScheduling of Public Transport Urban Passenger Vehicle and Crew Scheduling, North-Holland:Amsterdam,1981:269-280.
[146]王莹.动车组运用计划和乘务计划的优化方法研究,[博士学位论文].北京:北京交通大学,2009.
[147]王莹,刘军,苗建瑞.基于列生成算法的动车组检修计划优化[J].中国铁道科学,2010,31(2):115-120.
[148]王莹,刘军,苗建瑞.客运专线乘务交路计划编排的优化模型与算法[J].铁道学报,2009,31(1):15-19.
[149]李晨.带有协作机制的车辆路径问题的分支定价算法,[硕士学位论文].天津:南开大学,2010.
[150]王健.公交司售人员排班集合覆盖问题的求解算法研究与实现,[硕士学位论文].北京:北京交通大学,2011.
[151] Shi N. K constrained shortest path problem[J]. IEEE Transactions on Automation Science andEngineering,2010,7(1):15-23.
[152]叶耀华,钟鬼,朱屹容.一种市内邮件转运问题的模型与算法[J].运筹学学报,1998,2(4):91-94.
[153]郭冬芬,李铁克.基于约束满足的车间调度算法综述[J].计算机集成制造系统,2007,13(1):117-125.
[154]李铁克,郭冬芬.基于约束满足的热轧批量计划模型与算法[J].控制与决策,2007,22(4):389-393.
[155]李远,彭辉,沈林成.协同任务规划中基于约束满足的资源冲突检测与消解[J].系统工程与电子技术,2009,31(4):868-873.
[156]姚向华,施仁.约束编程及其在产品配置器中的应用[J].计算机应用与软件,2004,21(3):36-37.
[157]姜英新,孙吉贵.约束满足问题求解及ILOG SOLVER系统简介[J].吉林大学学报(理学版),2002,1:53-60.
[158]孙吉贵,朱兴军,张永刚等.最先失败原则的约束传播算法[J].小型微型计算机系统,2008,29(4):678-681.
[159]中国民用航空局. CCAR121大飞机承运人合格审定规则.北京:2010.
[160]孙宏.航空公司组织与计划[M].成都:西南交通大学出版社,2008.