Research On Optimization Method Of Urban Rail Transit Crew Scheduling Problem

Nowadays,in the urban rail transit operation management of most big cities in China,the train diagram can already be automatically generated by softwares,while the crew plan,which is the specific implementation of the train diagram,is mainly manually compiled by the engineers.Manually scheduling not only takes a lot of time,but it is also difficult to flexibly respond to the adjustments of the train diagram or any other emergencies,which will affect the service level of the urban rail transit.Therefore,automatic compilation of crew plan is an inevitable trend.The difficulties and effectiveness of the crew planning compilation are different depend on the scale of the lines.This thesis aims at the optimization of the largescale crew scheduling plan.Based on the existed research related to crew scheduling problem of different transportations,this thesis firstly summarizes the compilation process of the crew scheduling plan,and then establishes the optimization model to minimize the number of crew shift based on the set partitioning model and set covering model.Finally,the effectiveness of the algorithm is proved by case studies.The main research is as follows:(1)Based on the 0-1 integer programming model and column generation algorithm,this paper constructs the crew scheduling model of urban rail transit by satisfying the full coverage constraint of crew fragments,meal time constraint,rest time constraint,working time constraint,and continuous driving time constraint of the crew duty.The initial restricted master problem is constructed based on a feasible scheduling scheme,and by establishing the network graph model,the pricing subproblem of the column generation algorithm is transformed into the shortest path problem with resource constraints in the network graph.In each iteration of the column generation algorithm,among all the shortest paths with the smallest check value,the path with longer working time and higher work efficiency is selected as the new shift and added to the set of feasible shifts in the restricted master problem.Finally,the integer programming model is used to select some shifts from the new shift set generated by the column generation algorithm to form the final scheduling plan.(2)Taking the crew scheduling problem of Chengdu Metro Line 1 as an example,the results of model and algorithm proposed by this paper are compared with the manuel crew plan.At the same time,the set partioning model and set covering model,as well as two different crew segments generating methods are used to establish in total four different crew scheduling models to resolve the crew scheduling problem.The differences in the solving the four scheduling models are analyzed and compared.Furthermore,this paper compiles crew scheduling plan separately based on the four models,and the results are evaluated from the five aspects,including scheduling target,working time,driving time,rest time,and work efficiency.The results show that the scheduling scheme obtained by the model proposed by this paper is better than the manual scheduling scheme in terms of the efficiency of problem solving,number of shifts,work efficiency of shifts,and the total working time required to complete the same volumn of driving task.The set covering model has more optimization space than the set partioning model,it can obtain a theoretically better scheduling plan.In the resolution of large-scale crew scheduling problem,the fully enumeration of crew duty will not only increase the complexity of the algorithm,but also reduce the efficiency of the problem solving process.On the contrary,using the crew duty without overlapping crew segments can simplify the problem,and obtain a better scheduling plan in a shorter time.