Research On Optimization Of Crew Schedule Planning For Urban Rail Transit

With the prosperous development of urban rail transit,the issue of how to raise the level of operation management and reduce the cost of operation management has been paid more and more attention.The preparation of crew scheduling plans is regarded as an indispensable part of urban rail transit operations,and has attracted increasing sight from the industry.In the field work,crew scheduling plans are usually compiled manually by the relevant personnel,which not only takes a long time,but also has a great space for optimization in the operating costs and unnecessary labor time of crew members.Based on this,this article aims to reduce the crew-related costs of operating agencies and the non-essential labor time of crew members,exploring the automatic preparation and optimization of crew scheduling plans.The main research contents are as follows:(1)The relevant theories on the urban rail transit crew scheduling problem are systematically introduced,in particular,the article summarizes the characteristics of the crew scheduling problem and the planning process.And it has laid a solid theoretical foundation for the optimization of the next crew scheduling plan.(2)The optimization model of crew scheduling in urban rail transit is established.Firstly,the crew scheduling problem of urban rail transit is transformed into the vehicle routing problem under the space-time-state network,and five different directed arcs are defined to describe the related behaviors of crew members.Secondly,the objective function is set for the purpose of balancing the total number of crew members and the total non-essential labor time of crew members.Finally,by converting the value of non-essential labor time equivalent to each crew member into the fixed vehicle usage cost in the vehicle routing problem,the goal is unified.And the longest working hours,rest and dining and other related constraints are embedded into the inherent constraints such as the time window and vehicle capacity in the vehicle routing problem,so as to realize the simplification of model constraints.(3)An improved alternate direction multiplier method is designed to solve the crew scheduling problem.Firstly,the optimization model was reconstructed by dual,augmented and decomposed.In order to solve the vehicle sub-problems in augmented Lagrange form,a method to linearize the quadratic term was proposed,and a forward dynamic programming algorithm was designed to solve the vehicle sub-problems.Secondly,in order to evaluate the quality of the solution,based on the property that the Lagrangian dual form of the original problem is always less than or equal to the optimal value of the original problem,a method for finding the lower bound is designed.Finally,the open source Solomon dataset verifies the superior performance of the improved alternative direction multiplier method.(4)The crew scheduling system of urban rail transit is designed and developed,which realizes the automatic scheduling of crew scheduling and other functions.Based on the data of an urban rail transit line 4 in western China,this paper compares it with the existing scheduling plan of the operation organization,and proves that the automatic scheduling plan compiled by the system can optimize the operating cost and balance of work and rest,and can provide auxiliary management support for related technical personnel.Finally,the iterative process of the improved alternating direction multiplier method and the standard Lagrange relaxation algorithm are compared,which proves the superiority of the proposed algorithm in solving the large-scale crew scheduling problem.With 34 figures,10 tables and 60 reference literatures.