基于并行遗传算法的驾驶员排班问题研究

发布时间：2018-02-02 05:13

本文关键词： 驾驶员排班问题遗传算法 Hama BSP模型并行遗传算法粗粒度最优解　出处：《北京交通大学》2017年硕士论文　论文类型：学位论文

【摘要】：随着我国城市交通机动化进程的加快,交通需求和交通供给之间的矛盾也越来越突出,解决该问题的一个重要途径就是大力发展公共交通。运营组织与调度作为公共交通系统的核心内容,是实现运营任务的基本保证;而驾驶员排班作为公共交通企业管理调度工作中的重要组成部分,对公共交通的运行效率和运营成本有着决定性作用。科学合理的排班计划不仅可以提高企业的服务质量,还可以有效的减少企业的运营成本。驾驶员排班问题是世界公认的NP-hard问题,其难点在于如何在合理的时间内找到该问题的最优解或者近似最优解。最优解通常需要借助整数规划方法求得,实际问题中,问题规模通常较大,使得整数规划方法的求解时间难以评估:启发式算法虽然无法保证解的最优性,但却很好的平衡了求解时间和解的质量。遗传算法作为启发式算法中一种,具有很好的全局搜索能力和并行能力,但该算法也存在进化时间长,早熟的缺点。针对遗传算法的不足,设计了基于Hama的粗粒度最优解并行模型(Optimal Solution of Corse-Grained Parallel Model Based on Hama,H-OSCGPM)来提高算法的求解效率和求解质量。本文的研究内容和创新点如下:首先,论文介绍了公共交通领域的驾驶员排班问题,揭示了驾驶员排班问题的求解难点,并总结了驾驶员排班问题已有的研究成果。在已有研究的基基础上建立了数学模型。其次,论文设计了面向驾驶员推班的遗传算法(Crew Scheduling Orirented Genetic Algorithm,CSOGA),本文对CSOGA中的变异操作进行了改进,以提高并行算法在进行串行迭代时的求解质量,并用实例验证了CSOGA的有效性。随后,以粗粒度并行思想为指导,设计了基于 Hama的粗粒度最优解模型,对并行过程中的迁移策略、消息的交互处理进行了详细阐述,并对迁移个体的数量和迁移周期进行了确定。最后,论文选取了 6条典型公交线路进行实例验证分析。实验结果表明,并行算法的求解效率和求解质量更优。并行计算结果中,在求解质景得到改善前提条件下,6条线路的加速比可分别达到3.47,2.96,2.96,2.45,2.34和3.20;且加速比与所求问题的规模呈正相关关系,问题的规模越大,获得的加速比越高。综上所述,卡文提出的并行遗传算法,能够在合理的时间能找到驾驶员排班问题的较优解,并为其在其他领域的应用提供了理论支持。
[Abstract]:With the acceleration of motorization of urban traffic in China, the contradiction between traffic demand and traffic supply is becoming more and more prominent. One of the important ways to solve this problem is to develop public transportation vigorously. As the core content of public transportation system, operation organization and dispatch is the basic guarantee to realize the operation task. As an important part of the management and scheduling of public transport enterprises, driver scheduling is an important part. It plays a decisive role in the operation efficiency and operation cost of public transportation. Scientific and reasonable scheduling can not only improve the service quality of enterprises. Can also effectively reduce the operating costs of enterprises. Driver scheduling problem is recognized in the world as a NP-hard problem. The difficulty lies in how to find the optimal solution or approximate optimal solution of the problem in a reasonable time. The optimal solution usually needs to be obtained by means of integer programming. In practical problems, the scale of the problem is usually large. It is difficult to evaluate the solving time of integer programming. Although heuristic algorithm can not guarantee the optimality of solution, it balances the quality of solution time and solution. Genetic algorithm is one of the heuristic algorithms. It has good global search ability and parallel ability, but the algorithm also has the shortcomings of long evolutionary time and premature. The parallel model of coarse-grained optimal solution based on Hama is designed. Optimal Solution of Corse-Grained Parallel Model Based on Hama. H-OSCGPM) is used to improve the efficiency and quality of the algorithm. The contents and innovations of this paper are as follows: firstly, the paper introduces the problem of driver scheduling in the field of public transport. This paper reveals the difficulty of solving the driver scheduling problem, and summarizes the existing research results of the driver scheduling problem. Based on the previous research, the mathematical model is established. Secondly. This paper designs the genetic algorithm crew Scheduling Orirented Genetic algorithm (CSOGA). In this paper, the mutation operation in CSOGA is improved to improve the solution quality of parallel algorithm in serial iteration, and the effectiveness of CSOGA is verified by an example. Under the guidance of coarse-grained parallelism, the coarse-grained optimal solution model based on Hama is designed, and the migration strategy and message interactive processing in parallel process are described in detail. Finally, six typical bus routes are selected for verification and analysis. The experimental results show that. The efficiency and quality of the parallel algorithm are better. The speedup ratio of six lines can reach 3.47 / 2.96 respectively under the condition that the quality of the solution is improved. 2.45, 2.34 and 3.20; And the speedup ratio is positively correlated with the scale of the problem, the larger the problem scale, the higher the speedup ratio. In conclusion, Carvin proposed parallel genetic algorithm. The optimal solution of driver scheduling problem can be found in a reasonable time, and it provides theoretical support for its application in other fields.
【学位授予单位】：北京交通大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：U492.21;TP18

【参考文献】