论文部分内容阅读
随着社会的发展,物流受到越来越多的关注,有“第三利润源泉”之称。在我国现阶段,物流成本在GDP中的比重,与发达国家相比,还很落后。降低物流成本,对我国经济的发展有着重要的意义。物流成本的主要部分是配送成本。车辆路径问题(VehicleRouting Problem,VRP)是物流配送问题的一个子问题,它研究正是如何降低配送成本。
VRP是一个典型的NP-hard问题,即使问题规模比较小,求解也比较困难。现在成了组合优化领域里的一个热点问题。国内外许多学者对其进行了广泛的研究。目前,已经产生了许多针对此问题的解决方法。为人们继续深入的研究打下了基础。
本文首先分析了车辆路径问题的研究现状、分类及数学模型,并对常用求解算法进行了总结。其次,分析了粒子群算法的概念、模型和算法步骤,并对标准粒子群算法的特点及参数进行了分析,总结了一些典型的改进算法。
在此基础上,本文设计了两种算法。
第一种是对车辆路径问题进行求解的算法——粒子群算法和蛙跳混合算法(Hybridalgorithm of PSO and SLFA,HAPS)。该算法首先采用粒子群算法产生阶段最优解,然后利用蛙跳算法对阶段最优解进一步优化。利用蛙跳算法(shuffled leap-frog algorithm)强大的全局搜索能力,来弥补粒子群算容易陷入局部最优的缺点,从而达到探索能力和开发能力的平衡,使粒子群算求得更好的最优解。
另一种是,求解带软时间窗的车辆路径问题(Vehicle Routing Problem With Soft TimeWindows,VRPSTW)的混合算法--ACSPSO。该算法首先采用蚁群系统算法产生阶段最优解,以此作为粒子模板,随机生成粒子群,利用粒子群算法在阶段最优解基础上进一步优化。且在蚁群系统算法中,当容量超过限制后,从剩余的客户里选择需求量最大的作为新的起点继续探索路径,直到所有客户都被访问一遍。PSO算法计算速度快,易于实现,但在解决车辆路径问题时,很难直接产生出好的解,在应用到时间窗车辆路径问题时,车辆数目的优化是其无法实现的。而ACS算法能够为求解时间窗车辆路径问题提供优化的车辆数目。
用C语言编程实现,并针对VRP的经典测试集进行求解,优化了实例中的车辆路径；对VRPSTW的经典测试集进行求解,获得了很好的搜索成功率和结果平均值。最终得出这两种算法是求解车辆路径问题的一个可行方法的结论。