多车程带时间窗车辆路径问题的模型和算法

论文摘要

车辆路径问题是组合优化和运筹学领域研究的重要问题之一,主要研究满足一定约束条件下的最优车辆路线规划和使用方案,由于其重要的理论研究和实际应用价值,直得到人们的广泛关注。近些年来,人们开始逐渐研究从实际生活生产衍生而出的众多车辆路径问题分支,并取得了大量的研究成果和巨大的经济效益。而在大多数的车辆路径问题研究文献中,均假设车辆在一个工作周期内,完成一次运输任务后将不再被使用,显然这在很多实际应用中不能成立。本文所要研究的就是解决此类问题：一家大型物流公司,拥有一个车场停放着固定数量的车辆用于配送；公司的客户对其服务时间有着严格的限制,必须在事先指定的时间范围内(时间窗)得到服务；一辆车在一个工作周期内,可以完成多次运输任务,每次任务行使的时间必须限定在一个固定范围内。这一类问题可以抽象为多车程带时间窗的车辆路径问题。由于多车程和时间窗的双重约束的引进,对此类问题的求解会变的更加困难。本文针对多车程带时间窗的车辆路径问题的模型和求解算法进行了研究,主要研究工作如下：建立多车程带时间窗车辆路径问题的数学模型,并对求解多车程带时间窗车辆路径问题的常用启发式算法进行了介绍。设计并实现了一种求解多车程带时间窗车辆路径问题的基于车程的启发式算法,开发出符合问题特性的车程表现形式和局部搜索算子,实现了随机性的车程生成和有效的车程分配算法。修改了Solomon和Gehring标准算例,并对提出的算法进行了实验分析,求解结果全部优于当前的最优解,并且在求解质量上有了很大的提高。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 问题的提出
• 1.2 国内外相关研究综述
• 1.2.1 VRPM相关文献
• 1.2.2 VRPTW相关文献
• 1.2.3 VRPMTW相关文献
• 1.2.4 VRPMTW研究总结
• 1.2.5 VRPMTW研究的难度
• 1.3 VRP问题求解算法的研究进展
• 1.4 本文的主要研究工作
• 2 VRPMTW问题模型研究
• 2.1 车辆路径问题综述
• 2.1.1 车辆路径问题约束条件
• 2.1.2 车辆路径问题优化目标
• 2.2 VRPMTW问题的数学模型
• 2.2.1 多车程问题概述
• 2.2.2 时间窗问题概述
• 2.2.3 VRPMTW问题描述
• 2.2.4 VRPMTW问题的数学模型
• 3 求解VRPMTW问题的基于车程的启发式算法
• 3.1 车程构建过程
• 3.2 车程分配过程
• 3.3 Local Search过程
• 3.4 车程池更新过程
• 3.5 车程选择过程
• 4 算例分析
• 4.1 算例描述
• 4.2 参数设置
• 4.3 实验结果和分析
• 结论
• 参考文献
• 攻读硕士学位期间发表学术论文情况
• 致谢