周期性车辆路径问题的引导式邻域搜索算法设计及应用

摘要

周期性车辆路径问题（Period Vehicle Routing Problem，PVRP）是车辆路径问题（Vehicle Routing Problem，VRP）的重要分支，是VRP 问题在时间上的扩展，通常VRP 问题解决一天内的路径优化问题，而PVRP则把时间扩展为一个周期内的许多天内的路径优化问题。PVRP 问题在信件或者快递的投递服务、电梯的保养和维修、自动售货机的补充、废物收集等方面有着广泛的应用。
　　 本文详细分析了PVRP 问题和引导式邻域搜索算法（Guided LocalSearch，GLS），并对两方面都做了相关的国内外研究综述。在分析PVRP问题的基础上，设计了两阶段的改进的引导邻域搜索算法（ImprovedGuided Local Search，IGLS）：构建初始解和优化改进。初始解通过修正的Clarke Wright（CW）节约算法来构造。优化阶段的GLS算法是一个比较新的启发式算法，能较好解决包括TSP 问题、其它函数优化及大型调度问题等多种组合优化问题。IGLS算法通过对GLS的改进，把GLS算法中的静态的惩罚系数设计为动态的惩罚系数。对于PVRP 问题，迭代的起始阶段惩罚的弧往往不会再进入满意可行解，因此施以较大惩罚系数，使可行解改进时避免吸纳初始被惩罚的弧；当迭代进入后期，依然存在的较长的弧则很可能构成更好的满意可行解，此时期望较小的惩罚系数，允许较长的弧来构成和改进当前最优解。
　　 本文用国际标准算例对所设计的改进的引导式邻域搜索算法IGLS进行分析。对得到的结果和运算时间与其它算法进行比较，说明了IGLS算法是一种有效的启发式算法。同时还详细对比说明了动态惩罚策略与静态惩罚策略对求解时间和精度的影响，通过鲜明的对比，可以发现动态惩罚策略对问题求解速度有很大改进，精度上也有较大提高。与静态惩罚系数相比，动态惩罚系数用更多的参数对惩罚系数进行控制，结合了问题求解过程的属性，提高了对惩罚系数的控制，使IGLS 更适合PVRP问题的求解。
　　 本文详细介绍了一个第三方物流公司为一些供应商向某大型连锁超市配送中心供货服务的案例，对案例进行了求解分析。通过案例说明了PVRP 问题应用的可行性和有效性。

目录

文摘

英文文摘

声明

第一章绪论

第二章周期性车辆路径问题描述

第三章算法设计

第四章实验分析

第五章案例应用

第六章总结与展望

附录一：程序核心代码

附录二：P02 算例

参考文献

致谢

攻读学位期间发表的论文