带时间窗和装载约束车辆路径问题模型和算法

论文摘要

车辆路径问题作为运筹学和组合优化问题的一个分支,由于其深远的理论价值和实际意义,从发展以来一直作为热点被人们广泛研究。该问题在一定的客户需求和车辆约束下,通过规划车辆的行驶路径实现优化成本的目的。由于实际物流问题的复杂性,车辆路径已经作为一个学科衍生出了很多分支,取得了大量的研究成果。随着目前对冷藏食品的需求量不断增大,多温度食品的配送在近几年得到越来越多的重视。在实际运输中存在这样一类问题,食品对温度的要求不同,冷藏、常温食品只能分别由冷藏、常温车辆运输,同时存在食品即可在常温又可在冷藏条件下运输；同时客户对其商品的服务时间有严格的要求。我们称此问题为带时间窗和装载约束车辆路径问题。在规划此类问题的车辆路径时,需要考虑时间窗和食品温度的双重约束,以降低车辆行驶时间和固定车辆成本为目标,求解非常困难。本文针对带时间窗和装载约束的多车型路径问题进行了数学建模和算法的分析,主要研究工作如下：对问题进行了数学建模,对比了该问题和目前存在的问题的相异性和特殊性,并对目前相关问题常用的算法进行介绍。结合问题特性,修改常用的路径初始化CW算法,以满足问题约束条件。对于生成的初始化解,加入符合问题的启发式,设计了两种对比启发式算法：摧毁-重建方法和带阈值的禁忌算法,进一步的优化解。在带时间窗车辆路径问题的Solomon标准算例基础上生成实验所用的算例。针对上述设计的两种算法,分别进行试验求解,并对比分析两种算法的时效性。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 问题的提出
• 1.2 相关研究对比
• 1.3 相关研究文献综述
• 1.3.1 VRPTW相关文献
• 1.3.2 HVRPTW相关文献
• 1.3.3 MTL相关文献
• 1.4 求解算法研究
• 1.5 HVRPTW-ILC研究难度
• 1.6 本文的结构
• 2 HVRPTW-ILC问题模型构建
• 2.1 车辆路径问题概述
• 2.1.1 问题构成要素
• 2.1.2 问题优化目标
• 2.2 HVRPTW-ILC问题描述
• 2.3 HVRPTW-ILC问题数学模型
• 3 初始化算法
• 3.1 初始化算法框架
• 3.2 时间可行性算法
• 4 摧毁-重建启发式算法
• 4.1 摧毁-重建启发式框架
• 4.2 摧毁-重建算法
• 4.2.1 重建策略
• 4.2.2 新解接受策略
• 5 带阈值的禁忌算法
• 5.1 评价函数
• 5.2 邻域结构
• 5.3 禁忌和特赦原理
• 5.4 阈值更新原则
• 5.5 搜索策略和接受策略
• 5.6 多样性和加强性
• 5.7 TTS算法框架
• 6 算例设计和分析
• 6.1 算例设计
• 6.2 参数设置
• 6.3 实验结果和分析
• 结论
• 参考文献
• 攻读硕士学位期间发表学术论文情况
• 致谢