Study Of The Optimization Algorithm Of Crew Scheduling For Urban Rail Transit

Crew scheduling for urban rail transit,as always a necessary component that accounts for a large proportion in operating cost,has been an important researching field through years.In daily operation of urban rail transit,it first comes to timetable according to transport demands and to rolling stock turnover plan in the following.Finally it completes crew scheduling and crew shifting plan,which cover every trip by every specific crew member.This paper aims at an optimizing method which can automatically create better crew scheduling plans that decrease cost for the operating agency to the maximum extent on the base of existing rolling stock turnover plan.This paper comes up with a crew scheduling algorithm based on greedy mechanism for urban rail transit referring to existing research on column generation.In the algorithm,sub-problem is described as a network in which nodes represent the crew sections and arcs the available linking relationships between crew sections,thus changing the problem into an equivalent shortest path problem.Moreover,it comes up with a labeling method based on the choice of shadow price to solve the model under the constraints of practical work,aiming at getting better new column in shorter time.The model is further improved in order to adapt to crew scheduling problem with multiple shifting stations.However,with the increasing of length,rolling stocks and shifting stations,the crew sections will increase rapidly,which results in the exponential growth in calculating time.Therefore,this paper puts forward a group-and-price mechanism based on the algorithm proposed forward in this article,in order to decrease calculating time while ensuring the quality of result.According to the group-and-price mechanism the crew sections,which used to be all in a master problem,are divided into several groups by rules of time and space.Each group is independent to each other,and is calculated step by step,which can decrease calculating time sharply.In the meantime,it is decided the group and price of each crew section in order to ensure the quality of result by enhancing relations between groups through both shadow price of crew sections and result of each group problem.At last,this paper examines the algorithms by the practical example from several subway lines in Beijing.Then it compares the results with the crew scheduling plan used in practice to prove the efficiency and superiority of the algorithm proposed in this paper.Moreover,it examines the high efficiency of the group-and-price mechanism and the feature that can ensure the quality of result.In the meantime,it is also analyzed in this paper the method of grouping through experiments in order to find out the best dividing way for an actual line.