改进变邻域搜索算法在动态车辆路径问题中的研究

摘要

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

目录

封面

声明

中文摘要

英文摘要

目录

第 1 章 绪论

1.1 课题背景及意义

1.2 车辆路径问题研究现状

1.3 本文主要内容及组织结构

第 2 章 变邻域搜索算法

2.1 变邻域搜索算法简介

2.2 变邻域搜索算法基本结构

2.3 变邻域搜索算法结构

2.4 本章小结

第 3 章 变邻域搜索算法的改进

3.1 变邻域搜索算法改进概述

3.2 邻域结构

3.3 邻域转换机制

3.4 局部搜索算法

3.5 最优性分析

3.6 本章小结

第 4 章 改进变邻域搜索算法求解 DVRP 问题

4.1 引言

4.2 DVRP 的问题描述和模型

4.3 算法设计与实现

4.4 实验结果

4.5 本章小结

第 5 章 总结与展望

5.1 总结

5.2 展望

参考文献

附录 A 本文作者在攻读硕士学位期间所发表的论文

附录 B 本文算法的核心代码

致谢