时变、随机网络最优路径算法及其应用研究

摘要

最短路径问题是网络优化的核心技术.在传统的最短路径问题中,假设网络中的权值是静态的、确定的,这些假设在ITS、计算机网络与通信等许多应用领域是不现实的.时变、随机网络最优路径问题突破了传统的最短路径问题的局限性,成为ITS的基础理论.新的现实问题使得最优路径的计算变得非常困难.本文针对出现的新问题及前人研究中存在的问题,重点研究了时变网络中的最小时间路径问题、随机时间依赖网络期望最短路径问题、大规模网络模型与高效的路径计算问题,并针对计算机网络与通信的路由问题、智能交通系统的路径选择问题进行了应用研究.在时变网络方面,该文的工作分为三部分:(1)首次从理论上证明了传统的最短路径算法在时变网络中是不正确的并提出了时变网络中路径最优化的充分必要条件.在此基础上,在没有限制条件下设计实现了时间依赖的网络求解最小时间路径的算法并证明了算法的正确性.(2),利用该文给出的线性独立函数的智能神经元模型构成的广义神经网络,对交通流进行预测,进而给出了时变网络中每条弧的旅行时间预测方法,为时变网络最优路径算法及其在ITS的应用提供了完整的解决方案.(3)开展了时变网络在计算机路由协议的应用的研究,给出了时间依赖的混合型网络模型(HTDN模型),有效地描述了网络中链路权值随时间变化的特性,并且网络中的结点可以采用不同的等待策略,设计了一个新的、有效的时变网络分布式路由协议并证明了协议的正确性.在时变、随机网络方面,该文解决的问题是边耗费具有潜在的随机相关性和时间依赖性的路径规划问题,这样的问题使得问题求解变的非常困难.在这方面本文的主要工作是:(1)将随机时间依赖网络的路径规划问题转化成系统可靠性问题,给出了一个较弱的一致可靠性条件,确保基于可靠优先权的广义动态规划方法的正确性,给出了基于可靠性理论的求解最优路径问题的新方法和算法;(2)提出了新的随机优势判别法,使传统判别法的参数由二维降到一维,首次给出了K期望最路径的两种求解方法:基于可靠性理论的K期望寿命最短算法和基于随机优势的K期望最短路径算法;(3)首次给出了随机时间依赖网络K期望路径的并行算法.最后,将时变随机网络应用到公交网络中.该文提出的基于可靠性理论的模型和最优路径计算方法为解决随机网络的路径问题提供了新的途径.在大规模网络模型与高效的路径计算方面,该文提出了求解静态网络的新的层次网络模型和最优、近似最优路径算法.但是现有的层次网络模型和最优路径算法难以扩展到时变、随机网路中,为此该文提出了网络树模型和最优路径算法.实验结果表明,两种模型和算法的计算效率远远高于与传统的Dijkstra算法的计算效率.

目录

文摘

英文文摘

0引言

0.1 研究背景及意义

0.1.1时变、随机网络最优路径研究的科学依据及理论意义

0.1.2时变、随机网络最优路径的应用意义

0.2 时变、随机网络最优路径算法的发展历史和现状分析

0.2.1静态最短路径算法的研究

0.2.2时间依赖的网络中最小时间路径算法

0.2.3随机最短路径问题和算法

0.2.4最短路径问题的并行算法

0.2.5大规模网络模型与最优路径算法

0.3 问题的提出和本文主要贡献

0.3.1存在的问题

0.3.2本论文的主要贡献

0.4 论文的组织结构

1时间依赖网络最优路径算法

1.1 问题的提出

1.2 时间依赖的网络模型与理论基础

1.2.1模型

1.2.2时间依赖网络的理论基础

1.3 时间依赖网络最优路径求解算法

1.4小结

2随机时间依赖网络模型与最优路径算法

2.1 问题的提出

2.2 随机时间依赖网络K期望最短路径算法

2.2.1随机时间依赖网络模型

2.2.2扩展模型

2.2.3理论基础

2.1.2 K期望最短路径算法的理论基础

2.1.1 K期望最短路径算法

2.3 随机时间依赖网络K期望最短路径的并行算法

2.3.1数据分解型并行方法

2.3.2算法描述

2.3.3算法的正确性证明

2.3.4负载平衡

2.3.5实验结果

2.4 基于可靠性理论的随机时间依赖网络路径规划算法

2.4.1可靠性理论基础知识

2.4.2可靠性理论模型

2.4.3一致可靠性网络

2.4.4可靠优先权

2.4.5基于可靠性理论的优势判别法

2.4.6路径单调性

2.4.7期望失效时刻ET和期望寿命EL的计算方法

2.4.8期望寿命最短路径算法-RELSP算法

2.4.9 RELSP算法的正确性

2.4.10基于可靠性理论模型的K期望寿命最短路径算法

2.5小结

3大规模网络的网络模型与最优路径算法

3.1 问题的提出

3.2 层次网络模型与最优路径算法

3.2.1层次网络模型

3.2.2层次网络扩展模型

3.2.3层次网络最短路径算法的理论基础

3.2.4层次最短路径算法

3.2.5实验测试

3.3 网络树模型与最优路径算法

3.3.1网络树模型

3.3.2网络树模型最优路径算法

3.3.3实验测试

3.3.4实验测试结论

3.4小结

4时变、随机网络模型最优路径理论的应用研究

4.1 时间依赖网络在智能交通系统中的应用研究

4.1.1基于广义神经网络的交通流预测

4.1.2小结

4.2 随机时间依赖网络的应用

4.3 计算机网络路由协议中的应用

4.3.1时间依赖的混合型网络的分布式路由协议

4.3.2小结

5结论以及将来的工作

5.1 研究的问题以及意义

5.2 问题难点以及本文的工作

5.2.1时间依赖网络最优路径的研究

5.2.2随机时间依赖网络中期望最短路径研究

5.2.3大规模网络模型与最短路径算法的研究

5.2.4时变、随机网络最优路径算法的应用研究

5.3 将来的工作

参考文献

附录1本文的创新点

附录2论文期间发表论著情况

附录3论文期间完成或获得资助的课题情况

致谢