Modeling Crew Planning For Urban Rail Transit Systems

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.