经典的最短路径问题是图论、网络优化中一个重要的研究内容,它不仅可用于解决生产实际中的许多问题,而且还常常作为一个基本工具用于解决其他优化问题。然而,大量现实世界中的网络都具有动态、随机特性,这种网络中两节点间最短路径的定义及其求解方法都不同于传统最短路径问题,对其进行研究具有广泛的实际应用价值和理论研究价值。本文针对动态随机网络最短路径问题进行了较为深入的系统研究。论文的研究内容和创新点主要包括以下几个方面:(1).提出了基于蚁群优化(ACO)的赋时蚁群优化(TACO)算法,用于解决动态随机网络先验(a priori)最短路径问题。首先阐明了在动态、随机环境下对先验最短路径问题进行研究的重要意义。然后对当前复杂网络搜索问题的研究情况及其方法进行了介绍,分析表明这些方法能够用于解决动态随机网络最短路径问题,然而,单独应用这些方法又存在一些不可避免的缺陷。考虑到复杂网络搜索方法本身的特点,本文将其融合于赋时蚁群优化的框架之中,既解决了单独采用这些方法时带来的缺陷,又充分利用了这些搜索方法提供的网络结构信息,从而提高了TACO算法的搜索质量和效率。此外,本文提出的TACO算法并不是适合所有的网络模型,而是主要针对现实世界中广泛存在的无标度网络模型,并希望籍此增强算法的针对性,从而进一步提高算法的有效性。(2).动态随机网络最短路径的求解需要考虑时间以及网络的状态,因此其问题规模相对经典最短路径问题显著增加。而对于诸如动态随机网络实时最短路径这类问题的求解,问题规模的扩大将使下一节点的选择计算量大增,这势必影响算法的有效性。而事实上,对于给定的动态随机网络源、目标节点对以及源节点出发时刻,可能只有很少一部分节点、边以及边的状态能真正最终构成实时最短路径,即大量的网络信息对于给定的最短路径求解都是冗余的。基于此,本文研究了用于动态随机网络实时最短路径求解的网络化简问题,给出了网络化简的具体思路和方法,并对影响算法化简结果的一些因素以及算法的复杂性进行了分析。(3).动态随机网络中边的通过耗费是一个不确定量,因此在某些边的通过耗费不具有周期性且难以预测的情况下,采用实时最短路径往往比采用先验最短路径更为有效。这里,实时最短路径由根据网络当前状态在线选择的下一节点构成。本文根据已有的研究成果,进一步分析了实时最短路径可能的度量方式,进而给出了采用负效用函数度量网络最短路径的定义。将CPA(convolution-propagation approach)近似处理方法引入到动态随机网络实时最短路径的求解中,并基于改进的遗传算法设计了相应的路径搜索算法GASPSP。(4).针对本文提出的TACO算法的算法性能进行了仿真分析,并对算法中一些影响算法性能的重要参数进行了相关分析;针对本文提出的网络化简算法进行了仿真分析,验证了其有效性;针对本文提出的实时最短路径算法进行了仿真分析和比较,验证了该算法的有效性。