摘要
运输调度是铁路运输组织的重要组成部分,它包括乘务调度、动车调度、到发线调整、运行图调整,其中,乘务调度问题既要受到运行图限制,又要受复杂乘务规则的约束,是运输调度的一个难题。目前,我国对铁路乘务调度计划编制方法的研究较少,铁路乘务调度中仍以手工方式为主编制乘务调度计划。这种方式编制乘务调度计划效率低,所编制乘务调度计划质量难以保证,尤其在乘务规则复杂的情况下,采用手工方式编制乘务调度计划是非常困难的。研究一套科学的铁路乘务调度计划编制方法对提高我国铁路乘务调度计划编制效率,提高我国铁路乘务调度工作水平有着重要的意义。
针对我国铁路乘务调度计划编制方面存在的问题以及相关研究较少的现状,论文从铁路乘务调度计划编制的过程、建模方法和求解方法三方面对铁路乘务调度计划编制方法进行研究,选择出用于设计我国铁路乘务调度计划编制方法的理论依据;接下来,论文分析了我国铁路CSP问题的目标及约束条件,采用集合覆盖方法建立我国铁路CSP问题模型,并研究了如何利用列生成算法进行求解;然后,论文分析了我国铁路CRP问题的目标及约束条件,采用线性规划方法建立我国铁路CRP问题模型,研究了我国铁路CRP问题的求解过程;最后,本研究通过计算机仿真实验,以京津高速铁路列车开行方案为例,对论文设计的方法进行了验证。
通过研究,论文设计出了比较完整的我国铁路乘务调度计划编制方法。该方法求解我国铁路CSP问题时采用了列生成算法,解决了启发式算法不能保证解的最优性的问题,提高了铁路乘务调度计划的优化程度。仿真实验结果表明,论文设计的方法能够满足我国铁路乘务调度规则,具有一定的可行性。论文的研究为我国铁路乘务调度计划编制系统的开发及相关研究的进一步开展提供了理论支持。
Traffic control in railway transportation is an important part of Railway Transport Organization, and it contains crew scheduling, locomotive dispatching, receiving-departure track adjusting and train operation adjusting. Restricted by train operation and complex crew scheduling rules, crew scheduling is a difficult problem of traffic control in railway transportation. There is little research on domestic railway crew scheduling method at present. Now domestic railway staffs make crew roster mainly by hand. This method has low efficiency in crew scheduling and may not optimize crew roster enough, especially when crew scheduling rules are complicate. Research and design a scientific method of railway crew scheduling has significance in increasing domestic railway crew scheduling efficiency and improve domestic level of dispatching railway crew.
To the problem of domestic railway crew scheduling and lack of relative research, we research railway crew scheduling through progress, model and algorithms to determine theory used in domestic railway crew scheduling. Then we build a set cover model for domestic railway CSP problem after analyzing object and constraints and research how to solve the problem with column generation algorithm. Following that, we build a line program model for domestic railway CRP problem after analyzing object and constraints and research how to solve the problem. At last, we make a simulation by computer to prove the feasible of this method based on data of Beijing-Tianjin railway operation.
Through the research, we design a systemic domestic railway crew scheduling method. In this method, we solve domestic railway CSP problem with column generation algorithm to avoid the defect of heuristic algorithm and optimize crew roster further. The results of computer simulation show that, the method is able to fulfill domestic railway crew scheduling rules. The research builds the basis for developing crew scheduling system and further research on crew scheduling.
引文
铩颷1]赵鹏.高速铁路动车组和乘务员运用的研究[博士论文].北方交通大学.1998
[2]赵鹏,胡安洲,杨浩.机车乘务员运用计划的优化编制.铁道学报.1998.20(4).8-11
[3]赵鹏,姚凤金,张洪亮.综合调度仿真系统中的机车乘务调度计划的编制.铁道运输与经济.2004.27(3).74-76
[4]Alberto Caprara,Matteo Fischetti,Paolo Toth,Daniele Vigo,and Pier Luigi Guida.Algorithmsfor railway crew management.Tichnical report.1997
[5]Jasper Moller.Seminar on Algorithms and Models for Railway Optimization Crew Scheduli-ng.2002
[6]Alberto Caprara,Matteo Fischetti,Pier Luigi Guida,Paolo Toth,and Daniele Vigo.Solutionof large-scale railway crew planning problems:the italian experience.Technical report.1997
[7]Alberto Caprara,Matteo Fischetti,Paolo Toth,and Daniele Vigo.Modeling and solving thecrew rostering problem.Technical report.1995.
[8]Dennis Huisman.A column generation approach for the rail crew re-schednlingproblem.European Journal of Operational Research.2006
[9]李文慧.匈牙利方法在铁路列车乘务组分派问题中的应用.兰州交通大学学报.2007.26(3)
[10]侯海波.关于机车乘务员乘务方式改革的探讨.铁道技术监督.2004.(8).19-20
[11]段华斌,陈林.关于机车交路与乘务员乘务方式的探讨.内燃机车.2003.(2).21-22
[12]高振.钢铁原料采购物流优化问题与列生成算法研究[博士论文].东北大学.2003
[13]甘应爱,田丰等.运筹学.第2版.北京.清华大学出版社.1990
[14]Vanderbeck F.On Dantzig-Wolfe Decomposition in Intiger Programming and Ways toperform Branching in a Branch-and-Price algorithm[J].Operations Research.2000.48(1).111-128
[15]马振华.现代应用数学手册(运筹学与最优化理论卷).北京.清华大学出版社.1998
[16]Glenn W.Graves.Flight Crew Scheduling.Management science.1993.39(6)
[17]Ranga Anbil.Recent Advances in Crew-Pareing Optimization at American Aillines.Inerf-ace.1991.21(1)
[18]John G.Klincewicz.The Airline Exception Scheduling Problem.Transportation Sci.1995.29(1)
[19]饶云波.航空公司乘务员排班系统的优化算法[硕士论文].电子科技大学.2006
[20]林红,饶云波,李勇.遗传算法在乘务员排班系统中的应用.计算机技术与发展.2007.11(1).199-202
[21]王红,张蕾.遗传算法在航空公司飞行人员排班中的应用研究.计算机工程与应用.2006.(10).220-222
[22]李青,张军,张学军.解决排班问题的多目标优化模型及算法研究.北京航空航天大学学报.29(9).821-824
[23]Martin Desrochers.A column generation approach to the urban transit crew schedulingproblem.Transportation Sci.1989.23(1)
铩颷24]Jean Yves Blais.The HASTUS Vehicle and Manpower Scheduling System at theS.T.C.U.M.Interface.1990.20(1)
[25]Blais J.-Y..HASTUS,a model for the economic evaluation of driver's collective agreementsin transit companies.Information.1982.20(1)
[26]王鹏飞.智能公交之车辆人员排班算法的研究与应用[硕士论文].山东大学.2006
[27]李献忠,徐瑞华.基于乘务广义费用的城市轨道交通排班.同济大学学报.2007.35(6)
[28]李献忠,徐瑞华.基于时间耗费的城市轨道交通乘务排班优化.铁道学报.2007.29(1)