考虑出行时间相关性的最优路径搜索算法及应用

摘要

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

目录

封面

声明

致谢

中文摘要

英文摘要

目录

变量注释表

1 绪论

1.1问题背景及意义(Background and Significance)

1.2研究现状(Research Status)

1.3预备知识(Prior Knowledge)

1.4本文的研究内容和结构安排(The Research Content and Structure of this Paper)

2 考虑不确定条件下的路段相关性的最优路径问题2 The Optimal Path Finding Problem Considering Correlations between Different Links under Uncertainty

2.1可靠路径的基本概念(The Concept of Reliable Path)

2.2相关性条件下的有效出行时间模型(The Effective Travel Time Model under the Condition of Correlation)

2.3相关性条件下的可靠路径搜索算法和相关证明(The Reliable Path Finding Algorithm under the Condition of Correlation and Relate Prove)

2.4算法流程图(Algorithm Flowchart)

2.5数值实验(Numerical Experimentation)

2.6 本章小结(Conclusion)

3 基于最优路径的关键路段问题

3.1 相关性条件下的最优路径的路段改进数学模型(The Mathematical Model of Improved Links Based on the Optimal Path under the Condition of Correlation)

3.2算法描述(Description)

3.3数值实验(Numerical Experimentations)

3.4 本章小结(Conclusion)

4 基于能耗和可靠性的双目标最优路径问题

4.1节能路径的概念(The Concept of Energy Saving Path)

4.2双目标路径搜索模型(The Bi-objective Path Finding Model)

4.3算法描述(Description)

4.4数值实验(Numerical Experimentations)

4.5 本章小结(Conclusion)

5总结和展望

5.1结论(Conclusion)

5.2进一步展望(Further Research Prospect)

参考文献

作者简历

学位论文数据集