【作者】 张增勇；

【导师】 毛保华；

【作者基本信息】 北京交通大学 ， 交通运输规划与管理， 2014， 博士

【摘要】 乘务计划是城市轨道交通系统运行的重要日常计划,是建立在列车运行图基础上的乘务员工作计划。当前,我国城市轨道交通运营中,乘务计划多数是由各线路乘务中心的负责人员手工编制完成,一般要耗时一到两周。每次列车运行图调整后均需要重新编制乘务计划。此外,为了应对突发情况引起的运行任务的变化,乘务中心需要预备多个乘务计划方案或者提前一段时间得到通知临时编制乘务计划。由于实际情况的动态特性,这些应对措施往往灵活性不足,应变能力不强,从而直接影响到城市轨道交通的运营效率和服务水平。这也说明乘务计划的自动编制具有重要的研究价值和现实意义。本文通过对城市轨道交通运输企业乘务中心的实地调研,在借鉴国内外已有研究成果的基础上,将乘务计划分为乘务排班计划和乘务轮班计划两部分,并提出了乘务计划编制问题的模型与算法。基于运行图和车辆运用计划等基础数据,论文分别构建了单工作班制乘务排班模型和混合工作班制乘务排班模型,并设计了相应的算法。在乘务排班计划基础上,本文分别构建了单一循环乘务轮班模型和固定周期乘务轮班模型,并设计了相应的算法。论文的主要研究内容和结论如下：(1)以我国城市轨道交通乘务计划编制环境为对象,提出了单工作班制乘务排班模型。该模型为双层模型,同时考虑乘务作业段和乘务工作班。下层是乘务作业段生成模型,求解目标为最小的广义时间费用,用来优化车次链分割方式。上层为乘务工作班生成模型,求解目标为最小的惩罚费用,考虑的因素包括不同值乘点交接班、定时定点就餐、间休时间、班次只生成整班,各项考虑因素偏离标准时间时进行惩罚,其中,不同值乘点交接班、间休时间、班次中的工作时间采用单向上限惩罚机制,定时定点就餐、班次中的作业时间采用双向偏离惩罚机制；约束条件为不低于标准的就餐时间和间休时间,此外,设定了预留就餐时间的乘务工作班条件。(2)设计了求解单工作班制乘务排班模型的算法。下层模型的求解过程分为初始方案生成和调整两步,乘务作业段初始方案在生成时采用双向搜索策略的Dijkstra算法,调整时依次改变小乘务作业段在车次链中分布的位置。上层模型的计算基于下层模型的结果,求解过程分为初始方案生成、寻优、算法终止三步,乘务工作班初始方案在生成时同样采用改进的Dijkstra算法；寻优时采用离散粒子群算法,其中包括分解-重组、置换两个子过程；算法终止时采用精度策略。应用算例验证模型和算法,数据规模为9列车、182个乘务片段,计算结果统计显示：乘务工作班的作业时间均值超出标准13分钟,间休时间均值超出标准22分钟,两项数据表明方案整体理想。另外,研究发现：乘务排班质量的优劣与运行图任务的结构、约束条件、建模机制等密切相关。(3)以客流峰谷明显的乘务环境为研究对象,编制乘务排班计划时,在乘务作业段方案的基础上同时编制倒班乘务工作班和日勤乘务工作班,构建了混合工作班制乘务排班模型,并设计了相应的算法。模型的考虑因素和建模机制与单工作班制乘务排班模型相同；求解时,在生成乘务工作班初始方案以及寻优过程中,增加了日勤乘务工作班的惩罚费用增值,用以平衡两种工作班之间的惩罚费用比较。应用算例验证模型与算法,数据规模为20列车、309个乘务片段并且高峰与平峰任务量比例为2：1,计算结果统计显示：倒班工作班的作业时间均值超出标准15分钟,间休时间均值超出标准12.5分钟；日勤工作班的作业时间均值短于标准15分钟,间休时间均值超出标准18分钟。通过与单工作班制排班方案对比可知,即使是在列车运行任务更复杂的条件下,两者作业时间均衡,混合工作班制排班方案的间休时间均值还是明显减少,说明当客流峰谷明显时,采用混合工作班制的乘务排班方法是比较理想的。(4)以我国城市轨道交通乘务轮班环境为研究对象,分别构建了单一循环乘务轮班模型和固定周期乘务轮班模型,并设计了相应的算法。在轮班模式固定的条件下,按时段划分乘务工作班,每个司机在轮班时必须逐一执行各时段的工作班。基于这一特点,单一循环轮班时,司机顺序执行乘务位置,直到完成所有乘务工作班,模型的目标是所有乘务位置的时间费用均衡；固定周期轮班时,模型的目标是所有周期任务的时间费用均衡。求解时,两种模型均采用分层序列法、广度优先搜索、阶段解置换变异的操作策略。应用混合工作班制排班方案的数据验证模型和算法,结果表明：每个司机在两种轮班方式下的工作量均较为均衡,方案整体理想。更多还原

