Crew Scheduling Optimization For Urban Rail Transit System Based On Column Generation Strategy By Network Diagram Model

Urban rail transit is encountering a rapid development in China,which brings higher requirements to the operation and management of urban rail transit.As an important link in operation,crew scheduling problem has a great influence on the labor cost which is the main part of the operation cost.But in the operational practice,the establishment of crew schedule is completed by the chef operators of managed companies according to their experience in most cases,which usually takes a long time,and compiled without optimization,affecting the operational efficiency and economic benefits.Therefore,it is of great significance to study how to compile the crew schedule with the minimum cost in a short time.Based on the existed research and operation practice of management of urban rail transit,the column generation strategy was employed to solve urban rail transit crew scheduling problem.Due to the special policies and regulations,this article formed a targeted network model,translating the pricing subproblem into several shortest path problems to solve the linear relaxing problem.Furthermore,branch and pricing method,linear relaxing method and Lagrange heuristic algorithm were applied to handle different scales of crew scheduling problem.Finally,two strategies were proposed to prove the efficiency of the algorithm.The contributions of this dissertation are mainly summarized as following.(1)To handle the special policies and regulations in urban rail transit crew scheduling problem,several multi-layer networks were constructed through a designed network generation algorithm.The correspondence between the feasible shifts and the feasible path in networks was proved afterwards,which enable to apply column generation method to the crew scheduling problem.(2)To handle different scales of crew scheduling problem,branch and pricing method,linear relaxing method and Lagrange heuristic algorithm were applied to solve the integer programing problem,in which branch and pricing method with the strong branching strategy was used to solve small scale problem,linear relaxing method was used to solve the medium scale problem,and Lagrange heuristic algorithm was used to solve large scale problem.(3)To handle the disadvantages of the network generation algorithm and the iterative procedure,two strategies were proposed,one is Time Interval Based Network Generation Strategy and the other is Inferior Shift Elimination Strategy.The Improvement of these two strategies was analyzed in the case study.(4)At last,the influence of the duration of pieces and the temporal distribution to the crew scheduling is analyzed in the case study.