基于蚂蚁算法的公交驾驶员调度问题研究

论文摘要

公共交通在城市交通中占据主体地位,而驾驶员调度问题则是公共交通系统运营管理中的一个重要的问题,直接影响到公交公司的运营成本和服务质量。在国外,已经有比较成熟的驾驶员调度软件系统,而国内公交系统的特殊性,使得国外的研究成果和应用技术很难直接套用。因此驾驶员调度问题正在得到越来越多的国内研究者的关注。另一方面,驾驶员调度问题本身还有一些问题没有得到很好的解决,比如时间窗问题、用餐时间问题等,值得进行进一步研究。本文研究利用蚂蚁算法来解决公共交通中公共汽车驾驶员调度的问题。蚂蚁算法是一种带有正反馈机制的启发式算法,并具有贪婪的特性,在解决路径优化、调度排班这类利用传统数学规划方法很难解决的问题上具有很大的潜力。本文对驾驶员调度问题的数学模型进行了详细分析,根据驾驶员调度问题的特点和其特殊的约束,对蚂蚁算法做了改进,包括:将驾驶员调度特有的规则加入到算法当中,为可设置的参数;采用多只蚂蚁分工进行一个解的搜索;对启发信息进行重新设置等,并通过控制蚂蚁算法中蚂蚁移动的方式解决了驾驶员调度问题的时间窗问题。同时,蚂蚁算法可以直接在行车计划的基础上进行解的搜索,实现了贪婪式的要求。最后利用C#语言实现了蚂蚁算法,并进行了仿真试验,分析了蚂蚁算法的参数对算法性能的影响,得出了经验式的参数优化设置方法,并可以在较短的时间内获得满意解。与禁忌搜索算法的对比表明,对同一原始数据可得出相似的优化结果。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 课题来源
• 1.2 研究目的及意义
• 1.3 驾驶员调度问题的国内外研究现状
• 1.4 本文研究内容及结构安排
• 2 驾驶员调度问题的基本概念与方法
• 2.1 驾驶员调度问题的基本概念
• 2.2 驾驶员调度问题的描述
• 2.3 驾驶员调度问题的解决方法概述与算法选取
• 2.4 本章小结
• 3 驾驶员调度问题的建模
• 3.1 驾驶员调度问题的特点
• 3.2 驾驶员调度问题的建模
• 3.3 本章小结
• 4 蚂蚁算法的改进
• 4.1 蚂蚁算法模型
• 4.2 具有自适应参数的蚂蚁算法改进方法
• 4.3 蚂蚁算法的改进
• 4.4 本章小结
• 5 算法实现与模型求解
• 5.1 驾驶员调度问题的模型与解的表示
• 5.2 原始数据获取和数据预处理
• 5.3 具有自适应参数的蚂蚁算法计算方法
• 5.4 本章小结
• 6 算法仿真
• 6.1 算法的参数设置仿真
• 6.2 与其他算法的仿真结果的比较
• 6.3 本章小结
• 7 总结与展望
• 7.1 全文总结
• 7.2 研究展望
• 致谢
• 参考文献
• 附录1
• 附录2