带时间窗车辆路径问题的分支—切割—定价算法研究
发布时间：2021-04-22 00:46
带时间窗的车辆路径问题（Vehicle Routing Problem with Time Windows,VRPTW）作为物流行业中最常见的组合优化问题之一,其模型结构及算法都具有普遍性和拓展性。通过特定的转化与变形,VRPTW的模型及算法同样也适用于其他大多数的组合优化场景,公交线路规划、港口设备协同调度等资源分配问题都与其有着相似的数学结构。因此,对车辆路径问题的研究同样有助于推动其他相关领域的发展,如何有效提升该问题的求解效率对物流行业的发展有直接且重大的影响。本文将以精确算法作为研究方向,对VRPTW进行较为全面的理论探究。目前针对VRPTW精确算法的研究主要分为两个方向:整数规划以及动态规划。因VRPTW的求解属于强NP-hard问题,大多数学者更倾向于选择可在伪多项式时间内完成求解的动态规划来进行探究。而动态规划所求得的最优解的理论下界质量较差。且在时间窗约束较宽的情况下,其求解性能并不优于整数规划。相比之下,整数规划则更加灵活,它可以通过合并分支决策或加入有效不等式来实现高效求解。因此,本文将以整数规划为理论基础,对VRPTW进行算法优化。主要提出并实现的创新点及研究成...
【文章来源】：武汉理工大学湖北省 211工程院校 教育部直属院校
【文章页数】：77 页
【学位级别】：硕士
【文章目录】：
摘要
Abstract
第1章 绪论
1.1 研究背景及意义
1.1.1 研究背景
1.1.2 研究意义
1.2 课题来源
1.3 国内外研究现状
1.3.1 车辆路径问题研究
1.3.2 带时间窗的车辆路径问题研究
1.4 研究内容及结构安排
第2章 相关理论及技术
2.1 多面体理论
2.1.1 仿射集
2.1.2 多面体及小平面
2.2 最短路径问题
2.3 带时间窗的车辆路径问题描述
2.3.1 问题定义与假设
2.3.2 数学描述
2.4 整数线性规划
2.4.1 分支定界
2.4.2 列生成
2.4.3 割平面
2.5 基于三维多商品网络流的数学模型
2.6 基于路径不等式的数学模型
2.7 本章小结
第3章 带时间窗车辆路径问题的模型研究
3.1 基于集合划分的数学模型
3.1.1 主问题
3.1.2 子问题
3.2 基于二维车流的数学模型
3.3 本章小结
第4章 带资源约束的基本最短路问题
4.1 ESPPRC问题描述与数学模型
4.1.1 问题描述
4.1.2 数学模型
4.2 统治规则
4.2.1 动态规划的统治规则
4.2.2 整数规划的统治规则
4.3 多面体理论分析
4.3.1 两点加强割集不等式
4.3.2 三点加强割集不等式
4.4 有效不等式
4.4.1 点边不等式
4.4.2 时间前后不等式
4.4.3 顺序前后不等式
4.5 本章小结
第5章 实验设计与结果分析
5.1 ESPPRC实验设计与结果分析
5.1.1 数据来源与实验环境
5.1.2 实验设置与参数说明
5.1.3 结果分析
5.2 VRPTW实验设计与结果分析
5.2.1 数据来源与实验环境
5.2.2 实验设置与参数说明
5.2.3 结果分析
5.3 本章小结
第6章 总结与展望
6.1 全文总结
6.2 研究展望
致谢
参考文献
攻读硕士期间研究成果和参与项目
一、发表论文
二、参与项目
【参考文献】：
期刊论文
[1]求解带时间窗取送货问题的遗传算法[J]. 潘立军,符卓. 系统工程理论与实践. 2012(01)
[2]一种改进的Dijkstra算法在嵌入式GIS中的应用[J]. 刘志宇,杨柳. 计算机应用与软件. 2009(12)
[3]带时间窗和随机时间车辆路径问题:模型和算法[J]. 李相勇,田澎. 系统工程理论与实践. 2009(08)
[4]用单亲遗传算法求解配送车辆调度问题的研究[J]. 郎茂祥. 交通与计算机. 2006(01)
[5]车辆路径问题（VRP）的蚂蚁搜索算法[J]. 崔雪丽,马良,范炳全. 系统工程学报. 2004(04)
[6]基于模拟退火遗传算法的车辆路径问题研究[J]. 许国平,叶效锋,鲍立威. 工业控制计算机. 2004(06)
[7]有时间窗的集货送货一体化车辆路径规划启发式算法研究[J]. 霍佳震,张磊. 物流技术. 2004(05)
[8]带装载能力约束的开放式车辆路径问题及其禁忌搜索算法研究[J]. 符卓. 系统工程理论与实践. 2004(03)
[9]有时间窗车辆路径问题的改进遗传算法[J]. 张丽萍,柴跃廷,曹瑞. 计算机集成制造系统-CIMS. 2002(06)
[10]供应链中车辆路径问题的研究进展及前景[J]. 祝崇隽,刘民,吴澄. 计算机集成制造系统-CIMS. 2001(11)
硕士论文
[1]带时间窗车辆路径问题的精确算法研究[D]. 答家瑞.武汉理工大学 2017
本文编号：3152824
【文章来源】：武汉理工大学湖北省 211工程院校 教育部直属院校
【文章页数】：77 页
【学位级别】：硕士
【文章目录】：
摘要
Abstract
第1章 绪论
1.1 研究背景及意义
1.1.1 研究背景
1.1.2 研究意义
1.2 课题来源
1.3 国内外研究现状
1.3.1 车辆路径问题研究
1.3.2 带时间窗的车辆路径问题研究
1.4 研究内容及结构安排
第2章 相关理论及技术
2.1 多面体理论
2.1.1 仿射集
2.1.2 多面体及小平面
2.2 最短路径问题
2.3 带时间窗的车辆路径问题描述
2.3.1 问题定义与假设
2.3.2 数学描述
2.4 整数线性规划
2.4.1 分支定界
2.4.2 列生成
2.4.3 割平面
2.5 基于三维多商品网络流的数学模型
2.6 基于路径不等式的数学模型
2.7 本章小结
第3章 带时间窗车辆路径问题的模型研究
3.1 基于集合划分的数学模型
3.1.1 主问题
3.1.2 子问题
3.2 基于二维车流的数学模型
3.3 本章小结
第4章 带资源约束的基本最短路问题
4.1 ESPPRC问题描述与数学模型
4.1.1 问题描述
4.1.2 数学模型
4.2 统治规则
4.2.1 动态规划的统治规则
4.2.2 整数规划的统治规则
4.3 多面体理论分析
4.3.1 两点加强割集不等式
4.3.2 三点加强割集不等式
4.4 有效不等式
4.4.1 点边不等式
4.4.2 时间前后不等式
4.4.3 顺序前后不等式
4.5 本章小结
第5章 实验设计与结果分析
5.1 ESPPRC实验设计与结果分析
5.1.1 数据来源与实验环境
5.1.2 实验设置与参数说明
5.1.3 结果分析
5.2 VRPTW实验设计与结果分析
5.2.1 数据来源与实验环境
5.2.2 实验设置与参数说明
5.2.3 结果分析
5.3 本章小结
第6章 总结与展望
6.1 全文总结
6.2 研究展望
致谢
参考文献
攻读硕士期间研究成果和参与项目
一、发表论文
二、参与项目
【参考文献】：
期刊论文
[1]求解带时间窗取送货问题的遗传算法[J]. 潘立军,符卓. 系统工程理论与实践. 2012(01)
[2]一种改进的Dijkstra算法在嵌入式GIS中的应用[J]. 刘志宇,杨柳. 计算机应用与软件. 2009(12)
[3]带时间窗和随机时间车辆路径问题:模型和算法[J]. 李相勇,田澎. 系统工程理论与实践. 2009(08)
[4]用单亲遗传算法求解配送车辆调度问题的研究[J]. 郎茂祥. 交通与计算机. 2006(01)
[5]车辆路径问题（VRP）的蚂蚁搜索算法[J]. 崔雪丽,马良,范炳全. 系统工程学报. 2004(04)
[6]基于模拟退火遗传算法的车辆路径问题研究[J]. 许国平,叶效锋,鲍立威. 工业控制计算机. 2004(06)
[7]有时间窗的集货送货一体化车辆路径规划启发式算法研究[J]. 霍佳震,张磊. 物流技术. 2004(05)
[8]带装载能力约束的开放式车辆路径问题及其禁忌搜索算法研究[J]. 符卓. 系统工程理论与实践. 2004(03)
[9]有时间窗车辆路径问题的改进遗传算法[J]. 张丽萍,柴跃廷,曹瑞. 计算机集成制造系统-CIMS. 2002(06)
[10]供应链中车辆路径问题的研究进展及前景[J]. 祝崇隽,刘民,吴澄. 计算机集成制造系统-CIMS. 2001(11)
硕士论文
[1]带时间窗车辆路径问题的精确算法研究[D]. 答家瑞.武汉理工大学 2017
本文编号：3152824
本文链接：https://www.wllwen.com/kejilunwen/qiche/3152824.html
