论文部分内容阅读
随着我国城市交通机动化进程的加快,交通需求和交通供给之间的矛盾也越来越突出,解决该问题的一个重要途径就是大力发展公共交通。运营组织与调度作为公共交通系统的核心内容,是实现运营任务的基本保证;而驾驶员排班作为公共交通企业管理调度工作中的重要组成部分,对公共交通的运行效率和运营成本有着决定性作用。科学合理的排班计划不仅可以提高企业的服务质量,还可以有效的减少企业的运营成本。驾驶员排班问题是世界公认的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;且加速比与所求问题的规模呈正相关关系,问题的规模越大,获得的加速比越高。综上所述,卡文提出的并行遗传算法,能够在合理的时间能找到驾驶员排班问题的较优解,并为其在其他领域的应用提供了理论支持。