Crew Scheduling Optimization For Urban Rail Transit System With Crew Resources Sharing

The urban rail transit system in China is under rapid development.Large-scale networks have been formed in many cities.However,there is still a new research on operation organization methods and technologies based on network resources sharing.In this context,this study aims to address the crew planning problem through crew resources sharing,where crew members and bases are shared among different lines without considering cross-line trains.The significance of crew resources sharing come in two parts.Firstly,the spatial and temporal distribution of crew tasks is unbalanced and differs from different lines.Sharing can improve the utilization efficiency of crew resources and obtain a better crew schedule.Secondly,by sharing crew members and bases,crew members can choose the nearest crew base for their commute,which saves plenty of commuting time.In addition,the collaborative optimization of multiple lines will increase the solution space of the crew planning problem,which can better meet the preferences of different crew members.This paper first analyzes the impact of the crew resources sharing on the crew scheduling and crew rostering problems.Afterwards,the optimization problems of crew scheduling and crew rostering under crew resources sharing are studied,respectively.Finally,the optimization method of crew planning problem under the fixed-shift system,which is widely applied in domestic subways,is discussed.The main research contents and results are as follows:(1)This paper analyzes the impact of crew resources sharing on crew scheduling and crew rostering problems.The analysis shows that sharing crew resources will greatly increase the scale of the problem and the difficulty of solving.Furthermore,for the crew scheduling problem,cross-line duties need to be additionally considered,and it has an impact on the attributes of the crew tasks and shifts,the feasibility constraints of shifts,constraints among shifts,and robustness requirements.For the crew rostering problem,the satisfaction of crew members for the crew schedule can be better improved through the crew resources sharing,and there will be different specific manifestations for different rostering systems.(2)An extended set coverage model is constructed to solve the crew scheduling problem under crew resources sharing.In addition,multi-layer networks are designed considering cross-line duties and impact of the crew resources sharing.All feasible shifts are able to be represented by the generated networks.For the solution method,the column generation technique combined with the network model is used to solve the linear relaxation problem,and the column fixing technique is applied to obtain the integer solution.Case studies are based on three real-world lines under the same operating company of Beijing Subway and their conclusions are given as follows:(1)The proposed solution method can solve the large-scale crew scheduling problem which consists of three subway lines,and the Gap value does not exceed 0.85%;(2)Sharing crew resources will increase the computation time,but it can slightly increase the efficiency of the crew schedule,and reduce the number of shifts.(3)The crew rostering problem considering crew resources sharing is divided into two stages: rostering division and rostering allocation.In the rostering division stage,a network flow model is built based on rostering status and the optimization objective is the satisfaction of crew preferences.In the rostering allocation stage,an improved discrete artificial bee colony algorithm that introduces the neighbourhood search mechanism is designed to optimize the balance of the "work hardship".The results of case studies are given as follows:(1)The proposed solution method can well solve the crew rostering problem under crew resources sharing;(2)Sharing crew resources can improve the satisfaction of crew preferences and the balance of the "work hardship" of crew members,and reduce the commute time.(4)For the crew planning problem under crew resources sharing in a fixed shift system,the crew scheduling and crew rostering problem are adjusted and redesigned,respectively.For the crew scheduling problem,additional consideration is given to the proportion constraints of shift type,and a fallback mechanism is designed to ensure the solution quality when the constraints become complex.For the crew rostering problem,the rostering mechanism is adjusted to meet the crew’s preference of choosing the nearest crew base for their commute.Furthermore,the model and algorithm are designed according to the characteristics of fixed shift system.The results of case studies are as follows:(1)The proposed solution method can well solve the crew planning problem under crew resources sharing in a fixed shift system;(2)In the fixed shift system,sharing crew resources can improve the balance of the "work hardship" of crew members,reduce the number of crew members,and save considerable commute time when considering the proportion constraints for shifts with different commuting stations.