【Abstract】 Crew planning is an important part of daily operation planning of urban rail transit system and it is the crew work plan based on train diagram. In most China urban rail transit systems, crew planning is generated by the crew center officers of different lines, generally taking one to two weeks. When the train diagram is changed, the crew plan requires a new solution. Further more, to deal with the tasks changing caused by unexpected situations, the crew center need to prepare several crew plans, or make the plan temporarily notified in advance. Due to the dynamic characteristics of actual situation, these responses often lack flexibility and the adaptability is not strong, which directly affects the operational efficiency and service performances of urban rail transit. This indicates that the automatic crew planning is of important research value and practical significance.Based on the investigation in crew center of urban rail transit enterprise and the previous researches, this thesis divides crew planning into crew scheduling and crew rostering, and proposes the models and algorithms of crew planning. Using the data of diagram and vehicle scheduling, this thesis builds a single working shift crew scheduling model and a mixed working shifts crew scheduling model, and designs the corresponding algorithms. Based on crew scheduling, this thesis builds a single cycle crew rostering model and a fixed cycle crew rostering model, and designs the corresponding algorithms.The following provides the main contents of this thesis:(1) Considering the real operating condition of Chinese urban rail transit, this thesis proposes a crew scheduling model with single working shift. The two-layer model takes into account both crew work piece generating and crew duty generating. The lower layer is a crew work piece generating model, and the target is the minimum generalized time, to optimize vehicle blocks’ segmentation approach. The upper layer is a crew duty generating model, and the target is the minimum punishment, taking into consideration the different point cost by shift, dining cost, break cost, and only generating the whole duty. The various considering factors will be punished when a deviation from standard time. Among them, the cost of different points by shift, break, and spread time use a one-way limit punishment mechanism. While the cost of dining and work time use a two-way deviation punishment mechanism. The upper constraints are no less than standard meal times and breaks. Additionally, the crew duty conditions for emptying time to eat are set.(2) This thesis designs an algorithm to solve crew scheduling model with single working shift. Solving process of the lower model is divided into two steps:initial plan’s generation and adjustment. The initial plan’s generation of crew work pieces uses Dijkstra algorithm with bi-directional search strategy. The adjustment is to change position of small crew work pieces in vehicle blocks. The calculation of upper model bases on the results of the level model, and the solution process is divided into an initial plan’s generation, optimization, algorithm terminates three steps. Generating initial plan of crew duty uses the same improved Dijkstra algorithm. Discrete particle swarm algorithm, including decomposition-restructuring and replacement, are used in attaining the optimized solution. Algorithm terminates adopt accuracy strategy. Case studies are conducted to validate the model and algorithm, including9trains and182crew pieces. Results show that the average work time of duty is13minutes beyond the standard, and the average break time of duty is22minutes beyond the standard. Data show that the plan is overall satisfactory. In addition, it is found that the quality of crew scheduling is closely related to the tasks structure of diagram, constraints, modeling mechanism.(3) Taking into account the situation of a clear passenger flow peak in crew environment, this thesis proposes a crew scheduling model with mixed working shifts and designs the corresponding algorithm. In producing the crew plan, the generation of both shift crew duty and regular crew duty are based on work piece plan. Compared with single working shift crew scheduling model, the same factors and modeling mechanism are considered by crew scheduling model with mixed working shifts, In solving the model, regular crew duty in generating the initial plan and optimization process increases the punishing cost to balance the compare with shift crew duty. Case studies are conducted to validate the model and algorithm, including20trains,309crew pieces, and the tasks ratio is2:1between peak period and flat peak period. Results statistics show that the average work time of shift crew duty is15minutes beyond the standard, and the average break time is12.5minutes beyond the standard. The average work time of regular crew duty is15minutes shorter than the standard, and the average break time is18minutes beyond the standard. In contrast with the data of single working shift crew scheduling, the results show that even in more complex conditions, the break time is significantly reduced, while work time is substantially equal. This indicates that when the passenger flow’s peak and valley are evident, using the approach for crew scheduling with mixed working shifts is ideal. (4) This thesis proposes a single cycle crew rostering model and a fixed cycle crew rostering model, and then designs the corresponding algorithms. Under the conditions of a fixed rostering mode, the crew duties of a day are divided by period, each driver must take on duties according to the period. For a single cycle, the driver performs crew positions sequentially until the completion of all crew duties, and the target of model is to balance the cost of all crew positions. For a fixed cycle, the target of model is to balance the cost of all crew periodic tasks. In solving the above two models, operation strategy of stratified sequence method, breadth-first search and replacement of phase solution are proposed. Using data of crew scheduling with mixed working shifts to validate the models and algorithms, results show that each driver’s workload is substantially equal in the two kinds of rostering methods, and the attained plans are satisfactory.更多还原