航空公司飞机排班问题：模型及算法研究
|
摘要
航空公司的生产计划编制是一项非常艰巨而重要的工作，其实质在于通过周密的组织和精确的计划，实现各生产资源要素的优化配置，它的质量和效率关系到生产运营的安全、正常和效益。本文在深入分析当前国内各航空公司生产计划工作现状的基础上，选择了飞机排班计划作为研究课题，通过系统分析飞机排班工作的流程和要求，提出了描述飞机排班问题的数学模型。由于该问题是多目标、非线性的，因此寻找一种统一的能够适应各种具体要求，并且满足工程应用需要的多项式算法存在理论上和技术上的困难。为此论文在借鉴手工编制排班计划经验的基础上，将一个具体的飞机排班问题，归结为三种典型排班模式中的一种，即：基于飞机调度指令要求的排班问题，基于飞机使用均衡要求的排班问题和基于最少需用飞机数的排班问题，对于每种典型的飞机排班模式，在对次要的约束条件进行简化、松驰的基础上构造出相应的能够满足工程应用要求的启发式算法，并分析了算法的复杂性。该项研究为研制飞机排班决策支持系统软件奠定了理论基础。
论文的主要创新工作在：
1．根据当前国内航空公司的运营组织模式特点，以及飞机排班工作的实际需求，提出了描述飞机排班问题的数学模型，并通过将一般形式的飞机排班问题归结为三种典型的飞机排班模式，构造出相应的启发式算法，填补了国内在此领域的研究空白。
2．在解决基于飞机调度指令要求的飞机排班问题时，本文提出的分阶段指派算法较好地克服了标号算法的缺陷，该算法能普遍地应用于处理类似的固定工件排序问题。
3．在解决使飞机均衡使用的飞机排班问题时，本文利用航班节的网络模型将原问题转化为一个使目标函数最小的航班节编组问题，在此基础上构造了一个模拟退火算法。
4．在解决最少需用飞机数要求的飞机排班问题时，本文将寻找航班节衔接方案问题，描述成一个二部图的匹配问题，进而通过解两个二部图的最
小权最大匹配，寻找需用飞机数最少的飞机调度方案。
Airline operational planning is very hard and important work, which quality and efficiency is concerned with the safety and benefit of airline operation. The essence of this work is optimizing the configuration of primary airline resources by precise organizing and planning. Based on analyzing the status of domestic airline operational planning system, this dissertation determines the study subject as Tail-Number-Assignment (TNA) Problem. Firstly, a 0-1 Integer programming mathematical model is constructed to describe Tail-Number-Assigning work happened in domestic airline, since the problem is NPC, a unified polynomial algorithm which satisfies engineering requirement is unavailable. Illuminated by the practical experience, a specific TNA problem is classified into one of three typical TNA modes: TNA based on fleet dispatching commands, TNA based on fleet balance application, TNA based on minimum fleet requirement; Secondly, by simplifying and relaxing some minor constraints, corresponding mathematical models and heuristic algorithms are reconstructed for each typical TNA mode; Finally, computing complexities are discussed. All these research sets a primary foundation for developing Airline Tail Number Assigning System software.
The primary innovations are as follows:
1. On the basis of operational characters of domestic airline by now, a mathematical model describing TNA problem is constructed, and by classifying a specific TNA problem into one of three typical TNA modes, corresponding heuristic algorithms are reconstructed. This research supplies a domestic gap in this field.
2. When solving the TNA problem based on fleet dispatching commands, a Stage-Assignment algorithm is build to overcome the defect of FIFO algorithm, which can be widely applied to cope with fixed job scheduling problem.
3. When solving the TNA problem based on fleet balance application, a
flight pairing network model is build, by which the primary problem transferred to a directed path decomposition problem to minimize target function, and a simulated annealing algorithm is constructed.
4. When solving the TNA problem based on minimum fleet requirement, a bipartite graph describing flight-pairing-link property is constructed, by which the primary problem is transferred to two weighted bipartite matching.
论文的主要创新工作在：
1．根据当前国内航空公司的运营组织模式特点，以及飞机排班工作的实际需求，提出了描述飞机排班问题的数学模型，并通过将一般形式的飞机排班问题归结为三种典型的飞机排班模式，构造出相应的启发式算法，填补了国内在此领域的研究空白。
2．在解决基于飞机调度指令要求的飞机排班问题时，本文提出的分阶段指派算法较好地克服了标号算法的缺陷，该算法能普遍地应用于处理类似的固定工件排序问题。
3．在解决使飞机均衡使用的飞机排班问题时，本文利用航班节的网络模型将原问题转化为一个使目标函数最小的航班节编组问题，在此基础上构造了一个模拟退火算法。
4．在解决最少需用飞机数要求的飞机排班问题时，本文将寻找航班节衔接方案问题，描述成一个二部图的匹配问题，进而通过解两个二部图的最
小权最大匹配，寻找需用飞机数最少的飞机调度方案。
Airline operational planning is very hard and important work, which quality and efficiency is concerned with the safety and benefit of airline operation. The essence of this work is optimizing the configuration of primary airline resources by precise organizing and planning. Based on analyzing the status of domestic airline operational planning system, this dissertation determines the study subject as Tail-Number-Assignment (TNA) Problem. Firstly, a 0-1 Integer programming mathematical model is constructed to describe Tail-Number-Assigning work happened in domestic airline, since the problem is NPC, a unified polynomial algorithm which satisfies engineering requirement is unavailable. Illuminated by the practical experience, a specific TNA problem is classified into one of three typical TNA modes: TNA based on fleet dispatching commands, TNA based on fleet balance application, TNA based on minimum fleet requirement; Secondly, by simplifying and relaxing some minor constraints, corresponding mathematical models and heuristic algorithms are reconstructed for each typical TNA mode; Finally, computing complexities are discussed. All these research sets a primary foundation for developing Airline Tail Number Assigning System software.
The primary innovations are as follows:
1. On the basis of operational characters of domestic airline by now, a mathematical model describing TNA problem is constructed, and by classifying a specific TNA problem into one of three typical TNA modes, corresponding heuristic algorithms are reconstructed. This research supplies a domestic gap in this field.
2. When solving the TNA problem based on fleet dispatching commands, a Stage-Assignment algorithm is build to overcome the defect of FIFO algorithm, which can be widely applied to cope with fixed job scheduling problem.
3. When solving the TNA problem based on fleet balance application, a
flight pairing network model is build, by which the primary problem transferred to a directed path decomposition problem to minimize target function, and a simulated annealing algorithm is constructed.
4. When solving the TNA problem based on minimum fleet requirement, a bipartite graph describing flight-pairing-link property is constructed, by which the primary problem is transferred to two weighted bipartite matching.
引文
[1] 张梅倩．现代航空维修理论．中国民航广州中等专业学校．广州．1988
[2] 《民用飞机适航管理》编辑委员会．民用飞机适航管理．国防工业出版社．北京．1991
[3] 张水生．民用航空维修工程管理概论．中国民航出版社．北京．1999
[4] 耿淑香．航空公司运营管理方略．中国民航出版社．北京．2000
[5] 扬思梁．最盈利的管理方式—收益管理．航空工业出版社．北京．2000
[6] [日]太田正树．航空运输经济学．航空工业出版社．北京．1988
[7] [加]钟彼得著，韩伯裳等译．管理科学(运筹学)战略角度的审视．机械工业出版社．北京．2000
[8] 王朝瑞．图论．北京理工大学出版社．北京．19971998
[9] 《现代应用数学手册》编委会。现代应用数学手册，清华大学出版社．北京．
[10] 夏洪山，等编著．现代航空管理．人民交通出版社．北京．2000
[11] 杨保安，白思俊．网络在计划管理中的应用．航空工业出版社．北京．1989
[12] 刘家壮，王建方．网络最优化．华中工学院出版社．武昌．1987
[13] 张文海．DELPHI语言程序设计．电子工业出版社．北京．2001
[14] 邢文训，谢金星．现代优化计算方法．清华大学出版社．北京．1999
[15] 谢金星，邢文训．网络优化．清华大学出版社．北京．2000
[16] 林诒勋．线性规划与网络流．河南大学出版社．开封．1996
[17] 刘振宏，蔡茂诚译．组合最优化：算法和复杂性．清华大学出版社．北京．1986
[18] 孙宏．运用网络流模型解决航班衔接问题．西南交通大学学报，2002，Vol．38，223-226
[19] 孙宏，杜文．航空公司飞机排班问题的排序模型及算法．系统工程理论方法应用，2002，Vol．3，244-247
[20] 孙宏．航空公司飞机排班问题的分阶段指派算法．系统工程学报．2003．Vol．2．168-172
[21] 孙宏．用最小费用最大流模型解决航班衔接问题。南京航空航天大学学
报，2001，Vol．5，
[22] 唐国春．排序问题的定义分类和在国内的某些研究进展．运筹学杂志，1990，Vol．46，146-156
[23] 李文权，张志立．问题的难与易—论 P，NP及NPC．许昌师专学报，1993，Vol．4，44-48
[24] Smith, B., Leeimkuhler, J., et al. Yield management at American airlines. Interface, 1991, Vol. 22, 8-31
[25] 邓俊强，林诒勋．排序问题1‖U_j的对偶算法及全部解．排序通讯，1996，Vol．10，10-11
[26] 孙世杰．排序问题的简短历史和国外发展动态．排序通讯，1991，Vol．1，10-11
[27] Belobaba, P.P. Air travel demand and airline seat inventory management. Ph.D. disss., Massachusetts Institute of Technology(MIT),1987
[28] Belobaba, P.P. Application of probabilistic decision model to airline seat inventory control. Operational Research, 1989, Vol. 37, 183-197
[29] Kabbnai, N.M. and Patty, B.W. Aircraft routing at American airline. In proceeding of the 32~nd Annual Symposium of AGIFORS, Budapest, Hungary, 1992
[30] Gertsbakh, I. And Stern, H.I. Minimal resources for fixed and variable job schedules. Operational Research, 1978, Vol. 26, 68-75
[31] Arkin, E.M., Silverberg, E.B. Scheduling jobs with fixed start and end times. Discrete Applied mathematics, 1987, Vol.18, 1-8
[32] Jansen K. An approximation algorithm for the license and shift class design problem. European J. Oper. Res., 1994, Vol.73, 127-131
[33] Kolen A.W.J. and Kroon L.G. On the computational complexity of (maximum) shift class scheduling. European J. Oper. Res., 1993, Vol. 64,138-151
[34] Gopalan, R. The Aircraft Maintenance Routing Problem. Operational Research,1998, Vol. 46(2), 260-271
[35] ralluri, K. r. The Four-day aircraft maintenance routing problem.
Transportation Science, 1998, Transp. Sci. Vol. 31
[36] Talluri, K. T. SwappingApplications in a Daily Fleet Assignment. Transportation Science, 1996, Vol. 30
[37] Gupta, U.I., Lee, D.T. and Leung, J.Y.T. An optimal solution for the channel-assignment problem. IEEE Transactions Computer, 1979,C-28, 807-810
[38] Fischetti, M., Martello, M.S. and Toth, P. Approximation algorithms for fixed job schedule problems. Operational Research, 1992, Vol. 40, 96-108
[39] Fischetti M., Martello S. and P. Toth. The fixed job scheduling problem with spread-time constraints. Operational Research. 1987, Vol. 35, 849-858
[40] Fischetti M., Martello S. and Toth P.. The fixed job scheduling problem with working-time constraints. Oprational Research. 1989, Vol. 37, 395-403
[41] Gu, Z., Jhnson, E.L., Nemhauser, G.L. and Wang, Y. Some properties of the fleet assignment problem. Opns. Res. Lett. 1994, Vol. 15, 59-71
[42] Gabrel V. Scheduling jobs within time windows on identical parallel machines: new model and algorithms. European Journal Operational Research. 1995, Vol. 83, 320-329
[43] Abara, J. Applying Integer Programming to the Fleet Assignment Problem. Interface, 1989, Vol. 19, 20-28
[44] Clarke, L.W., Hane C.A., E.L. Johnson and G. L. Nemhauser. Maintenance and Crew Considerations in Fleet Assignment. Transportation Science. 1996, Vol. 30, 249-260
[45] Clarke, L.W., E.L. Johnson and G.L. Nemhauser. The Aircraft Rotation Problem. Annual Operational Research Mathematical Industrial System. 1997, Vol. Ⅱ(69), 33-46
[46] Desaulniers, G., J. Desrosiers, I. Ioachim, M. Solomon. Daily Aircraft Routing and Scheduling. GERAD. 1994b
[47] Feo, T.A.,J.F. Bard.. Flight Scheduling and Maintenance Base Planning. Management Science. 1989, Vol. 35, 1415-1432
[48] Gopalan, R., K. Talluri. Mathematical Models in Airline Schedule
Planning: a Survey. Ann. Oper. Res. Math. Ind. Syst., 1997, Vol. Ⅱ(69),115-130
[49] Hane, C.A., C. Barnhart, E.L. Johnson, R.E. Marsten and G.L. Nemhauser. The Fleet Assignment Problem: Solving Large-Scale Integer Programming. Mathematical Programming. 1995, Vol.70,211-232
[50] Cynthia Barnhart, Natashia L., Lloyd W. Clarke. Flight String Model for Aircraft Fleeting and Routing. Transportation Science. 1998, Vol. 32(5), 208-219
[51] Ahuja, R.K., Magnanti, T.L. and Orlin, J.B. Network flow: theory, algorithms, and applications. Prentice Hall, Englewood Cliffs, N.J. 1993
[52] Ford, L.R., Dulkerson, D.R. Flow in network. New Jersey, Princeton University Press. 1962
[53] Berge, M.E. and Hopperstad, C.A. Demand driven dispatch: a method for dynamic aircraft capacity assignment, model and algorithms. Operational Research. 1993, Vol. 41,153-168
[54] Daskin, M.S. and Panayotopoulos, N.D. A lagrangian relaxation approach to assigning aircraft to routes in hub-and spoke networks. Transportation Science. 1989, Vol. 23, 91-99
[55] Subramanian, R., Scheff, R.P., Quillinan, Jr.J.D. and Wiper, D.S. Coldstart:fleet assignment at Delta Airlines. Interfaces. 1994,Vol. 24, 104-119
[56] Brian, R, Cynthia, B., Tim, K. and Ahmad, J. Airline fleet assignment with time windows. Transportation Science. 2000,Vol. 34(1),1-20
[57] Levin, A. Scheduling and fleet routing models for transportation systems. Transportation Science. 1971, Vol. 5,232-255
[58] Ryan, D.M. The solution of massive generalized set partitioning problems inaircrew rostering. J. Oper. Res. Soc. 1992, Vol. 43,459-467
[59] Ryan, D.M. and Garner, K.M. The solution of air-crew scheduling problems for air new zealand. Proc. of the 21st Annu. Conf. Of O.R.S.N.Z.1985, 42-48
[60] Marsten, R.E. Muller, M.R. and Killion, C.L. Crew planning at
flying Tige: a successful application of integer programming. Networks.1981, Vol. Ⅱ, 165-177
[61] Marsten, R.E. and Shepardson, F, Exact solution of crew scheduling problems using set partitioning model:recent successful applications. Management Science. 1979, Vol. 25, 1175-1183
[62] Hoffman, K.L. and Padberg, M. Solving airline crew scheduling problems by branch-and-cut. Management Science. 1993, Vol. 39, 657-682
[63] Graves, G.W., Mcbridge, R.D., Gershkoff, I. And Andersion, D. Flight crew scheduling. Management Science. 1993, Vol. 39, 736-745
[64] Gamache, M., Soumis, F. and Desrosiers, J. A column generation approach for large scale aircrew rostering problem. Oper. Res. 1998a,Vol. 39,657-682
[65] Anbil, R., Zanga, R. and Johnson, E.J. A global approach to crew-pairing optimization. IBM Syst. J. 1992, Vol. 31, 71-78
[66] Monroe, W.W. and Chu, H.D. Real-time crew rescheduling at American airlines. Presentation at INFORMS New Orleans. 1995
[67] Ryan, M. and Falkner, J.C. A bus crew scheduling system using a set partitioning model. Asia Pacific J. Oper. Res. 1987, Vol. 4, 39-56
[68] Clarke, M.D. Solving the problem of irregular airline operations. Presentation at INFORMS New Orleans. 1995
[69] Chu, H.D., Gelman, E. and Johnson, E.L. Solving large scale crew scheduling problem, Eur. J. Oper. Res. 1997, Vol. 97, 260-268
[70] Anbil, R., Gelman E., Patty, B. and Tanga, R. Recent advances in crew-pairing optimization at American airlines. Interface. 1991,Vol. 21, 62-74
[71] Cynthia Barnhart, Natashia, L., Lloyd W. Clarke. Flight String Model for Aircraft Fleeting and Routing. Transportation Science. 1998, Vol. 32(5), 208-219
[72] Garey, M.R. and Johnson, D.S. Computers and intractability: a guide to NP-completeness. W.H. Freeman & Company, San Francisco, 1978
[73] Papadimitriou, C.H. andSteiglitz, K. Combinatorial optimization: algorithms and complexity. Prentice-Hall, inc., New Jersey, 1982
[74] Vance, P.H., Barnhart, C., Johnson, E.L. and Nemhauser, G.L.
Airline crew scheduling: a new formulation and decomposition algorithm. Oper. Res. 1997,Vol. 45, 188-200
[75] Baker, E.K. Efficient heuristic algorithms for the weighted set covering problem. Computers Oper. Res. 1981, Vol. 8, 303-310
[76] Barnhart, C., Hatay, L. and Johnson, E.L. Deadhead selection for the long-haul crew pairing problem. Oper. Res. 1995, Vol. 43, 491-499
[77] Desrosiers, J., Dumas, Y., Solomon, M.M. and Soumis, F. Time constrained routing and scheduling. Handbooks in Operations Research and Management Science, Network Routing, 1995, Vol. 8, 35-139
[78] Metropolis, N., Rosenbluth, A. and Rosenbluth, M. Equation of state calculation by fast computing machines. Journal of Chemical Physics, 1953, Vol. 21, 1087-1092
[79] Kirkptrick, S., Gelatt, Jr.C.D. and Vecchi, M.P. Optimization by simulated annealing. Science, 1983, Vol. 220, 671-680
[80] Aarts, E.H.L. and Laarhoven, P.J.M. Simulated annealing: theory and application. D Reidel Publishing Company. Dordrecht. 1987
[81] Ackley, D.H., Hinton, G.E. and Seinowski, T.J. A learning algorithm for Boltzmann machines. Cognitive Science. 1985, Vol. 9,147-169
[82] Seneta, E. Non-negative matrices and markov chains. 2nd Edition. Springer Verlag. New York. 1981
[83] Geman, S. and Geman, D. Stochastic relaxation, Gibbs distributions, and the Bayaesian restoration of images. In: IEEE Proc. Pattern Analysis and Machine Intelligence, PAMI-6, 1984, 721-741
[84] Anily, S.F. Probabilistic analysis of simulated annealing methods. Graduate School of Busuness, Golumbia University, New York, Preprint.1985
[85] Lundy, M. and Mees, A. Convergence of an annealing algorithm. Mathematical Programming, 1986, Vol. 34, 111-124
[86] Huang, M.D., Romeo, F. and Sangiovanni-Vincentelli, A.L. An efficient general cooling schedule for simulated annealing. In: Proceeding of IEEE Int. Conference on Computer-Aided design. Santa Clara. 1986
[87] Lai, K.K. and Chan, J.W.M. Developing a simulated annealing algorithm for the cutting stock problem. Computers Ind. Engng. 1996
[88] Isaacson, D. and Madsen, R. Markov Chains. Wiley. New York. 1976
[89] 盛骤．概率论与数理统计．第二版，高等教育出版社．北京．1990
[90] 李文权．博士学位论文：铁路区段站日工作计划优化模型及其算法的研究．西南交通大学．1999年
[91] 林诒勋．同顺序m×n排序问题的动态规划方法．数学进展，1986，Vol．4，337-346
[92] 林诒勋．最小化误时损失的一台设备排序问题．应用数学学报，1983，Vol．21．228-235
[93] 俞文此．工件集合上的某种全序及其应用．应用数学与计算数学学报，1991，Vol．5，66-71
[94] 马振华．现代应用数学手册——运筹学与最优化理论卷．清华大学出版社．北京．1998．
[95] 李文权，王炜，杜文，林诒勋．铁路技术站调机运用模型及算法．系统工程学报，2000，Vol．15(3)，66-71
[96] 林尧瑞，张钹，石纯一．专家系统原理与实践．清华大学出版社．北京．1988
[97] 刘军．一类复杂规划问题的分层规划方法．北方交通大学学报，1995，Vol．19(3)
[98] 孙宏，杜文．航空公司航班衔接问题的模型及算法．四川工业学院学报，2001，Vol．22(2)，20-22
[99] 郭耀煌．运筹学原理与方法．西南交通大学出版社．成都．1994
[100] 孙宏，文军，罗风娥．航班运营飞行计划．民航飞行学院出版社．成都．2002
[101] 中国民用航空局．航空承运人运行合格审定规则．中国民用航空局．北京．1999
[102] 中国民用航空局．中国民用航空飞行人员训练管理规定．中国民用航空局．北京．1998
[103] 中国民用航空局．中国民用航空器适航管理条例．中国民用航空局．北京．1996
[104] H．P．威廉斯著，孟国璧等译．数学规划模型建立与计算机应用．国防工业出版社．北京．1991
[105] 林诒勋．动态规划与序贯最优化．河南大学出版社．开封．1996
[106] 吴文虎，王建德．实用算法的分析与程序设计．电子工业出版社．北京．1998
[2] 《民用飞机适航管理》编辑委员会．民用飞机适航管理．国防工业出版社．北京．1991
[3] 张水生．民用航空维修工程管理概论．中国民航出版社．北京．1999
[4] 耿淑香．航空公司运营管理方略．中国民航出版社．北京．2000
[5] 扬思梁．最盈利的管理方式—收益管理．航空工业出版社．北京．2000
[6] [日]太田正树．航空运输经济学．航空工业出版社．北京．1988
[7] [加]钟彼得著，韩伯裳等译．管理科学(运筹学)战略角度的审视．机械工业出版社．北京．2000
[8] 王朝瑞．图论．北京理工大学出版社．北京．19971998
[9] 《现代应用数学手册》编委会。现代应用数学手册，清华大学出版社．北京．
[10] 夏洪山，等编著．现代航空管理．人民交通出版社．北京．2000
[11] 杨保安，白思俊．网络在计划管理中的应用．航空工业出版社．北京．1989
[12] 刘家壮，王建方．网络最优化．华中工学院出版社．武昌．1987
[13] 张文海．DELPHI语言程序设计．电子工业出版社．北京．2001
[14] 邢文训，谢金星．现代优化计算方法．清华大学出版社．北京．1999
[15] 谢金星，邢文训．网络优化．清华大学出版社．北京．2000
[16] 林诒勋．线性规划与网络流．河南大学出版社．开封．1996
[17] 刘振宏，蔡茂诚译．组合最优化：算法和复杂性．清华大学出版社．北京．1986
[18] 孙宏．运用网络流模型解决航班衔接问题．西南交通大学学报，2002，Vol．38，223-226
[19] 孙宏，杜文．航空公司飞机排班问题的排序模型及算法．系统工程理论方法应用，2002，Vol．3，244-247
[20] 孙宏．航空公司飞机排班问题的分阶段指派算法．系统工程学报．2003．Vol．2．168-172
[21] 孙宏．用最小费用最大流模型解决航班衔接问题。南京航空航天大学学
报，2001，Vol．5，
[22] 唐国春．排序问题的定义分类和在国内的某些研究进展．运筹学杂志，1990，Vol．46，146-156
[23] 李文权，张志立．问题的难与易—论 P，NP及NPC．许昌师专学报，1993，Vol．4，44-48
[24] Smith, B., Leeimkuhler, J., et al. Yield management at American airlines. Interface, 1991, Vol. 22, 8-31
[25] 邓俊强，林诒勋．排序问题1‖U_j的对偶算法及全部解．排序通讯，1996，Vol．10，10-11
[26] 孙世杰．排序问题的简短历史和国外发展动态．排序通讯，1991，Vol．1，10-11
[27] Belobaba, P.P. Air travel demand and airline seat inventory management. Ph.D. disss., Massachusetts Institute of Technology(MIT),1987
[28] Belobaba, P.P. Application of probabilistic decision model to airline seat inventory control. Operational Research, 1989, Vol. 37, 183-197
[29] Kabbnai, N.M. and Patty, B.W. Aircraft routing at American airline. In proceeding of the 32~nd Annual Symposium of AGIFORS, Budapest, Hungary, 1992
[30] Gertsbakh, I. And Stern, H.I. Minimal resources for fixed and variable job schedules. Operational Research, 1978, Vol. 26, 68-75
[31] Arkin, E.M., Silverberg, E.B. Scheduling jobs with fixed start and end times. Discrete Applied mathematics, 1987, Vol.18, 1-8
[32] Jansen K. An approximation algorithm for the license and shift class design problem. European J. Oper. Res., 1994, Vol.73, 127-131
[33] Kolen A.W.J. and Kroon L.G. On the computational complexity of (maximum) shift class scheduling. European J. Oper. Res., 1993, Vol. 64,138-151
[34] Gopalan, R. The Aircraft Maintenance Routing Problem. Operational Research,1998, Vol. 46(2), 260-271
[35] ralluri, K. r. The Four-day aircraft maintenance routing problem.
Transportation Science, 1998, Transp. Sci. Vol. 31
[36] Talluri, K. T. SwappingApplications in a Daily Fleet Assignment. Transportation Science, 1996, Vol. 30
[37] Gupta, U.I., Lee, D.T. and Leung, J.Y.T. An optimal solution for the channel-assignment problem. IEEE Transactions Computer, 1979,C-28, 807-810
[38] Fischetti, M., Martello, M.S. and Toth, P. Approximation algorithms for fixed job schedule problems. Operational Research, 1992, Vol. 40, 96-108
[39] Fischetti M., Martello S. and P. Toth. The fixed job scheduling problem with spread-time constraints. Operational Research. 1987, Vol. 35, 849-858
[40] Fischetti M., Martello S. and Toth P.. The fixed job scheduling problem with working-time constraints. Oprational Research. 1989, Vol. 37, 395-403
[41] Gu, Z., Jhnson, E.L., Nemhauser, G.L. and Wang, Y. Some properties of the fleet assignment problem. Opns. Res. Lett. 1994, Vol. 15, 59-71
[42] Gabrel V. Scheduling jobs within time windows on identical parallel machines: new model and algorithms. European Journal Operational Research. 1995, Vol. 83, 320-329
[43] Abara, J. Applying Integer Programming to the Fleet Assignment Problem. Interface, 1989, Vol. 19, 20-28
[44] Clarke, L.W., Hane C.A., E.L. Johnson and G. L. Nemhauser. Maintenance and Crew Considerations in Fleet Assignment. Transportation Science. 1996, Vol. 30, 249-260
[45] Clarke, L.W., E.L. Johnson and G.L. Nemhauser. The Aircraft Rotation Problem. Annual Operational Research Mathematical Industrial System. 1997, Vol. Ⅱ(69), 33-46
[46] Desaulniers, G., J. Desrosiers, I. Ioachim, M. Solomon. Daily Aircraft Routing and Scheduling. GERAD. 1994b
[47] Feo, T.A.,J.F. Bard.. Flight Scheduling and Maintenance Base Planning. Management Science. 1989, Vol. 35, 1415-1432
[48] Gopalan, R., K. Talluri. Mathematical Models in Airline Schedule
Planning: a Survey. Ann. Oper. Res. Math. Ind. Syst., 1997, Vol. Ⅱ(69),115-130
[49] Hane, C.A., C. Barnhart, E.L. Johnson, R.E. Marsten and G.L. Nemhauser. The Fleet Assignment Problem: Solving Large-Scale Integer Programming. Mathematical Programming. 1995, Vol.70,211-232
[50] Cynthia Barnhart, Natashia L., Lloyd W. Clarke. Flight String Model for Aircraft Fleeting and Routing. Transportation Science. 1998, Vol. 32(5), 208-219
[51] Ahuja, R.K., Magnanti, T.L. and Orlin, J.B. Network flow: theory, algorithms, and applications. Prentice Hall, Englewood Cliffs, N.J. 1993
[52] Ford, L.R., Dulkerson, D.R. Flow in network. New Jersey, Princeton University Press. 1962
[53] Berge, M.E. and Hopperstad, C.A. Demand driven dispatch: a method for dynamic aircraft capacity assignment, model and algorithms. Operational Research. 1993, Vol. 41,153-168
[54] Daskin, M.S. and Panayotopoulos, N.D. A lagrangian relaxation approach to assigning aircraft to routes in hub-and spoke networks. Transportation Science. 1989, Vol. 23, 91-99
[55] Subramanian, R., Scheff, R.P., Quillinan, Jr.J.D. and Wiper, D.S. Coldstart:fleet assignment at Delta Airlines. Interfaces. 1994,Vol. 24, 104-119
[56] Brian, R, Cynthia, B., Tim, K. and Ahmad, J. Airline fleet assignment with time windows. Transportation Science. 2000,Vol. 34(1),1-20
[57] Levin, A. Scheduling and fleet routing models for transportation systems. Transportation Science. 1971, Vol. 5,232-255
[58] Ryan, D.M. The solution of massive generalized set partitioning problems inaircrew rostering. J. Oper. Res. Soc. 1992, Vol. 43,459-467
[59] Ryan, D.M. and Garner, K.M. The solution of air-crew scheduling problems for air new zealand. Proc. of the 21st Annu. Conf. Of O.R.S.N.Z.1985, 42-48
[60] Marsten, R.E. Muller, M.R. and Killion, C.L. Crew planning at
flying Tige: a successful application of integer programming. Networks.1981, Vol. Ⅱ, 165-177
[61] Marsten, R.E. and Shepardson, F, Exact solution of crew scheduling problems using set partitioning model:recent successful applications. Management Science. 1979, Vol. 25, 1175-1183
[62] Hoffman, K.L. and Padberg, M. Solving airline crew scheduling problems by branch-and-cut. Management Science. 1993, Vol. 39, 657-682
[63] Graves, G.W., Mcbridge, R.D., Gershkoff, I. And Andersion, D. Flight crew scheduling. Management Science. 1993, Vol. 39, 736-745
[64] Gamache, M., Soumis, F. and Desrosiers, J. A column generation approach for large scale aircrew rostering problem. Oper. Res. 1998a,Vol. 39,657-682
[65] Anbil, R., Zanga, R. and Johnson, E.J. A global approach to crew-pairing optimization. IBM Syst. J. 1992, Vol. 31, 71-78
[66] Monroe, W.W. and Chu, H.D. Real-time crew rescheduling at American airlines. Presentation at INFORMS New Orleans. 1995
[67] Ryan, M. and Falkner, J.C. A bus crew scheduling system using a set partitioning model. Asia Pacific J. Oper. Res. 1987, Vol. 4, 39-56
[68] Clarke, M.D. Solving the problem of irregular airline operations. Presentation at INFORMS New Orleans. 1995
[69] Chu, H.D., Gelman, E. and Johnson, E.L. Solving large scale crew scheduling problem, Eur. J. Oper. Res. 1997, Vol. 97, 260-268
[70] Anbil, R., Gelman E., Patty, B. and Tanga, R. Recent advances in crew-pairing optimization at American airlines. Interface. 1991,Vol. 21, 62-74
[71] Cynthia Barnhart, Natashia, L., Lloyd W. Clarke. Flight String Model for Aircraft Fleeting and Routing. Transportation Science. 1998, Vol. 32(5), 208-219
[72] Garey, M.R. and Johnson, D.S. Computers and intractability: a guide to NP-completeness. W.H. Freeman & Company, San Francisco, 1978
[73] Papadimitriou, C.H. andSteiglitz, K. Combinatorial optimization: algorithms and complexity. Prentice-Hall, inc., New Jersey, 1982
[74] Vance, P.H., Barnhart, C., Johnson, E.L. and Nemhauser, G.L.
Airline crew scheduling: a new formulation and decomposition algorithm. Oper. Res. 1997,Vol. 45, 188-200
[75] Baker, E.K. Efficient heuristic algorithms for the weighted set covering problem. Computers Oper. Res. 1981, Vol. 8, 303-310
[76] Barnhart, C., Hatay, L. and Johnson, E.L. Deadhead selection for the long-haul crew pairing problem. Oper. Res. 1995, Vol. 43, 491-499
[77] Desrosiers, J., Dumas, Y., Solomon, M.M. and Soumis, F. Time constrained routing and scheduling. Handbooks in Operations Research and Management Science, Network Routing, 1995, Vol. 8, 35-139
[78] Metropolis, N., Rosenbluth, A. and Rosenbluth, M. Equation of state calculation by fast computing machines. Journal of Chemical Physics, 1953, Vol. 21, 1087-1092
[79] Kirkptrick, S., Gelatt, Jr.C.D. and Vecchi, M.P. Optimization by simulated annealing. Science, 1983, Vol. 220, 671-680
[80] Aarts, E.H.L. and Laarhoven, P.J.M. Simulated annealing: theory and application. D Reidel Publishing Company. Dordrecht. 1987
[81] Ackley, D.H., Hinton, G.E. and Seinowski, T.J. A learning algorithm for Boltzmann machines. Cognitive Science. 1985, Vol. 9,147-169
[82] Seneta, E. Non-negative matrices and markov chains. 2nd Edition. Springer Verlag. New York. 1981
[83] Geman, S. and Geman, D. Stochastic relaxation, Gibbs distributions, and the Bayaesian restoration of images. In: IEEE Proc. Pattern Analysis and Machine Intelligence, PAMI-6, 1984, 721-741
[84] Anily, S.F. Probabilistic analysis of simulated annealing methods. Graduate School of Busuness, Golumbia University, New York, Preprint.1985
[85] Lundy, M. and Mees, A. Convergence of an annealing algorithm. Mathematical Programming, 1986, Vol. 34, 111-124
[86] Huang, M.D., Romeo, F. and Sangiovanni-Vincentelli, A.L. An efficient general cooling schedule for simulated annealing. In: Proceeding of IEEE Int. Conference on Computer-Aided design. Santa Clara. 1986
[87] Lai, K.K. and Chan, J.W.M. Developing a simulated annealing algorithm for the cutting stock problem. Computers Ind. Engng. 1996
[88] Isaacson, D. and Madsen, R. Markov Chains. Wiley. New York. 1976
[89] 盛骤．概率论与数理统计．第二版，高等教育出版社．北京．1990
[90] 李文权．博士学位论文：铁路区段站日工作计划优化模型及其算法的研究．西南交通大学．1999年
[91] 林诒勋．同顺序m×n排序问题的动态规划方法．数学进展，1986，Vol．4，337-346
[92] 林诒勋．最小化误时损失的一台设备排序问题．应用数学学报，1983，Vol．21．228-235
[93] 俞文此．工件集合上的某种全序及其应用．应用数学与计算数学学报，1991，Vol．5，66-71
[94] 马振华．现代应用数学手册——运筹学与最优化理论卷．清华大学出版社．北京．1998．
[95] 李文权，王炜，杜文，林诒勋．铁路技术站调机运用模型及算法．系统工程学报，2000，Vol．15(3)，66-71
[96] 林尧瑞，张钹，石纯一．专家系统原理与实践．清华大学出版社．北京．1988
[97] 刘军．一类复杂规划问题的分层规划方法．北方交通大学学报，1995，Vol．19(3)
[98] 孙宏，杜文．航空公司航班衔接问题的模型及算法．四川工业学院学报，2001，Vol．22(2)，20-22
[99] 郭耀煌．运筹学原理与方法．西南交通大学出版社．成都．1994
[100] 孙宏，文军，罗风娥．航班运营飞行计划．民航飞行学院出版社．成都．2002
[101] 中国民用航空局．航空承运人运行合格审定规则．中国民用航空局．北京．1999
[102] 中国民用航空局．中国民用航空飞行人员训练管理规定．中国民用航空局．北京．1998
[103] 中国民用航空局．中国民用航空器适航管理条例．中国民用航空局．北京．1996
[104] H．P．威廉斯著，孟国璧等译．数学规划模型建立与计算机应用．国防工业出版社．北京．1991
[105] 林诒勋．动态规划与序贯最优化．河南大学出版社．开封．1996
[106] 吴文虎，王建德．实用算法的分析与程序设计．电子工业出版社．北京．1998