【作者】 田志强；

【导师】 倪少权；

【作者基本信息】 西南交通大学 ， 交通运输规划与管理， 2011， 博士

【摘要】 乘务员运用计划的编制是交通运输领域中各种运输方式都需要面临的重要问题,其实质是在给定运行时刻表及运输工具的接续关系后,制定各类乘务人员的工作计划。在航空运输及城市交通运输领域,乘务员的运用费用在直接生产费用中仅次于燃料费用。随着我国高速铁路的建设和发展,乘务员的工作要求越来越高,其运用费用在生产运营总费用中的比重逐渐加大,乘务计划在运营管理中的作用也越趋明显,计划的编制水平将成为影响高速铁路乘务员运用效率的关键因素。乘务计划的编制过程通常划分为乘务交路计划编制和乘务排班计划编制两个子问题。乘务交路计划主要根据列车运行计划和动车组交路计划来确定值乘区段的接续关系,并确定所需要的最少乘务员数。乘务排班计划则是在综合考虑乘务员休息、培训等的基础上,确定乘务员在一定周期内每天工作的具体安排,并保证乘务员(组)之间工作量的均衡,其编制工作一般是在乘务交路计划的基础上进行。本文在参考国内外研究成果的基础上,研究我国高速铁路乘务计划编制问题,建立了相关问题的优化模型,结合现代优化计算方法,设计了各问题的有效求解算法。论文的主要研究工作如下：1.分析了高速铁路乘务制度选择、乘务计划分类、计划编制影响因素、编制流程及常用建模方法等相关基础理论,为乘务计划编制问题优化模型的建立奠定了理论基础；对智能优化算法中比较具有代表性的模拟退火算法和蚁群算法的基本原理、应用流程、参数设计、主要特点及常用改进进行了归纳和总结,为乘务计划编制问题相关模型求解算法的设计奠定了基础。2.分析了乘务交路计划编制问题的特点,将其划分为值乘区段集合覆盖和乘务交路段匹配两个子问题。考虑到乘务计划中便乘的存在及不同模型的求解难度,选用集合覆盖模型对问题进行表述,并对该形式下可行乘务交路段的费用计算方法进行讨论,建立了以最小化乘务交路段总费用为目标的集合覆盖模型,设计了求解模型的改进蚁群算法。根据成对列车运行计划中以乘务员换乘站到发的乘务交路段数相等的特点,建立了乘务交路段匹配的指派问题模型,进一步分析了其与TSP问题的共性,设计了求解的蚁群算法。3.研究了两种不同形式的高速铁路乘务排班计划编制问题,即单一循环乘务排班计划和给定周期乘务排班计划。对单一循环乘务排班计划,建立了以乘务交路接续总时间最短和乘务交路接续冗余时间分布最均衡为目标的优化模型。分析得出问题的实质是一个带有里程约束的TSP问题,进而根据问题的特点,设计了基于动态启发式信息的蚁群优化算法；对于给定周期乘务排班计划,将其编制过程划分为乘务交路段集合分解和非极大排班方案调整两个阶段,分别建立了优化模型并设计了求解算法。4.在分析高速铁路乘务计划原有编制流程优、缺点的基础上,以系统整体最优为目标,从优化模型的建立及求解和编制流程的改进两个方面对乘务计划的综合优化问题进行了研究。综合考虑乘务计划编制过程中各阶段的优化目标及约束条件,建立了乘务计划综合优化模型,并设计了蚁群算法；针对乘务交路计划编制问题模型迭代式求解的特点,设计了多种交互控制策略对乘务计划编制流程进行改进。5.通过分析蚁群算法的特点及乘务计划编制过程中各子问题的结构,对蚁群算法进行改进,设计了基于双重信息素和启发式信息的蚁群优化算法,以及基于动态启发式信息的蚁群优化算法,应用于求解乘务计划编制过程中相关问题的求解。上述研究不仅对于提高高速铁路乘务计划的编制水平、实现乘务计划编制的智能化具有实际意义,同时对我国高速铁路乘务计划编制决策支持系统的研究与设计也具有参考价值。更多还原

【Abstract】 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.更多还原