论文部分内容阅读
物流调度在现代社会经济活动中的地位越来越重要。随着物流活动在经济活动中的比重越来越大，降低物流成本已经成为企业降低运营成本的一个核心。车辆路径问题(VRP, Vehicle Route Problem)由旅行商问题（TSP, Travelling Salesman Problem）发展而来，自提出以来，引起了众多学者的广泛关注和深入研究。经过数十年的研究，众多的车辆路径问题模型以及它们的解决算法已被提出。车辆路径问题是组合优化领域中典型的NP-hard(NP-Hard, non-deterministicpolynomial hard)问题，可分为静态车辆路径问题(SVRP, Static Vehicle Route Problem)和动态车辆路径问题(DVRP, Dynamic Vehicle Route Problem)。动态车辆路径问题是一种需求实时送达的，由静态车辆路径问题发展而来的新的车辆路径问题模型，是对现实物流更加真实的抽象。动态车辆路径问题也是比静态车辆路径问题更加复杂的一类NP-hard问题，目前的计算机和确定性算法无法在合理的时间范围内得到车辆路径问题的最优解。因此，针对动态车辆路径问题的研究，现主要集中在采用启发式算法求其近似解。几乎所有的启发式算法都是在全局搜索和局部搜索之间寻求一种平衡，以使得算法的效率和性能尽可能优化。变邻域搜索算法是一种快速有效的启发式算法，但易陷入局部最优化。采用变邻域搜索算法解决动态车辆路径问题，即需寻找一种全局搜索与局部搜索的一种平衡，使动态车辆路径问题的目标函数尽可能小，且保持可接受的算法速度。变邻域搜索算法的邻域结构代表了所求问题的搜索空间或解空间，对邻域结构的表示是变邻域搜索算法的核心。对搜索空间解进行搜索时，搜索策略对算法效率的具有很大的影响。在局部搜索算法中，多采用类似爬山法（hill-climbing method）的搜索策略，以尽快找到优化解，而此方法很容易陷入局部最优。据此，文章提出改进基本变邻域搜索算法的邻域结构，保证所求问题的最优解包含在搜索空间中。另外，通过调整搜索策略即调整变邻域搜索算法的局部搜索方法，使算法能够尽快找到局部最优解。应用改进变邻域搜索算法求解动态车辆路径问题时，根据动态车辆路径问题本身的特点，为加快搜索速度，在搜索的过程中加入了粒度搜索。实验结果显示，改进的算法对解决动态车辆路径问题具有较好的有效性。本文主要做了如下工作：（1）回顾车辆路径问题模型，分析其特点，并详细介绍了动态车辆路径问题模型；（2）介绍基本变邻域搜索算法的结构和特点，并分析其优缺点，提出需改进的方面；（3）针对基本变邻域搜索算法的问题，从算法的领域结构和局部搜索出发，提出改进变邻域搜索算法；(4)根据车辆路径问题所具有的特点，结合粒度搜索提高算法效率，将改进算法用于求解动态车辆路径问题；(5)最后，对实验结果进行分析和总结；