客运专线客运乘务计划优化研究
|
摘要
客运专线客运乘务计划问题是客运专线调度领域中的重要问题之一,合理的乘务计划不仅能够提高乘务的工作效率和企业的竞争力,而且对于降低成本等均有重要的意义。传统的手工编制,完全依靠编制人员的主观经验,缺乏理论基础。因此研究客运专线客运乘务计划的优化理论与方法能够为手工编制乘务计划提供科学依据与实际操作方法,并为实现乘务计划排班自动化奠定理论基础。
本文在既有研究的基础上,综合运用运输组织学理论、线性规划理论、图论和最优化理论等方法,融理论研究和实际应用为一体,通过实际调查、理论研究、算法设计等手段,对乘务计划编制的优化方法进行系统地分析,并将结果应用到广深线的乘务组排班中。主要研究内容如下：
(1)在全面总结前人研究成果的基础上,提出了客运专线客运乘务计划编制的一般理论及方法,其中主要包括客运乘务计划的含义、类别、影响因素、编制方法、编制过程及评价准则。
(2)仔细分析了客运乘务计划优化问题,将问题分解为乘务交路计划和乘务值乘计划两个优化子问题。通过对子问题的图形化描述以及对约束条件的假设和未知量的设定,论文构建了乘务交路计划优化模型,研究了两种算法思路,即适用于计算机编制的基于蚁群算法思路和适用于手工编制的基于贪心策略的算法思路；同时论文构建了乘务值乘计划优化模型并设计了求解策略。
(3)详细介绍广深线的线路、动车组运营概况以及交路现状,结合其特点,分析了现行乘务排班计划,总结现行乘务计划存在的问题。
(4)针对广深线动车组的客运乘务编制计划问题,应用构建的乘务交路计划和乘务值乘计划数学优化模型,得出优化方案,并将其与既有方案相比较,结果证明该模型与算法具有良好的适应性。
在本文的最后,阐述了全文的研究工作和存在的问题,并对进一步的工作给予了展望。
Passenger crew scheduling problem has always been an important issue in the field of passenger dedicated line. Reasonable crew scheduling program can not only improve the efficiency of crew work, but also reduce operating costs and improve the competitiveness of transport enterprises. The method of traditional manual arrangement depending entirely on the personal subjective experiences lacks theoretical guidance. Therefore, it is quite urgent to research a set of theory and method of the passenger special line for the manual arrangement scientific and providing automatic crew scheduling a theoretical foundation.
In this paper, on the basis of existing research, the theories of transportation histologic. linear programming, graph theory and optimum method are used by the actual investigation, theory research and algorithm designing methods on systematical analysis. The results can be applied to the passenger crew scheduling of Guangzhou-Shenzhen line EMU(Electrical Multiple Units).
(1) In order to compile a scientific and reasonable crew scheduling, this paper first introduces the basic concepts of crew scheduling plan, the influence factors of compilation of crew scheduling plan.
(2) The crew planning problem divided into two parts,which are crew scheduling problem and crew rostering problem, is Analyzied deeply. The optimization model of crew scheduling plan is established by the desciption of the crew scheduling problem and assuming conditions, for which both based on the ant colony algorithm and greedy algorithm are designed. At the same time, the solving strategy is designed for the optimization model of crew rostering problem.
(3) On this basis, we analyze the routing of crew and crew monthly plan of Guangzhou-Shenzhen line EMU(Electrical Multiple Units), and find the over work problem of crew of Guangzhou-Shenzhen line.
(4) according to the practical compiling approach of Guangzhou-Shenzhen line crew scheduling plan, this paper bring forward a solution strategy of the crew overworking problem. Compared with the present plan of crew scheduling, the improved plan effectively solve this problem, which show us it is of great implementation.
To sum up, the paper concluded the research working and existing problems, and the further work is prospected.
本文在既有研究的基础上,综合运用运输组织学理论、线性规划理论、图论和最优化理论等方法,融理论研究和实际应用为一体,通过实际调查、理论研究、算法设计等手段,对乘务计划编制的优化方法进行系统地分析,并将结果应用到广深线的乘务组排班中。主要研究内容如下：
(1)在全面总结前人研究成果的基础上,提出了客运专线客运乘务计划编制的一般理论及方法,其中主要包括客运乘务计划的含义、类别、影响因素、编制方法、编制过程及评价准则。
(2)仔细分析了客运乘务计划优化问题,将问题分解为乘务交路计划和乘务值乘计划两个优化子问题。通过对子问题的图形化描述以及对约束条件的假设和未知量的设定,论文构建了乘务交路计划优化模型,研究了两种算法思路,即适用于计算机编制的基于蚁群算法思路和适用于手工编制的基于贪心策略的算法思路；同时论文构建了乘务值乘计划优化模型并设计了求解策略。
(3)详细介绍广深线的线路、动车组运营概况以及交路现状,结合其特点,分析了现行乘务排班计划,总结现行乘务计划存在的问题。
(4)针对广深线动车组的客运乘务编制计划问题,应用构建的乘务交路计划和乘务值乘计划数学优化模型,得出优化方案,并将其与既有方案相比较,结果证明该模型与算法具有良好的适应性。
在本文的最后,阐述了全文的研究工作和存在的问题,并对进一步的工作给予了展望。
Passenger crew scheduling problem has always been an important issue in the field of passenger dedicated line. Reasonable crew scheduling program can not only improve the efficiency of crew work, but also reduce operating costs and improve the competitiveness of transport enterprises. The method of traditional manual arrangement depending entirely on the personal subjective experiences lacks theoretical guidance. Therefore, it is quite urgent to research a set of theory and method of the passenger special line for the manual arrangement scientific and providing automatic crew scheduling a theoretical foundation.
In this paper, on the basis of existing research, the theories of transportation histologic. linear programming, graph theory and optimum method are used by the actual investigation, theory research and algorithm designing methods on systematical analysis. The results can be applied to the passenger crew scheduling of Guangzhou-Shenzhen line EMU(Electrical Multiple Units).
(1) In order to compile a scientific and reasonable crew scheduling, this paper first introduces the basic concepts of crew scheduling plan, the influence factors of compilation of crew scheduling plan.
(2) The crew planning problem divided into two parts,which are crew scheduling problem and crew rostering problem, is Analyzied deeply. The optimization model of crew scheduling plan is established by the desciption of the crew scheduling problem and assuming conditions, for which both based on the ant colony algorithm and greedy algorithm are designed. At the same time, the solving strategy is designed for the optimization model of crew rostering problem.
(3) On this basis, we analyze the routing of crew and crew monthly plan of Guangzhou-Shenzhen line EMU(Electrical Multiple Units), and find the over work problem of crew of Guangzhou-Shenzhen line.
(4) according to the practical compiling approach of Guangzhou-Shenzhen line crew scheduling plan, this paper bring forward a solution strategy of the crew overworking problem. Compared with the present plan of crew scheduling, the improved plan effectively solve this problem, which show us it is of great implementation.
To sum up, the paper concluded the research working and existing problems, and the further work is prospected.
引文
[1]Arabeyre J., Fearnlrey J., Steiger F. Teather W.. The airline crew scheduling problem:A survey [J]. Transpotation Science,1969,3:140-163.
[2]Barnhart C.. Belobaba P., Amedeo R. Odoni.Applications of operations research in the air transport industrylJ]. Transportation Seienee,2003,37(4):368-391
[3]Dawid H., Konig J., Strauss C.. An enhanced rostering model for airline crews[J]. Computer&Operations Research,2001.28:671-688
[4]Kohl N., Karisch S. E..airline crew rostering:problem types, modeling and optimization[J]. Annals of Operrations Research,2004,127:223-257
[5]Lavoie S., Minoux M., Odier E.. A new approach of crew pairing problems by column generation and application to air transport[J]. European Journal of Operational Research, 1988.35:45-58
[6]彭其渊.客运专线运输组织[M].北京：国铁道出版社,2007
[7]钱颂迪主编.运筹学(修订版)[M].北京：清华大学出版社,1990
[8]Andrew J. Schafer Ellis L. Johnson, Anton J. Kleywegt, George L. Nemhauser. Airline crew scheduling under uncertainty [J]. Transportation Science,2005,39(3):340-348
[9]赵鹏.高速铁路动车组和乘务运用的研究[D].北京交通大学,1998
[10]孙宏,杜文,徐杰.最小费用最大流模型在航班衔接问题中的应用[J].南京航空航天人学学报.2001,33(5)：475-481
[11]谢金星,邢文训.网络优化[M].北京：清华大学出版社,2000
[12]耿敬春,肖国荣,倪少权,牛会想.客运专线动车组周期性运用计划编制的研究[J].铁道学报,2006,28(4)：17-21
[13]夏平.客运专线乘务员运用计划编制研究[D].北京交通大学,2007
[14]Klabjan D., Johnson E.L., Nemhauser G.L., Gelman E., Ramaswamy S. Airline crew scheduling with time windows and plane-count constraints [J]. Transportation Science, 2002,36(3):337-348
[15]王莹.动车组运用计划和乘务计划的优化方法研究[D].北京交通大学,2009
[16]程岩岩.我国铁路乘务调度计划编制方法的研究与设计[D].北京交通大学,2007
[17]李献忠,徐瑞华.基于乘务广义费用的城市轨道交通排班[J].同济大学学报,2007,35(6)：750-754
[18]夏平,马建军.乘务员运用计划编制模型与计算方法的研究[J].铁道运输与经济,2007,29(1)：27-31
[19]张苏波,吕红霞,刘淑辉.列车乘务排班系统的设计与实现[J].铁道运输经济,2007,29(8)：19-21
[20]阎永光,黄斌.广深线城际列车乘务组排班计划编制方法探讨[J].交通运输工程与信息学报,2010,8(1)：25-29
[21]陈林,王诚东.客运专线乘务组织模式及交路方案设置的构想[J].交通运输工程与信息学报,2010,8(1)：30：34
[22]Caprara A., Monaci,M., Toth P. A global method for crew planning in railway Application[A]. Computer-Aided Scheduling of Public Transport.Springer,2001:17-36
[23]银大伟.乘务计划编制系统的研究与设计[D].西南交通大学,2008
[24]郑芸.航空公司小规模机群飞机排班问题的数学模型与算法分析[D].中国民用航空学院,2006
[25]Klabjan D. Topics in airline crew scheduling and large scale optimization[D]. Georgia Institute of Technology,1999
[26]李献忠,徐瑞华.基于时间耗费的城市轨道交通乘务排班优化[J].铁道学报,2007,29(1)：21-25
[27]Wang F.Z., Wang H.X.., Shen J. S. Modeling and solving for railway crew scheduling Problem[A]. Proceedings of the 6th World Congress on Intelligent Control and Automation.2006.
[28]朱君.计算机软件在旅客列车乘务中的应用[J].运输管理自动化,2005,27(2)：54-55
[29]李青,张军,张学军.解决排班问题的多目标优化模型及算法研究[J].北京航空航天大学学报,2003,29(9)：21-24
[30]于得水.客运专线乘务计划编制系统的设计与实现[D].西南交通大学,2007
[31]张苏波.客运专线乘务排班计划系统相关问题研究[D].西南交通大学,2009
[32]赵鹏,胡安洲,杨浩.机车乘务计划的优化编制[J].铁道学报,1998,20(4)：8-13
[33]Cordeau J.F., Stojkovic G.., Soumis F., Desrosiers J. Benders Decomposition for Simultar Aircaft Routing and Crew Scheduling[J]. Transpotation Science,2001, 35(4):375-388
[34]Lettocsky L. Airline operation recovery:an optimization approach[D]. Georgia Institute of Technology,1997
[35]朱星辉.航空公司航班计划优化设计研究[D].南京航空航天大学,2007
[36]宋静波.基于混合模拟退火算法的航空公司勤务编排算法研究[D].南京航空航天大学,2009
[37]赵红竹.基于自适应遗传算法的机组排班方法研究和应用[D].南京航空航天大 学,2008
[38]王红,齐雁楠.机组人员搭配协调性评价方法研究[J].计算机工程与设计,2006,27(17)：3220-3222
[39]Caprara A. Fischetti M, Toth P, Vigo D. Algorithms for Railway Crew Management[J]. Mathematical Programming,1997,79:125-141
[40]王红,张蕾.遗传算法在航空公司飞行人员排班中的应用研究[J].计算机工程与应用,2006,220-2
[41]Kohl N. Solving the world's largest crew scheduling problem[J]. Orbit,2003,8-12
[42]赵鹏,姚凤金,张洪亮.综合调度仿真系统中的机车乘务计划的编制[J].铁道运输与经济,2005,27(3)：74-76
[43]Rosenberger G. M. Topics in airline operation[D]. Georgia Institute of Technology,2001
[44]Schaefer A. J. Airline crew scheduling under uncertainty[D]. Georgia Institute of Technology,2000
[2]Barnhart C.. Belobaba P., Amedeo R. Odoni.Applications of operations research in the air transport industrylJ]. Transportation Seienee,2003,37(4):368-391
[3]Dawid H., Konig J., Strauss C.. An enhanced rostering model for airline crews[J]. Computer&Operations Research,2001.28:671-688
[4]Kohl N., Karisch S. E..airline crew rostering:problem types, modeling and optimization[J]. Annals of Operrations Research,2004,127:223-257
[5]Lavoie S., Minoux M., Odier E.. A new approach of crew pairing problems by column generation and application to air transport[J]. European Journal of Operational Research, 1988.35:45-58
[6]彭其渊.客运专线运输组织[M].北京：国铁道出版社,2007
[7]钱颂迪主编.运筹学(修订版)[M].北京：清华大学出版社,1990
[8]Andrew J. Schafer Ellis L. Johnson, Anton J. Kleywegt, George L. Nemhauser. Airline crew scheduling under uncertainty [J]. Transportation Science,2005,39(3):340-348
[9]赵鹏.高速铁路动车组和乘务运用的研究[D].北京交通大学,1998
[10]孙宏,杜文,徐杰.最小费用最大流模型在航班衔接问题中的应用[J].南京航空航天人学学报.2001,33(5)：475-481
[11]谢金星,邢文训.网络优化[M].北京：清华大学出版社,2000
[12]耿敬春,肖国荣,倪少权,牛会想.客运专线动车组周期性运用计划编制的研究[J].铁道学报,2006,28(4)：17-21
[13]夏平.客运专线乘务员运用计划编制研究[D].北京交通大学,2007
[14]Klabjan D., Johnson E.L., Nemhauser G.L., Gelman E., Ramaswamy S. Airline crew scheduling with time windows and plane-count constraints [J]. Transportation Science, 2002,36(3):337-348
[15]王莹.动车组运用计划和乘务计划的优化方法研究[D].北京交通大学,2009
[16]程岩岩.我国铁路乘务调度计划编制方法的研究与设计[D].北京交通大学,2007
[17]李献忠,徐瑞华.基于乘务广义费用的城市轨道交通排班[J].同济大学学报,2007,35(6)：750-754
[18]夏平,马建军.乘务员运用计划编制模型与计算方法的研究[J].铁道运输与经济,2007,29(1)：27-31
[19]张苏波,吕红霞,刘淑辉.列车乘务排班系统的设计与实现[J].铁道运输经济,2007,29(8)：19-21
[20]阎永光,黄斌.广深线城际列车乘务组排班计划编制方法探讨[J].交通运输工程与信息学报,2010,8(1)：25-29
[21]陈林,王诚东.客运专线乘务组织模式及交路方案设置的构想[J].交通运输工程与信息学报,2010,8(1)：30：34
[22]Caprara A., Monaci,M., Toth P. A global method for crew planning in railway Application[A]. Computer-Aided Scheduling of Public Transport.Springer,2001:17-36
[23]银大伟.乘务计划编制系统的研究与设计[D].西南交通大学,2008
[24]郑芸.航空公司小规模机群飞机排班问题的数学模型与算法分析[D].中国民用航空学院,2006
[25]Klabjan D. Topics in airline crew scheduling and large scale optimization[D]. Georgia Institute of Technology,1999
[26]李献忠,徐瑞华.基于时间耗费的城市轨道交通乘务排班优化[J].铁道学报,2007,29(1)：21-25
[27]Wang F.Z., Wang H.X.., Shen J. S. Modeling and solving for railway crew scheduling Problem[A]. Proceedings of the 6th World Congress on Intelligent Control and Automation.2006.
[28]朱君.计算机软件在旅客列车乘务中的应用[J].运输管理自动化,2005,27(2)：54-55
[29]李青,张军,张学军.解决排班问题的多目标优化模型及算法研究[J].北京航空航天大学学报,2003,29(9)：21-24
[30]于得水.客运专线乘务计划编制系统的设计与实现[D].西南交通大学,2007
[31]张苏波.客运专线乘务排班计划系统相关问题研究[D].西南交通大学,2009
[32]赵鹏,胡安洲,杨浩.机车乘务计划的优化编制[J].铁道学报,1998,20(4)：8-13
[33]Cordeau J.F., Stojkovic G.., Soumis F., Desrosiers J. Benders Decomposition for Simultar Aircaft Routing and Crew Scheduling[J]. Transpotation Science,2001, 35(4):375-388
[34]Lettocsky L. Airline operation recovery:an optimization approach[D]. Georgia Institute of Technology,1997
[35]朱星辉.航空公司航班计划优化设计研究[D].南京航空航天大学,2007
[36]宋静波.基于混合模拟退火算法的航空公司勤务编排算法研究[D].南京航空航天大学,2009
[37]赵红竹.基于自适应遗传算法的机组排班方法研究和应用[D].南京航空航天大 学,2008
[38]王红,齐雁楠.机组人员搭配协调性评价方法研究[J].计算机工程与设计,2006,27(17)：3220-3222
[39]Caprara A. Fischetti M, Toth P, Vigo D. Algorithms for Railway Crew Management[J]. Mathematical Programming,1997,79:125-141
[40]王红,张蕾.遗传算法在航空公司飞行人员排班中的应用研究[J].计算机工程与应用,2006,220-2
[41]Kohl N. Solving the world's largest crew scheduling problem[J]. Orbit,2003,8-12
[42]赵鹏,姚凤金,张洪亮.综合调度仿真系统中的机车乘务计划的编制[J].铁道运输与经济,2005,27(3)：74-76
[43]Rosenberger G. M. Topics in airline operation[D]. Georgia Institute of Technology,2001
[44]Schaefer A. J. Airline crew scheduling under uncertainty[D]. Georgia Institute of Technology,2000