基于改进蚁群算法的车辆调度研究

作     者：王坤楠 

作者单位：暨南大学 

学位级别：硕士

导师姓名：孟小华

授予年度：2011年

学科分类：08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：蚁群算法 车辆路径问题 信息素 物流配送 

摘      要：车辆路径问题VRP(Vehicle Routing Problem),是物流调度系统中关键的一环,其作用是为配送车辆选取合理的运输路径,一个好的物流调度系统不仅可以提升服务质量及资源利用率,还能够增强客户对企业服务的满意度,进而提升企业的竞争力。 蚁群算法是一种模拟进化算法,它是受到自然界中真实蚁群觅食行为的启发而提出的,在求解VRP(车辆路径优化)等组合优化问题上取得了有效的成果。本文研究的主要目的是在已有蚁群算法的基础上,对其做进一步的改进,使之适用于求解车辆路径优化问题。本文对蚁群算法的改进策略主要有以下几个方面：首先,τmax(信息素最大值)的初始值的设置的改进,本文使用贪心算法来生成初始可行路线,得到初始的路径总长度L,从而制定τmax的初始值;其次,信息素更新的改进,在MMAS(最大最小蚁群算法)算法中,只对最优解路径上的信息素进行更新,在本文中将对最优解以及接近最优解蚂蚁所经过路径上的信息素进行更新,这样,在这些次优解的路径上的信息素浓度将会比其它路径上的信息素浓度积累的更快,能够有效的避免算法的过早收敛。最后,对ρ(信息素挥发因子)的自适应调整,用来防止因p过小而降低算法的收敛速度,这样可以提高了算法的收敛速度和算法的全局搜索能力。 通过仿真实验,证明了论文提出的改进蚁群算法,不仅改善了蚁群算法的性能,还在VRP问题上的应用取得了较好的效果,证实了该算法的有效性。