Optimization Research On Urban Rail Transit Crew Scheduling Problem Based On Crew Sharing

Crew planning is one of the key issues of urban rail transit transport organization.Its compilation effect has a significant impact on the efficiency of transport organization and operating cost.With the development of urban rail transit network,the related operational and management problems tend to be complicated,which makes the background of crew planning more complex.Crew scheduling is the core sub-problem of crew planning.In practice,inefficient manual method is usually adopted,which is inconvenient to adjust and lack of optimization process,and lacks efficiency and economy.Therefore,it is of great significance to study scientific and rational optimization methods to achieve efficient and automated compilation of crew scheduling problem and to obtain more optimized compilation results.In recent years,the number of urban rail transit operating lines has been increasing and there are great differences in the use of crew between lines.In order to achieve a more reasonable allocation of crew resources,this paper proposes a crew scheduling problem based on crew sharing.Based on the relevant existed research,considering the characteristics of urban rail transit crew scheduling problem,the crew scheduling model is constructed based on the set covering problem and solved by a two-stage method.The model of crew sharing problem is based on the single line model and the algorithm of single line problem is improved to adapt the sharing problem.The main contributions of this paper are as follows.(1)Discuss the crew scheduling problem under the crew sharing mode,introduce the background and compiling conditions of the problem,give the definition of the sharing problem and analyze the solving process of the problem.(2)Considering relevant operational and management rules,crew scheduling model of single line is constructed as a set covering model base on feasible duties,while the generation of feasible duty is based on tree structure and depth-first method.The scheduling results are obtained by solving 0-1 integer programming directly.(3)The crew sharing scheduling problem increases transfer continuity constraint on the single line model and improves the generation process of the feasible duties in the solution process.For the case where the large-scale problem is difficult to solve,a method based on Lagrange relaxation is used to handle the problem.(4)Based on the actual data of urban rail transit,a case study is designed to verify the effectiveness of the algorithm and then we compare and analyze the results of single-line and sharing mode.Finally,the influencing factors of sharing problem are analyzed.