Study On Theory And Methods Of Crew Planning Problem Of High-speed Railway

Crew planning problem is one of the most important problems that every transportation mode has to face. The essence of this problem is making the working plan of crews after given the running scheduling and the continuation relationship of conveyance. In the field of air transportation and urban transportation, the use of crew costs in the direct production cost just less than fuel cost. As the construction and development of China high-speed railway, the working requirement of crews become more and more harsh, and the proportion of its cost in the total cost also increasing gradually, thus the effect of crew plan in the operation and management of high-speed railway become increasingly significant. The quality of the crew plan will be the key factor that influences the using efficiency of crew members of high-speed railway.Crew planning problem usually divide into two sub-problems, which are crew scheduling problem and crew rostering problem. The target of crew scheduling problem is to decide the connection between all segments according to the train working diagram and the EMU plan, and minimize the crew member used in this stage. In contrast, the goal of crew rostering problem is to decide the working schedule of crew members in certain period, and balance the workload of all crew members. The weaving of crew rostering problem usually based on the result of crew scheduling problem. Based on the research results at home and abroad, this dissertation studies the crew planning problem of China high-speed railway, build the optimization models of related problems, and designed effective algorithms for each model combined with modern optimization algorithms. The main research works of the dissertation are as follows:1. The choosing of institution, classification, influence factor, weaving flow and commonly used model techniques of crew planning problem of China high-speed railway are analyzed to found the theory foundation for further study. The basic principles, application flow, parameter design methods, main characteristics and commonly used improving strategies of simulated annealing algorithm and ant colony algorithm are summarized to build the algorithm foundation for solving the related optimization models founded in the study process of crew planning problem.2. The weaving of crew scheduling plan is divided into two stages on the basis of analyzing the characteristic of crew scheduling problem. The set covering model is chose to formulate the problem with the consideration of the existence of deadhead and the difficulty for solving different models. The optimization model aimed at minimize the total cost of crew segments is founded and the ant colony algorithm is designed for solving the model. The assignment model for the matching of crew segments is build according to the characteristic that the segments departure from or arrive at the same relief station are equally in train working diagram in pairs. Furthermore, this problem is described as traveling salesman problem and an ant colony algorithm for solving this problem is designed.3. Two different forms of crew rostering problem are studied. For the single-circulation crew rostering problem, an optimization model is build with the objectives of minimize the connection time and balance of redundant time in connection time. By further analyze, we conclude that the essence of this problem is a traveling salesman problem with restrictions of travel distance. Ant colony algorithm based on dynamic heuristic information is designed according to the characteristic of this problem. For the crew rostering problem with given periodic, the weaving procedure is divide into two stage, optimization model and solving algorithm are studied for each stage, respectively.4. Based on the advantage and disadvantage of the weaving flow of crew plan, and aimed at global optimization, this dissertation studies the integrated optimization of crew planning problem from two different points of view which are modeling optimization and weaving flow optimization. Build optimization model of crew planning problem by consider the objectives and constraints of each stage simultaneously, and then designed ant colony algorithm. For the algorithm designed for solving the crew scheduling problem improve the solution iteratively, this dissertation designed various control strategies to improve the weaving flow of crew planning problem.5. Two improved ant colony algorithms are designed on the basis of analyzing the characteristic of ant colony algorithm and the structure of the sub-problems in crew planning problem. Then, the ant colony algorithm with double pheromone and heuristic information and the ant colony algorithm with dynamic heuristic information are used to solving relative problems.The research above has not only practical significance for improving the quality of crew plan of high-speed railway and realize the intelligent weaving of crew plan, but also has reference value for the research and design of decision support system for the crew planning problem of China high-speed railway.