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

摘要

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