带有资源约束的基础最短路径问题的算法研究

发布时间：2021-04-21 21:36

　　最短路径问题为图论中的一个经典问题,其算法的研究在优化问题中有着重要的理论价值,很多现实优化问题都可以转化为最短路径问题来进行求解。随着科学技术的飞速发展和日常生活的需要,传统的最短路径问题无法满足人们的需求,由此衍生出了带有各类资源约束的最短路径问题,本文中所研究的问题模型就是其中的一种,为带有时间窗和容量资源约束的基本最短路径问题（ESPPRC）。本文针对带有资源约束的基本最短路径问题的精确算法进行了研究,并发现现有精确算法的求解效率还无法满足需要,因此尝试提出了一种改进算法来加快求得精确解的速率。本文通过对带有资源约束的基础最短路径问题的三种求解思想的研究与分析,找到了每种算法各自的优点和存在的问题,并提出了改进的思路和方向。在原有方法的基础上,提出了对ESPPRC问题的一种改进算法,算法结合了脉冲算法中的下界矩阵的思想和标号算法中利用label存储局部路径的思想,并利用分支定界、剪枝策略来缩小搜索空间。算法将下界矩阵的存储内容由局部路径成本扩充为完整的路径信息,并利用这个矩阵设计了拼接路径策略来提高算法的求解速率,并提出了两种排序策略分别针对稀疏图和稠密图来优化矩阵的生成顺序,... 

【文章来源】：大连理工大学辽宁省 211工程院校 985工程院校 教育部直属院校

【文章页数】：64 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
1 绪论
    1.1 研究背景及研究意义
    1.2 国内外研究现状
    1.3 主要研究内容
    1.4 章节安排
2 相关问题介绍
    2.1 最短路径问题分析
        2.1.1 最短路径问题定义
        2.1.2 经典算法分析
    2.2 多约束最短路径问题
        2.2.1 问题概述
        2.2.2 问题分析
        2.2.3 相关算法介绍
    2.3 本章小结
3 ESPPRC问题模型与算法分析
    3.1 问题描述和数学模型
        3.1.1 ESPPRC问题描述
        3.1.2 车辆路径问题的列生成算法
        3.1.3 ESPPRC问题数学模型
    3.2 算法分析
        3.2.1 求解思路分析
        3.2.2 改进算法介绍
    3.3 pulse算法
        3.3.1 pulse算法主要思想
        3.3.2 pulse算法计算实例与缺陷分析
    3.4 本章小结
4 ESPPRC问题的改进算法
    4.1 问题定义
    4.2 改进算法设计
        4.2.1 改进思路
        4.2.2 路径拼接
        4.2.3 优化下界矩阵生成顺序
    4.3 算法可行性分析
    4.4 算法实现
    4.5 本章小结
5 数值实验
    5.1 实验结果
        5.1.1 环境和实例分析
        5.1.2 实验结果
    5.2 结果对比
    5.3 ESPPRC问题的其他应用
    5.4 本章小结
结论
参考文献
致谢


【参考文献】：
期刊论文
[1]复杂约束条件下求解带权最短路径方法[J]. 杨澜,段卓辉,邓宏涛.  江汉大学学报(自然科学版). 2018(04)
[2]带时间窗的车辆路径问题的精确算法研究[J]. 答家瑞,郑澜波.  物流技术. 2017(06)
[3]过必经节点集的动态剪枝搜索算法[J]. 姚博,冯宏伟,高原,马佳丽,冯筠.  计算机工程与应用. 2017(15)
[4]移动对等网络中的感知蚁群路由算法[J]. 曲大鹏,王兴伟,黄敏.  计算机学报. 2013(07)



本文编号：3152533