Research On The Optimization Of Crew Planning For High Speed Railway

With the continuous formation of the networked operation pattern of high speed railway in our country,the problems of its transport organization tend to be refined and complicated gradually.The crew planing,as one of the important sub-problems of the high speed railway transportation organization,also tend to be more complicated in background,more efficient in process and more humanized in result.The majority of existing crew planning is set up manually resulting in low efficiency.The quality of the results often depends on the experience of the staff and was difficult to adjust.Therefore,it is of great significance to study a set of scientific and efficient methods for crew planning of high speed railways for improving the efficiency and reducing the cost of operation.First of all,this paper analyzes the limitations of the existing research results with the help of setting up a general model describing the ’relative time’ constraint based on time-space connection network.Based on the analysis of the characteristics of the high speed railway crew planning problem,this paper studies the solving strategy of crew scheduling problem and the crew rostering problem.For the crew scheduling problem,this paper,for the first time,considers the dining rules of ’fixed time window’ for lunch and dinner,and classifies this problem as a large-scale combinatorial optimization problem considering the ’mixing time’ constraint.Based on time-space-state network and Lagrangian relaxation algorithm,the paper proposes a effective solving strategy.For crew rostering problem,this paper,for the first time,proposes the concepts of’closed-loop rostering’ and ’non closed-loop rostering’ to define two reasonable crew rostering scheme of single-cycle crew rostering and classifies this problem as a combinatorial optimization problem only considering the ’relative time’ constraint.Based on time-space connection network and network flow model,the paper proposes a accurate solving strategy.Secondly,the paper studies the solving method of the crew scheduling problem problem.By defining the ’state’ dimension of the problem in the time-space-state network and two kinds of ’fixed time window’ dining rules,crew rules are transformed into ’point’ generation strategy(The recursion principle of time-space node state coordinates)and ’arc’ generation strategy(The decision condition of crew tasks transformation).Based on the generation strategy,the time-space-state network is constructed so that the crew rules can be fully portrayed in the network to control the network scale and simplify the mathematical model.Then,the paper establishes network flow model based on time-space-state network and designed the Lagrangian relaxation algorithm which decomposes the crew scheduling problem from the combinatorial optimization problem of multi-crew duties into the set of the shortest-path time-space problems for single-crew duty.Aiming at the characteristics of ’strong symmetry’ and ’overrelaxation’,the paper proposes the linear inequality constraints to break ’symmetry’ and control ’overrelaxation’ to accelerate the convergence of the algorithm and improve the quality of the lower bound.Thirdly,the paper studies the solving method of the crew rostering problem.Aiming at the characteristics of a single-cycle crew rostering problem,the paper establishes a time-space connection network which can describe crews’ different rest types,turns the problem into a traveling salesman problem taking into account the midway rest and designs an iterative optimization algorithm solved by CPLEX.The results are compared with the existing results to analyze the effect of the result.Aiming at the problem that can not be solved easily because of its large scale,this paper puts forward the principle of setting the time window of crew rules to speed up the solution of the problem and gives the proof of the principle.Finally,this paper solves two examples of an inter-city railway and regional high speed railway network respectively.The results showed that the proposed method could high-quality and efficiently solve the large-scale combinatorial optimization problem with ’mixing time’ constraints such as high speed railway crew scheduling problem and crew rostering problem only considering ’relative time’ constraints.