Study On Optimization Of Crew Pairing In Urban Rail Transit Based On Column Generation Algorithm

With the progress of our society and the rapid development of economy,urban rail transit has entered a stage of rapid development.Crew pairing is the basis of crew scheduling and an important part of daily operation of urban rail transit.At present,there are few studies on the pairing of rail transit crew tasks in China.Most of them are made by manual preparation,which is inefficient and costly.In view of the difficulties existing in the present stage of crew pairing in urban rail transit,this paper proposes an optimization method of crew pairing in urban rail transit based on column generation algorithm,which has important practical significance for improving the level of crew scheduling.The crew pairing is based on the given train operation diagram,according to the train service number in the train operation diagram,the pairing and the formation of reasonable crew task.Crew scheduling is to arrange crew members’ rotation tasks in a certain stage through crew task rotation according to the result of crew pairing.In this paper,according to the actual situation,the problem of crew pairing in urban rail transit is studied.By analyzing the characteristics of different types of shifts,the crew pairing results are obtained,and then the crew scheduling of different types of shifts are generated.The crew pairing problem is a large scale integer programming problem that is difficult to solve.First of all,on the basis of the existing studies on the pairing of cabin crew tasks,this paper analyzes the characteristics of shifts in different time periods,defines the tasks performed by the attendant during the meal period as "meal replacement" shifts,and obtains four types of shifts: morning shift,day shift,night shift and meal replacement.Then,using the idea of set coverage problem for reference,a "path-based" model of crew task pairing problem is constructed.Furthermore,an accurate algorithm based on column generation and branch and bound technology is designed to solve the integer solution of the crew pairing problem.In the process of solving the cabin crew pairing problem by using the column generation algorithm,we firstly relaxed the cabin crew pairing model linearly and introduced artificial variables,and calculated the limiting master problem using the Nairobi business optimization software.According to the solving dual results and the characteristics of different shifts,build and solve the pricing problems of the column generation algorithm,and then judge whether to terminate the column generation algorithm or add new variables.In order to better solve the pricing problem,based on the characteristics of different shifts,this paper designed the multi-label shortest circuit algorithm and Dijkstra algorithm respectively.Among them,the Dijkstra algorithm was used to solve the morning shift,and the multi-label shortest circuit algorithm was used for the day shift,night shift and alternate shift.Since the result of the column generation algorithm is the solution after linear relaxation,and the original problem belongs to the integer programming problem,this paper designs an improved branch and bound algorithm to obtain the integer solution according to the characteristics of the problem.Finally,the feasibility and effectiveness of the proposed method are verified by numerical experiments based on the actual data of Beijing Subway YIZHUANG Line.