原文传递
考虑出行时间相关性的最优路径搜索算法及应用
| 论文题名： | 考虑出行时间相关性的最优路径搜索算法及应用 |
| 关键词： | 路径搜索算法;网络不确定性;出行时间;最优路径;交通网络 |
| 摘要： | 最优路径搜索问题是算法研究领域长期关注的问题，其在交通、通信以及地理信息系统中有着广泛的应用。从不确定性的角度研究最优路径搜索问题，是近年来新的热点研究问题。本文基于考虑交通网络中出行时间的不确定性的最优路径搜索算法，重点探讨了在考虑不同路段之间的出行时间的相关性条件下，如何搜索最优的可靠路径搜索算法以及节能路径的搜索算法。 第一章绪论部分简要介绍了不确定条件下的可靠路径搜索问题的研究背景、意义，并且探讨了不确定条件下的可靠路径搜索算法的研究历史与现状,论述了一些经典的路径搜索算法。 第二章研究了考虑路段出行时间相关性的可靠路径搜索问题，现有的研究中很少有算法能够考虑该问题。本章所提出的算法利用不等式放缩的技巧，给出了有效出行时间的上界和下界，以最小的有效出行时间的上界为阈值，避免搜索不可能成为最优的路径，节约了计算量，证明了算法的全局最优性，最后给出了算例验证了算法的有效性和正确性。 第三章研究了基于最优路径的关键路段问题，本章在第二章算法的基础上，给出了相关的数学模型，以整个网络的最小化系统总时间为目标函数，找出对系统总时间影响最大的路段定义为关键路段，通过对关键路段的改进可以最大限度的缓解整个网络的拥堵情况。 第四章研究了基于可靠性和车辆节能两个目标的最优路径问题。运用多目标规划的理论，结合K短路算法和第二章的可靠路径搜索算法，给出了搜索Pareto有效解的方法以及相关的证明，最后还通过两个不同规模的中、大型网络验证了算法的有效性。 |
| 作者： | 沈良 |
| 专业： | 计算数学 |
| 导师： | 邵虎 |
| 授予学位： | 硕士 |
| 授予学位单位： | 中国矿业大学 |
| 学位年度： | 2016 |
| 正文语种： | 中文 |
检索历史
应用推荐
