基于贪婪随机自适应大邻域搜索算法的带时间窗多行程车辆路径问题
随着经济的快速发展,物流配送需求也急剧增加且配送场景呈现多元化特点。对于物流配送常见的带时间窗多行程车辆路径问题(MTVRPTW),本文研究第一层级优化目标为最小化配送迟到时长和工作超时时长,第二层级优化目标为最小化车辆的数目,第三层级优化目标分别为最小化总体在途时长和最小化总体工作时长的MTVRPTW问题。本文研究不同优化目标下的MTVRPTW问题,并对不同优化目标下的MTVRPTW问题进行模型构建和求解,以更好服务物流企业的调度决策,降低企业成本,提高企业竞争力。具体的研究工作如下:(1)对MTVRPTW问题的研究现状进行文献综述,分析目前研究成果存在的问题,并对求解车辆路径问题的算法进行了分类阐述及优缺点比较。通过对MTVRPTW问题进行分析,将最小化配送迟到时长和工作超时时长作为第一层级优化目标,将最小化车辆数目作为第二层级优化目标,而第三层级优化目标分别考虑最小化在途时长和最小化工作时长两类情况。(2)在构建不同优化目标下的MTVRPTW问题的数学模型基础上,设计了求解MTVRPTW问题的贪婪随机自适应大邻域搜索算法(GRALNS)的求解流程。首先引入贪婪随机自适应搜索的构建阶段产生高质量初始解,然后在大邻域探索阶段,设计删除策略、插入策略和车辆减少策略对该初始解进行邻域探索,逐步优化车辆行程方案的服务迟到和工作超时情况、车辆数目以及车辆在途时长(或工作时长)。(3)在公开数据集的9组数据实例上进行仿真实验以验证求解方案的有效性。论文首先将本文提出的贪婪随机自适应大邻域搜索算法与原始大邻域搜索算法进行对比,结果显示本文提出的GRALNS算法可以在输出满意解的稳定性上更优,且多次实验结果表明,GRALNS在多数数据集上的搜索结果更优;最后对两类决策角度不同产生的车辆行程方案的成本差异进行对比和分析。
- 作者：
- 江恩涛
- 学位授予单位：
- 深圳大学
- 授予学位：
- 硕士
- 学位年度：
- 2020年
- 导师姓名：
- 甘小冰
- 中图分类号：
- F252；O224
- 关键词：
- 带时间窗；多行程；大邻域搜索；贪婪随机自适应搜索
-